2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ See also this question. $\endgroup$ May 2, 2017 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, 2017 at 21:25

1 Answer 1

2
$\begingroup$

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

$\endgroup$
7
  • $\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, 2017 at 20:44
  • $\begingroup$ It shows $5^{2^r}\not\equiv1$ but $5^{2^{r+1}}\equiv1\pmod{2^{r+3}}$. $\endgroup$ May 3, 2017 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, 2017 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$ May 3, 2017 at 4:41
  • 1
    $\begingroup$ Could we really have $5^{2^{k-3}}\not\equiv1$ but $5^{2^{k-4}}\equiv1$? $\endgroup$ May 3, 2017 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .