Proposition 3

Let $p > 2$ be a prime number and let $n > 0$ be an integer; then the group $U(p^n)$ is cyclic of order $p^{n-1}$; if $n \geq 2$ then the residue class mod $p^n$ of an integer $x$ congruent to 1 mod $p$ is a generator of $U(p^n)$ if and only if $x$ is not congruent to 1 mod $p^2$. Let $m > 1$ be an integer; then the group $U(2^m)$ is cyclic of order $2^{m-2}$; if $m \geq 3$ then the residue class mod $2^m$ of an integer $x$ congruent to 1 mod 4 is a generator of $U(2^m)$ if and only if $x$ is not congruent to 1 mod 8.

Since $U(p^n)$ has order $p^{n-1}$, the order of every element $u$ of $U(p^n)$ is a power of $p$, and $u$ is a generator of $U(p^n)$ if and only if $u^{p^{n-2}} \neq 1$. Now if $u$ is the class of $x = 1 + py$, then $u^{p^{n-2}}$ is the class of $1 + p^{n-1}y$, by Lemma 3, whence $u$ generates $U(p^n)$ if and only if $y \not\equiv 0 \mod p$, in other words $x \not\equiv 1 \mod p^2$. For example, the class $1 + p$ generates $U(p^n)$. Similarly, the class $u$ of $x$ mod $2^n$ generates $U(2^n)$ if and only if $u^{2^{n-3}} \neq 1$, which means that $x$ is not congruent to 1 mod 8, by Lemma 3; this is satisfied by $x = 5$.