¿Cómo encontrar el resto de $\frac{2^{99}}{9}$?

Question

La cuestión se resuelve en el libro que he leído en una forma muy extraña de como,

$$\frac{2^{99}}{9} = \dfrac{{(2^{3})}^{33}}{2^3-(-1)}$$ Por lo tanto por el teorema del resto el resto es $-1$. En las preguntas al resto es negativo que el número se resta de números como $2^3$ para obtener un número positivo, entonces, la respuesta es $8-{-1}=9$.

No sé cuál es el teorema del resto del libro es hablar de. Me he convertido la cuestión en mod notación,

$$2^{99} \bmod 9 = (2^3)^{33} \bmod (2^3 - (-1))$$

Pero no creo que hay alguna fórmula para $a \bmod (c-d)$. Por favor, dime cómo resolver este tipo de preguntas.

Answer 1

$$2^{99} \equiv (2^3)^{33} \equiv 8^{33} \equiv (-1)^{33} \equiv -1 \equiv 8 \pmod 9$$

Answer 2

El teorema que se refiere es, probablemente, el polinomio teorema del resto. Que es que el resto de $p(x)/(x-a)$$p(a)$. Así que con $p(x) = x^{33}$ $a=-1$ tenemos que el resto de la división será $p(-1) = (-1)^{33}$. Que es: $$p(x) = x^{33} = (x-(-1))q(x) + (-1)^{33} = (x-(-1))q(x) - 1$$

La inserción de $x = 2^3$ en los resultados de esta en

$$p(2^3) = (2^3-(-1))q(2^3) - 1 = 9q(2^3)-1$$

A partir de esto podemos ver que $2^{99} = 9q(2^3) - 1 = 9q(2^3)-9+8 = 9(q(2^3)-1) + 8$ y desde $q$ es un polinomio con términos enteros tenemos que $Q = q(2^3)-1$ es un número entero por lo $2^{99} = 9Q + 8$

---

Para la prueba del polinomio teorema del resto deje $p(x)$ ser un polinomio y el uso de euclides división con $x-a$ a continuación, vamos a obtener un resultado $q(x)$ y el restante $r(x)$ de grado uno menos que $x-a$, que es r(x) es una expresión de la constante de $C$. Ahora el resultado de la división será $$p(x) = q(x)(x-a) + r(x) = q(x)(x-a) + C$$.

Ahora sustituye $x$ $a$ y obtenemos

$$p(a) = q(a)(a-a) + C = 0q(a) + C = C$$

Answer 3

Para resolver preguntas como esta, el enfoque habitual es usar $$\def\mod{\mathbin{\rm mod}} ab \mod n = (a \mod n)(b\mod n) \mod n $ $ iterativamente. Vamos a comenzar. Tenemos que $$ 2^{99} = 2^{4\cdot 24 + 3} = 8 \cdot 16^{24} $ $ reducir modulo $9$, tenemos $$ 2^{99}\mod 9 = 8 \cdot 7^{24} \mod 9 $de % $ $7^{24} = 49^{12}$, reducir otra vez y seguir en ese camino\begin{align*} 2^{99} \mod 9 &= 49^{12}\cdot 8 \mod 9\\ &= 4^{12} \cdot 8 \mod 9\\ &= 16^6 \cdot 8 \mod 9\\ &= 7^6 \cdot 8 \mod 9\\ &= 49^3 \cdot 8 \mod 9\\ &= 4^3 \cdot 8 \mod 9\\ &= 16^2 \cdot 2 \mod 9\\ &= 49 \cdot 2 \mod 9\\ &= 8. \end{align*}

Answer 4

Podría ser que el libro estaba usando la fórmula de la suma geométrica en cambio $ \frac{1-x^{n+1}}{1-x}=1+x+x^2+\ldots+x^n. $$ de esta manera obtenemos $$ A=\frac{1-(-2^3)^{33}}{1-(-2^3)}=1-2^3+2^6-\ldots+2^{32}\in\mathbb{N} $ y $$ \frac{2^{99}}{9}=\frac{1-(-2^3)^{33}-1}{1-(-2^3)}=A-\frac{1}{9}. $$