Largest possible order in the multiplicative group mod n

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

• See also this question. – Dietrich Burde May 2 '17 at 19:17
• 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}}$? – 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$.
• 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? – Nasenhaar May 2 '17 at 20:44
• It shows $5^{2^r}\not\equiv1$ but $5^{2^{r+1}}\equiv1\pmod{2^{r+3}}$. – Lord Shark the Unknown May 3 '17 at 4:23
• 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}$? – Nasenhaar May 3 '17 at 4:29
• You also know $5^{2^{k-2}}\equiv1\pmod{2^k}$. So the order of $5$ is a factor of $2^{k-2}$. – Lord Shark the Unknown May 3 '17 at 4:41
• Could we really have $5^{2^{k-3}}\not\equiv1$ but $5^{2^{k-4}}\equiv1$? – Lord Shark the Unknown May 3 '17 at 4:56