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
    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.2012-11-08
  • 0
    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 ring2012-11-08
  • 0
    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.2012-11-08
  • 0
    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?2012-11-08
  • 0
    if it can't account for the whole ring, how can it be the whole ring?2012-11-08
  • 0
    at the same time though.. we know that +/- <5> partitions the group of units.. I can't seem to reconcile this. Don't the two contradict?2012-11-08
  • 0
    It can't be the whole ring. I suspect the problem is asking you to show that the _group of units_ $(\mathbb{Z}/2^a\mathbb{Z})^{\times}$ is expressible in this way, not the entire ring itself. There are elements not in the two cosets: all the non-units.2012-11-08
  • 0
    Exactly. Maybe this is what is causing me so much grief. The question I'm given clearly states "Deduce that every residue class (mod $2^a$) can be written as $\pm 5^r$ for some $r$2012-11-08
  • 0
    But ya I guess it has to only refer to the group of units. Clearly it doesnt hold else if it didnt. Anyways, thanks for taking the time to help out!2012-11-08
  • 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$.