4
$\begingroup$

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 3

3

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.

  • 0
    If you still can't (or don't want to) believe it try multiplying out $\pm\langle 5 \rangle$ in mod $8$. You'll see that $0,\ 2,\ 4,\ 6$ are not represented.2012-11-08
1

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.

0

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