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?
How to calculate $3^{45357} \mod 5$?
-
2It’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. – 2012-11-11
3 Answers
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$.
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.
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$
-
0Could you explain the second line, please? How the second equation results from the first one? – 2012-11-11
-
0@o2genum, please find the edited answer.Please let me know you have any more confusion. – 2012-11-11
-
0@o2genum The $\implies$ sign was indeed misleading. – 2012-11-11
-
0@did, is the latest version clear enough? – 2012-11-11
-
0Dunno, ask the OP. (Anyway, invoking Fermat to check that 81 = 1 mod 5 (something already noted by the OP)...) – 2012-11-11
-
0Yes, thank you very much: finally, I got it. Maybe it would be excessive, but for such plain newbies as me there would be helpful some references to basic modular arithmetic laws ($a \equiv b \implies a^n \equiv b^n \pmod m$ for integer $a, b, n \geq 0$, and $ad \equiv bd \Leftrightarrow a \equiv b \pmod m$ for integer $a, b, d, m$ and $d$ is relatively prime to $m$) – 2012-11-11
-
0@o2genum,though acceptably excessive, it is useful generalization and address similar problems. I think you meant if $ad\equiv bd\pmod m\implies a\equiv b\pmod m$ if $(d,m)=1$ – 2012-11-11
-
0Yes, I meant that, and is my variant not quite right? – 2012-11-11
-
0@o2genum, it's ok and $m$ does not need to be prime. – 2012-11-11
-
0$m$ is not exactly prime, it's relativaly prime to $d$ which means just $gcd(d, m) = 1$. Thanks again for that elegant proof. – 2012-11-11
-
0@o2genum, that's what I meant. – 2012-11-11