Usando el pequeño teorema de Fermat, encuentre el residuo menos positivo de$3^{999999999}\mod 7$

Question

Estoy pasando por los problemas de la Teoría de números elementales de Rosen y tengo algunos problemas con este problema,

Encuentra el residuo menos positivo de$3^{999999999}\mod 7$.

Answer 1

Fermat Poco teorema dice que

Si $p$ es un primer e $a \nmid p$, $$a^{p-1} \equiv 1 \mod p.$$

Podemos usar este teorema para reducir los exponentes, como en el problema en cuestión. En primer lugar, debemos observar que la hipótesis de Fermat Poco Teorema se cumplen. Es decir,

$$7 \ \text{is prime and } 3 \nmid 7.$$

Así tenemos que,

$$3^6 \equiv 1 \mod 7.$$

El exponente por lo tanto puede reducirse de la siguiente manera,

$$3^{999999999} \equiv 3^{999999996} \cdot 3^3 \equiv \left( 3^6 \right)^{166666666} \cdot 3^3 \equiv 1^{166666666} \cdot 3^3 \equiv 1 \cdot 27 \equiv 6 \mod 7.$$

Answer 2

Desde FLT,$3^6\equiv 1 \pmod 7.$ Desde$999999999 = 166666666 \times 6 + 3$ tenemos$$ 3^{999999999} \equiv 3^3\equiv 6.$ $

Answer 3

Insinuación: $\, {\rm mod}\ 7\!:\ \color{#c00}{3^3\equiv -1}\,\Rightarrow\, (\color{#c00}{3^3})^{333333333}\equiv (\color{#c00}{-1})^{333333333}\equiv -1$