Cómo calcular $3^{45357} \mod 5$ ?

Question

He escrito algo de código, esto es lo que da: \begin{align*} 3^0 \mod 5 = 1 \\ 3^1 \mod 5 = 3 \\ 3^2 \mod 5 = 4 \\ 3^3 \mod 5 = 2 \\\\ 3^4 \mod 5 = 1 \\ 3^5 \mod 5 = 3 \\ 3^6 \mod 5 = 4 \\ 3^7 \mod 5 = 2 \\\\ 3^8 \mod 5 = 1 \\ 3^9 \mod 5 = 3 \\ 3^{10} \mod 5 = 4 \\ 3^{11} \mod 5 = 2 \\\\ 3^{12} \mod 5 = 1 \\ 3^{13} \mod 5 = 3 \\ ... \end{align*} Como veo, hay un punto $1, 3, 4, 2$ . E intuitivamente, es fácil predecir que $3^{45357} \mod 5 = 3$ . Desgraciadamente, casi no estoy familiarizado con las matemáticas modulares. ¿Podría darme una explicación analítica estricta de esta cosa?

Answer 1

El patrón que has visto aquí es que $3^{4k+1}\;\text{mod}\:5=3$ para los enteros $k\ge 0$ . Se puede demostrar esto inductivamente a partir del caso base, y el hecho de que $3^4=81$ es igual a $1$ modulo $5$ . Por lo tanto, ya que $4\cdot 11339+1=45357$ entonces su predicción se mantiene.

Answer 2

Utilizando Pequeño teorema de Fermat ,

$a^{p-1}\equiv1\pmod p$ si $(a,p)=1$

$\implies (a^{p-1})^d\equiv1^d\pmod p \equiv1 \pmod p$

si $b=c+(p-1)d$ es decir, $b\equiv c\pmod {p-1}$ donde $a,b,c,d$ son enteros no negativos y $p$ es primo,

$ a^b=a^{c+(p-1)d}=a^c\cdot(a^{p-1})^d\equiv a^c\pmod p$

Aquí, $3^{5-1}\equiv 1\pmod 5$ como $(3,5)=1$

Como $45357\equiv 1\pmod 4\implies 3^{45357}\equiv 3^1\pmod 5\equiv 3$

Answer 3

Como dices que no estás familiarizado con la aritmética modular, aquí tienes una prueba alternativa. Su exponente $45357$ tiene forma $\rm\:4n+1\:$ y su pequeña tabla de valores satisfacen todos $\rm\: mod\ 5\!:\ 3^{4n+1}\! \equiv 3,\:$ es decir $\rm\:5\mid 3^{4n+1}\!-3 = 3(3^{4n}-1).\:$ Esto es cierto ya que $\rm\:5\cdot 16 = 3^4-1\:|\:3^{4n}\!-1\ $ por $\rm\:x-1\:|\:x^n-1$ .