Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\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\}$

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer

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\,$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.