What is the rest of dividing $5^n$ by $7$?

76 Views Asked by At

It seems to repeat every 6 values of $n$: \begin{align} 5^1 &\equiv 5 \pmod{7} \\ 5^2 &\equiv 4 \pmod{7} \\ 5^3 &\equiv 6 \pmod{7} \\ 5^4 &\equiv 2 \pmod{7} \\ 5^5 &\equiv 3 \pmod{7} \\ 5^6 &\equiv 1 \pmod{7} \\ 5^7 &\equiv 5 \pmod{7} \\ & \dots \end{align}

So it seems to depend on the divibility of $n$ by 6, but I can't figure out if there is a better pattern such as an expression in terms of $n$, or how to prove it more formally.

1

There are 1 best solutions below

2
On BEST ANSWER

What you've discovered is called the multiplicative order of $5$ mod ($7$). It is the smallest integer $x$ such that $5^x\equiv 1 \mod(7)$. It is a fact that if $x$ exists for any particular congruence class mod(n) that $x$ must divide $\phi(n)$, which is Euler's totient function evaluated at n. If n is prime then this is simply equal to $n-1$ (as any prime is coprime to all numbers less than itself), and all congruence classes with a prime modulus are guaranteed to have a multiplicative order (more generally, if $a$ and $n$ are coprime, then $a^x \equiv 1 \mod(n)$ always has a solution). In your example $n=7$, which is prime, so the order of any element mod($7$) must divide $7-1=6$. Note that $\phi(n)$ may not always be equal to the multiplicative order, only that it must be divisible by it. For example, $2^3\equiv 1 \mod(7)$ and $3|\phi(7)$.