el resto de la división de $7^{1203}$ por $143$

Question

Tengo que encontrar el resto de la división de $7^{1203}$ por $143$. Pensé que podría utilizar el Teorema de Euler: Deje $a \in \mathbb{Z}$ e $n \in \mathbb{N}$.También sabemos que $(a,n)=1$.A continuación, $a^{\varphi(n)} \equiv 1 \mod n$ Así,tomamos $a=7$ e $n=143$ y ver que $(a,n)=1$.Así,desde el teorema anterior,obtenemos que $7^{120} \equiv 1 \mod 143$. $$7^{1203} \mod 143=7^{10 \cdot 120+3} \mod 143=(7^{120})^{10} \cdot 7^{3} \mod 143=7^{3} \mod 143=57$$ Para el resto de la división de $7^{1203}$ por $143$ es $57$.Es que lo he hecho bien o he hecho algo mal??

Answer 1

Todo se ha hecho correctamente. La siguiente es una "mejora" que no es necesario en este caso.

Imagine trabajar por separado modulo $11$ e $13$. Tenemos $7^{10}\equiv 1\pmod{11}$ e $7^{12}\equiv 1\pmod{13}$. Tenga en cuenta que $60$ es el mcm de $10$ e $12$. De ello se desprende que $7^{60}\equiv 1$ modulo $11$ e $13$, y por lo tanto el modulo $143$.

Si el exponente ha sido $1263$ en lugar de $1203$, esta observación habría ahorrado una cantidad significativa de tiempo.

Tenga en cuenta que la más clara primos divisores el módulo de $n$, más tendemos a ahorrar mediante el uso de este tipo de truco.