5
$\begingroup$

I wrote some code, here is what it gives: \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*} As I see, there's a period $1, 3, 4, 2$. And intuitively, it's easy to predict that $3^{45357} \mod 5 = 3$. Unfortunately, I'm almost unfamilar with modular math. Could you give me strict analytic explaination of this thing?

$\endgroup$
  • 2
    $\begingroup$ It’s a theorem that the nonzero residues modulo a prime form a cyclic group. In this case, of order four, and generated, as you’ve seen, by the residue of $3$. So the value of $3^n$ modulo $5$ depends only on the residue of $n$ modulo $4$, you’re done. $\endgroup$ – Lubin Nov 11 '12 at 7:00
4
$\begingroup$

Using Fermat's Little theorem,

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

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

if $b=c+(p-1)d$ i.e., $b\equiv c\pmod {p-1}$ where $a,b,c,d$ are non-negative integers and $p$ is prime,

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

Here, $3^{5-1}\equiv 1\pmod 5$ as $(3,5)=1$

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

$\endgroup$
  • $\begingroup$ Could you explain the second line, please? How the second equation results from the first one? $\endgroup$ – Andrey Moiseev Nov 11 '12 at 7:36
  • $\begingroup$ @o2genum, please find the edited answer.Please let me know you have any more confusion. $\endgroup$ – lab bhattacharjee Nov 11 '12 at 7:41
  • $\begingroup$ @o2genum The $\implies$ sign was indeed misleading. $\endgroup$ – Did Nov 11 '12 at 8:29
  • $\begingroup$ @did, is the latest version clear enough? $\endgroup$ – lab bhattacharjee Nov 11 '12 at 8:32
  • $\begingroup$ Dunno, ask the OP. (Anyway, invoking Fermat to check that 81 = 1 mod 5 (something already noted by the OP)...) $\endgroup$ – Did Nov 11 '12 at 8:35
6
$\begingroup$

The pattern you've seen here is that $3^{4k+1}\;\text{mod}\:5=3$ for integers $k\ge 0$. You can prove this inductively from the base case, and the fact that $3^4=81$ is equal to $1$ modulo $5$. Hence, since $4\cdot 11339+1=45357$, then your prediction holds.

$\endgroup$
1
$\begingroup$

Since you say you are unfamiliar with modular arithmetic, here is an alternative proof. Your exponent $45357$ has form $\rm\:4n+1\:$ and your small table of values all satisfy $\rm\: mod\ 5\!:\ 3^{4n+1}\! \equiv 3,\:$ i.e. $\rm\:5\mid 3^{4n+1}\!-3 = 3(3^{4n}-1).\:$ This is true since $\rm\:5\cdot 16 = 3^4-1\:|\:3^{4n}\!-1\ $ by $\rm\:x-1\:|\:x^n-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.