Encontrar el resto de $13*12^{45}$ dividido por $47$

Question

Escribí $13\times 12^{45}$ $(12+1)\times 12^{45} = 12^{46}+12^{45}$ por lo que puede utilizar de Fermat decir que $12^{46}$ es igual a $1$$\Bbb Z_{47} $.

Ahora sólo tengo que encontrar a $12^{45}$$\Bbb Z_{47} $. Sé que $12^2 = 144$ lo que equivale a $3$$\Bbb Z_{47} $, y por la multiplicación de que una y otra vez por $12$ y el uso de algunas propiedades de congruencias llegué a $12^{45}$. Me las arreglé para ver que el total del resto es $22$ (no estoy seguro de si eso es correcto).

De todos modos, este método me llevó mucho tiempo y estoy seguro de que no es de otra manera, la forma más rápida, para resolverlo. Cualquier sugerencia?

Answer 1

Desde $12^{46} \equiv 1$, tenemos $12^{45} \equiv 12^{-1}$, que se encuentra más fácilmente usando el Algoritmo euclidiano extendido: quiere un entero $x$ tal que $12x\equiv 1$, que es lo mismo que decir te quiero un $x$ que hay un entero $n$, así que eso $$ 12 x +47n = 1 $ y al euclidiano extendido gorithm es exactamente lo que ofrece tal un $x$ (y un $n$ como bien, pero importa).

Answer 2

Desde $48\equiv1$mod $47$, tenemos

$$13\cdot12^{45}\equiv48\cdot13\cdot12^{45}=52\cdot12^{46}\equiv5\cdot1=5\mod 47$$

Answer 3

Tenga en cuenta que $47$ es primo, tenemos $12^{46} \equiv 1 \pmod{47}$ por el pequeño Teorema de Fermat.

Así, podemos reducir la expresión $13 \times 12^{45} = 12^{46} + 12^{45} \equiv 1 + 12^{-1} \pmod{47}$

Para evaluar esto, señalamos el hecho de que $12 \times 4 = 48 \equiv 1 \pmod{47}$. Así, $4 \equiv 12^{-1} \pmod{47}$.

Sustituyendo esto en nos da $13 \times 12^{45} \equiv 1+4 = 5 \pmod{47}$.