# Every residue class $\pmod{2^a}$ can be written as $\pm 5^r$ for some $r$

So the question is to show that every residue class $\pmod{2^a}$ can be written as $\pm 5^r$ for some $r$.

The hint is to first show that:

For $a \ge 3$, and $H$ the multiplicative subgroup of $(Z/2^aZ)^*$ generated by $5\pmod{2^a}$ show that $-1 \notin H$

This is a homework question, so I'm not looking for an answer... but at this point I don't even know how to begin showing this. I really was hoping for no group theory to be in this course..

## 3 Answers

Lukas has shown you how to show that $-1$ is not in the cyclic group generated by $5$. You can then see that the groups $-\langle 5\rangle$ and $\langle 5\rangle$ form disjoint cosets.

The group of units modulo $2^a$ has order $\phi(2^a) = 2^{a-1}$. Now the hard part is showing that the order of $5$ modulo $2^a$ is $2^{a-2}$ so that the two cosets form an actual partition.

• Ya, thanks to lucas I was able to show -1 isnt in H. Once I get going I'm using OK, but for questions like these that bridge number theory and group theory... I don't really know which direction to approach a given problem from. I thought for sure this proof would be by contradiction somehow.. but apparently not. – Thomas Nesbitt Nov 8 '12 at 20:05
• Also, I'm a little hesitant on the last part of your argument there. If we show that the #units = #multiples of 5, -5.. how does this imply we can write every unit as +/-5 ? Since not all elements are units in this ring – Thomas Nesbitt Nov 8 '12 at 20:07
• Right now, the statement "every residue class in $2^a$ can be written as $\pm 5^r$" is not true. The order of $5$ mod $2^a$ is $2^{a-2}$ so that together, $\pm \langle 5\rangle$ contains $2^{a-1}$ elements which is not enough to account for the entire ring. That is the cardinality of the group of units however and $\pm 5^r$ is always a unit itself, so it necessarily partitions the group into the two cosets. – EuYu Nov 8 '12 at 20:18
• Bahh I still don't get it. As you said, $\pm<5>$ contains $2^{a-1}$ elements and thus cant account for the whole ring. So there are elements in the ring not in either coset? – Thomas Nesbitt Nov 8 '12 at 20:24
• if it can't account for the whole ring, how can it be the whole ring? – Thomas Nesbitt Nov 8 '12 at 20:25

Hint: Let $v_2(n)$ denote the exponent of $2$ in $n$.

If $4 | x-y$, we have $v_2(x-y) = v_2(n) + v_2(x-y)$. (For a proof see http://www.artofproblemsolving.com/Resources/Papers/LTE.pdf )

So let $x$ denote the order of $5$ modulo $2^a$. Since $x \mid 2^a$, we must have $x = 2^k$. Now using the theorem , $a= v_2(5 ^{2^k} - 1) = v_2(2^2) + v_2(2^k) = k+2$.So $k = a-2$ i.e order of $5$ modulo $2^a$ is $2^{a-2}$. (We can possibly prove this by induction too.)

Now $5^r + 1 \equiv 2 \mod 4$, so for $a \ge 2$,indeed $-1 \not\in \left(\mathbb{Z}/2^a\mathbb{Z}\right)^{\times}$.

Now it is not hard to conclude.

As a first step for the hint: $5\equiv 1 \pmod 4$, so $5^r \equiv 1 \pmod 4$ for all $r \in \mathbb{Z}$. And $1\not\equiv -1 \pmod 4$. Now if $5^r \equiv -1 \pmod {2^a}$ for $a\ge 2$, then this congruence would also have to be true modulo $4$.