I am trying to figure out what is the largest possible order that an element of the multiplicative group $\bmod{n}$ can have if $n=p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_m^{k_m}$.

then I can prove that

$$U(n) \cong U(p_1^{k_1}) \times U(p_2^{k_2}) \times \dots \times U(p_m^{k_m})$$

Now I know from my number theory book, that if $p_i$ is an odd prime, then $p_i^{k_i}$ has a primitive root, which makes $U(p_i^{k_i})$ cyclic. So the largest order of an element in that group is $\phi(p_i^{k_i})$. I also know, that $2$ and $4$ have primitive roots, so the largest orders in $U(2)$ and $U(2^2)$ are $\phi(2)$ and $\phi(2^2)$ respectively.

However, I am having trouble with $U(2^k)$ where $k\geq 3$.

I was able to show that for any $x\in U(2^k), \quad x^{2^{k-2}}\equiv 1 \pmod{2^k}$.

But how can I show that there $\textbf{must}$ be an element of order $2^{k-2}$ in $U(2^k), k\geq3$ ?

  • $\begingroup$ See also this question. $\endgroup$ – Dietrich Burde May 2 '17 at 19:17
  • $\begingroup$ Thanks for that pointer, that was certainly helpful. However, how is enough to show that $5^{2^{k-3}}\not\equiv 1 \pmod{2^k}$? Don't we have to consider all the other possible exponents, $5^{2^{k-i}}$? $\endgroup$ – Nasenhaar May 2 '17 at 21:25

The number $5$ has order $2^{k-2}$ in $U(2^k)$ for $k\ge3$. To prove this use induction to prove that $$5^{2^r}\equiv 1+2^{r+2}\pmod{2^{r+3}}$$ for all integers $r\ge0$.

  • $\begingroup$ I proved what you suggested, but I am still having troubles using that result to conclude that $5$ has order $2^{k-2}$. How does that follow? $\endgroup$ – Nasenhaar May 2 '17 at 20:44
  • $\begingroup$ It shows $5^{2^r}\not\equiv1$ but $5^{2^{r+1}}\equiv1\pmod{2^{r+3}}$. $\endgroup$ – Lord Shark the Unknown May 3 '17 at 4:23
  • $\begingroup$ Then I know that $5^{2^{k-3}} \not \equiv 1\pmod{2^k}$. How do we know that no smaller exponent of $5$ could be congruent to $1 \pmod{2^k}$? $\endgroup$ – Nasenhaar May 3 '17 at 4:29
  • $\begingroup$ You also know $5^{2^{k-2}}\equiv1\pmod{2^k}$. So the order of $5$ is a factor of $2^{k-2}$. $\endgroup$ – Lord Shark the Unknown May 3 '17 at 4:41
  • 1
    $\begingroup$ Could we really have $5^{2^{k-3}}\not\equiv1$ but $5^{2^{k-4}}\equiv1$? $\endgroup$ – Lord Shark the Unknown May 3 '17 at 4:56

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.