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.

How can I prove that $5^n \equiv 1 (\bmod 2^r$) when $n=2^{r-2}$?

Actually what I am trying to prove is that the cyclic group generated by the residue class of $5 (\bmod 2^r)$ is of order $2^{r-2}$.

share|improve this question
3  
I think induction on $r$ does it. –  lhf Jan 2 '12 at 13:59
1  
If you want to use a cannonball to swat flies, $(\mathbb{Z}/2^r\mathbb{Z})^*\cong \mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2^{r-2}\mathbb{Z}$ for $r\geq 2$; hence, the group of units has exponent $2^{r-2}$. when $r\geq 3$. –  Arturo Magidin Jan 2 '12 at 18:21
    
@ArturoMagidin: This was the question, actually. Which I couldn't prove. –  James Jan 2 '12 at 18:26
1  
@Karatug: Well, no; the statement you have is weaker (you are only asking how to show the order of $5$ divides $2^{r-2}$; and even if you show the order is exactly $2^{r-2}$, then you don't get the structure of the unit group from that (you only get that it has a cyclic factor of order at least $2^{r-2}$, but it could be cyclic of order $2^{r-1}$ if all you know is the order of $5$). –  Arturo Magidin Jan 2 '12 at 18:52
1  
@Karatug: Here is a previous answer that shows the order of $5$ is exactly $2^{r-2}$ modulo $2^r$. –  Arturo Magidin Jan 2 '12 at 18:56

4 Answers 4

up vote 5 down vote accepted

Hint: If $a=1\pmod{2b}$ then $a^2=1\pmod{4b}$.

(Proof: if $a=2bk+1$ then $a^2=4bk(bk+1)+1$. End of the proof.)

Use this for $a=5^n$, $n=2^{r-2}$ and $b=2^{r-1}$, to build a proof by induction on $r$, starting from the $r=2$ case $5^1=1\pmod{4}$.

share|improve this answer
1  
Works for the first question. To reach OP's extra goal you need to make the extra observation that when $b$ is even and $k$ is odd, then $$a^2\not\equiv 1\pmod{8b}.$$ –  Jyrki Lahtonen Jan 2 '12 at 18:46

We divide your original problem into two parts. The specific question you asked has nothing to do with $5$ and is answered for all odd $a$ in Part $1$. The fact that the order of $5$ is actually $2^{r-2}$ and not something smaller is proved in Part $2$.

Part $1$: Suppose that $a$ is odd, and $r \ge 3$. Then $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Since $2^r$ does not have a primitive root, the order of $a$ modulo $2^r$ is less than $\varphi(2^r)$. But the order of $a$ divides $\varphi(2^r)$. Since $\varphi(2^r)=2^{r-1}$, it follows that the order of $a$ is a divisor of $2^{r-1}$ which is less than $2^{r-1}$. Thus the order of $a$ divides $2^{r-2}$. It follows that $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Part $2$: We show that if $r\ge 3$, then $5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$. This will show that the order of $5$ modulo $2^r$ is actually $2^{r-2}$, and not something smaller.

We show by induction that $5^{2^{r-3}}\equiv 1+2^{r-1} \pmod{2^r}$, and so in particular $5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$.

It is easy to check that the result holds at $r=3$. Suppose now that $5^{2^{k-3}}\equiv 1+2^{k-1} \pmod{2^k}$. We show that $5^{2^{k-2}}\equiv 1+2^{k} \pmod{2^{k+1}}$.

By the induction assumption $5^{2^{k-3}}= 1+2^{k-1} +s2^k$ for some $s$. Square both sides, and simplify modulo $2^{k+1}$. We get that $$5^{2^{k-2}}=(1+2^{k-1} +s2^k)^2 \equiv 1+2^k +2^{2k-2}\pmod{2^{k+1}}.$$ But $2^{2k-2}$ is divisible by $2^{k+1}$, since $k \ge 3$. The result follows.

share|improve this answer

Hint: $$ 5^{2^{k+1}}-1=(5^{2^k}-1)(5^{2^k}+1) $$ The latter factor is always congruent to $2\pmod 4$. I recommend that you then prove a result giving the exact power of two that divides $5^{2^n}-1$ by induction on $n$. This gives you the order of the residue class of $5$ modulo any power of two.

share|improve this answer

Let a be an odd integer=2b+1(say), $$a^2=4b^2+4b+1=8b(b+1)/2+1=8c+1 $$(say) where $$c=b(b+1)/2$$ an integer (See also If $n$ is an odd natural number, then $8$ divides $n^{2}-1$) $$a^4=(1+8c)^2=1+16c+64c^2=1+16d $$ for some integer $$d=c+4c^2$$ $$a^8=(1+16d)^2=1+32d+256d^2=1+32e$$ Using induction for n≥3,we get $$a^{2^{n-2}}≡1(mod 2^n).$$ See http://www.amazon.com/Introduction-Theory-Numbers-Ivan-Niven/dp/0471625469

share|improve this answer

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.