Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Lubin Nov 11 '12 at 7:00
add comment

3 Answers

up vote 4 down vote accepted

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$

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

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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