# primitive residue classes modulo 32

$\mathbb Z_{32}^*$ is the primitive residue classes modulo 32. How is it possible to show that $\mathbb Z_{32}^*$ is generated by 5 and -1, without showing it for every element of $\mathbb Z_{32}^*$=$\{1,3,5,7,9,11,...,31\}$

-

The number $32$ is small, so it is easy to show by computing that $5$ has order $8$. Note that we only need to compute $5^{2^k}$ modulo $32$. For $\varphi(32)=16$, so the order of $5$ must be a power of $2$.

The following is severe overkill. We show that for any $n\ge 3$, $\mathbb{Z}^\ast_{2^n}$ is generated by $5$ and $-1$.

Lemma: Let $n\ge 3$. Then $5^{2^{n-3}}\not\equiv 1 \pmod{2^n}$, while $5^{2^{n-2}}\equiv 1\pmod{2^n}$.

Proof of Lemma: We show by induction on $n$ that if $n \ge 3$, then $5^{2^{n-3}}\equiv 1+2^{n-1}\pmod{2^n}$. This easily yields both parts of our assertion.

The result is easy to check for $n=3$. Suppose now that $$5^{2^{k-3}}\equiv 1+2^{k-1}\pmod{2^{k}}.\tag{1}$$ We show that $5^{2^{k-2}}\equiv 1+2^{k}\pmod{2^{k+1}}$. Square both sides of $(1)$, and simplify modulo $2^{k+1}$. We get $$5^{2^{k-2}}=(1+2^{k-1} +n2^k)^2\equiv 1+2^{k}\pmod{2^{k+1}},$$ since $2^{2k-2}$ is divisible by $2^{k+1}$ if $k\ge 3$. This ends the proof of the lemma.

Now it is easy to finish. The order of $5$ modulo $2^n$ divides $\varphi(2^n)=2^{n-1}$, so the order of $5$ is a power of $2$. It follows from the results above that the order of $5$ is exactly $2^{n-2}$.

No power of $5$ is congruent to $-1$ modulo $2^n$. It follows that if $n \ge 3$, then $5$ and $-1$ together generate all of $\mathbb{Z}^\ast_{2^n}$.

-

Let $n > 1$ be an integer. We consider the group $G = (\mathbb{Z}/2^n\mathbb{Z})^*$. Clearly $|G| = 2^{n-1}$.

Let $e \ge 2$ be an integer. Let $k$ be an odd integer. $(1 + 2^e k)^2 = 1 + 2^{e+1}k + 2^{2e} k^2 = 1 + 2^{e+1}(k + 2^{e-1}k^2)$. Note that $k + 2^{e-1}k^2$ is odd. Hence, by induction on $m \ge 1$, $(1 + 2^e k)^{2^m} = 1 + 2^{e+m}k'$ for some odd integer $k'$.

Since $5 = 1 + 2^2$, $5^{2^m} = 1 + 2^{m + 2}k'$, where $k'$ is odd. Hence the order of $5$ in $G$ is $2^{n-2}$. Let $H$ be the subgroup of $G$ generated by $5$. Suppose $-1 \in H$. There exists integer $m$ such that $-1 \equiv 5^m$ (mod $2^n$). Since $5 \equiv 1$ mod $4$, $-1 \equiv 1$ (mod $4$). This is a contradiction. Hence $G$ is generated by $-1$ and $5$.

-

Working modulo $\,32\,$:

$$5^2=-7\;\;,\;\;5^3=-35=-3\;\;,\;5^6=(5^3)^2=9\;\;,\;5^8=5^6\cdot 5^2=9\cdot (-7)=-63=1$$

$$\Longrightarrow 5^8=1\Longrightarrow ord_{32}(5)=8$$

$$(-1)^2=1\Longrightarrow ord_{32}(-1)=2$$

Finally, since $\,\langle 5\rangle\cap\langle -1\rangle=\{1\}\,$ , we get that

$$\langle 5\rangle\langle-1\rangle\cong\langle 5\rangle\otimes\langle -1\rangle\cong\Bbb Z_{32}^*$$

since $\left|\Bbb Z_{32}^*\right|=\phi(32)=16\,$

-
You also need to show that $5^4\neq 1$, so that the order of $5$ is exactly $8$ and no less. – Brett Frankel Oct 30 '12 at 1:11
Correction: the OP needs to show that, not I. Since I made the calculation for $\,5^3=-3\,$, the work left is trivial. – DonAntonio Oct 30 '12 at 2:52