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


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.

  • $\begingroup$ 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. $\endgroup$ – Thomas Nesbitt Nov 8 '12 at 20:05
  • $\begingroup$ 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 $\endgroup$ – Thomas Nesbitt Nov 8 '12 at 20:07
  • $\begingroup$ 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. $\endgroup$ – EuYu Nov 8 '12 at 20:18
  • $\begingroup$ 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? $\endgroup$ – Thomas Nesbitt Nov 8 '12 at 20:24
  • $\begingroup$ if it can't account for the whole ring, how can it be the whole ring? $\endgroup$ – 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$.


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.