Number Theorem 9th note
Artin's Conj
Original form: \(a \neq - 1\text{ sq. free}\), \(\exists\inf\) many \(p\) such \(a\) is a primitive root \(\operatorname{mod}p\).
Problem
Suppose that \(p,q > 0\) are odd primes with \(q = 4p + 1\).
Prove that \(2\) is a primitive root \(\operatorname{mod}q\). (HW)
Theorem 9.1
The group \(U_{n}\) is cyclic iff \(n = 1,2,4,p^{e},\text{ or }p^{2e}\), where \(p\) is an odd prime.
Pf
(<=)
We only left with the case \(n = 2p^{e}\).
By the multiplicativity,
\(\varphi(2p^{e}) = \varphi(2)\varphi(p^{e}) = \varphi(p^{e})\).
Let \(g\) be a primitive root \(\operatorname{mod}p^{e}\), then so is \(g + p^{e}\).
One of \(g\) and \(g + p^{e}\) must be odd.
So we have an odd primitive root \(h\operatorname{mod}p^{e}\).
We claim \(h\) is a prim. root \(\operatorname{mod}2p^{e}\).
By its construction, \(h\) is coprime to \(2\) and \(p\).
So \(h\) is a unit \(\operatorname{mod}p^{e}\), we have that \(\varphi(p^{e})|i\).
But \(\varphi(2p^{e}) = \varphi(p^{e})\), so \(\varphi(2p^{e})|i\).
Therefore, \(h\) has order \(\varphi(2p^{e})\) in \(U_{2p^{e}}\), and thus a prim. root.
(=>)
If \(n \neq 1,2,3,p^{e}\text{ or }2p^{e}\), then we must in one of the followity:
-
\(n = 2^{e}(e \geq 3)\)
-
\(n = 2^{e} \cdot p^{f}\left( e \geq 2,f \geq 1\text{ and }p\text{ odd prime} \right)\)
-
\(n\) is divisible by at least two odd primes.
In case (1), \(U_{n}\) is now cyclic by Prof. 8.13. Case (2) and (3) are covered Lemma 8.17.
Recall Corollary 7.8 and now the structure of \(U_{p^{e}}\) is known.
Corollary 9.2
If \(2^{f}\| n\), then
Remark 9.3
One can further factonze \(C_{p^{(e - 1)(p - 1)}}\). In general, we have
HW: Solve the congruence \(x^{5} \equiv 7\operatorname{mod}18\).
HW: Find an integer which is a primitive root \(\operatorname{mod}2 \cdot 11^{e}\) for all \(e \geq 1\).
Def 9.4
The exponent \(e(G)\) of a finite group \(G\) is the least integer \(e > 0\) such that \(a^{e} = 1\) forall \(a \in G\). The exponent \(e\left( U_{n} \right)\) is called the universal exponent of \(n\), denoted by \(e(n)\).
By Lagrange's theorm \(e(G)||G|\) so \(e(n)|\varphi(n)\).
Lemma 9.5
The exponent of product of cyclic groups is the lcm of their orders.
Ex. 9.6
Find the least three digits of \(3^{1001}\) ?(cf. \(\varphi(1000) = 400\))
Theorem 9.7 (Korselt)
If \(n\) is a Carmichael number, then \(n\) is a square-free and \(p - 1\) divides \(n - 1\) for each \(p\) dividing \(n\).
Pf
If \(n\) is a Carmichael, then by def
\(a^{n - 1} \equiv 1\operatorname{mod}n,\forall a \in {\mathbb{Z}}\).
So \(e(n)|(n - 1)\). If \(p^{f}\| n\), then \(e(n)\) is divisible by
\(e\left( p^{f} \right)\)
\(e\left( p^{f} \right) = \varphi(p(f)) = p^{(f - 1)(p - 1)}\), so
\(p - 1|n - 1\). If \(f > 1\), then \(p|n - 1\) as well. But this is
impossible since \(p|n\). Hence \(f\) is at most \(1\).
HW: 6.18, 6.20.
HW: Find all \(a\) such that \(x\mapsto x^{a}\) is a ring isomorphism for \({\mathbb{Z}}_{11}\).
9.1
One motivation. Solve quadratic equastions in \({\mathbb{Z}}_{n}\). Assume that \(\gcd(2a,n) = 1\). The quadratic congruence \(ax^{2} + bx + c \equiv 0\left( \operatorname{mod}n \right)\) has a solution iff \(\Delta = b^{2} - 4ac\) admits a square root \(s\) in \({\mathbb{Z}}_{n}\). In this case, the original form \(x=\frac{\left( - b \pm \sqrt{\Delta} \right)}{2a}\) can be interperted as \({( - b \pm s)(2a)}^{- 1}\).
Def 9.8
An element \(a \in U_{n}\) is a quadratic residue \(\operatorname{mod}n\) if \(a = s^{2}\) for some \(s \in U_{n}\); the set of such quad. res. is denoted by \(Q_{n}\).
Rmk
If \(S\) exists in \({\mathbb{Z}}_{n}\), then \(S\) must be in \(U_{n}\) because
Ex. 9.9
\(Q_{11} = \left\{ 1,4,9,5,3 \right\},Q_{12} = \left\{ 1 \right\}\)
The number of the square root of \(a \in Q_{n}\) does not depend on \(a\).
Suppose that \(s^{2} = a\) for some \(s \in U_{n}\),
then we can write any \(t \in U_{n}\) as \(t = s \cdot x\)
for some unique \(x \in U_{n}\).
Then \(t^{2} = a\) is equivalent to \(x^{2} = 1\operatorname{mod}n\).
The number \(N\) of solutions for \(x^{2} = 1\) is given by Example 5.3.
So
\(\left| Q_{n} \right| \cdot N = |U_{n}| \Rightarrow |Q_{n}| = \frac{\varphi(n)}{N}\).
Lemma 9.10
\(Q_{n}\) is a subgroup of \(U_{n}\). Moreover, the map \(\theta:U_{n} \rightarrow Q_{n}\) given by \(\theta(s) = s^{2}\) is an eprodmorphism (=homomorphism + surjection).
Pf
Check that \(Q_{n}\) contains \(1\) and closed under product, inverse. Checking the map is a homomorphism.(all easy!)
Rmk 9.11
The kernel \(\text{Ker}\theta\) of \(\theta\) is exactly the set of solutions to \(x^{2} \equiv 1\operatorname{mod}n\). We have an isomorphism \(U_{n}/\text{Ker}\theta ≌ Q_{n}\), which also explains \(\left| Q_{n} \right| = \frac{\varphi(n)}{N}\).
Lemma 9.12
Let \(n = n_{1}n_{2}\ldots n_{k}\) where the integer \(n_{i}\) are mutually coprime. Then \(a \in Q_{n}\) iff \(a \in Q_{n_{i}}\) for each \(i\).
Pf
The decomposition
\(U_{n} ≌ U_{n_{1}} \times U_{n_{1}} \times \ldots \times U_{n_{k}}\)
restricts to the subgroup \(Q_{n}\).
This is because an element in \(U_{n}\) is a square iff each of
its components in \(U_{n}\) is a square.
Lemma 9.13
Suppose that there is a primitive root \(g\operatorname{mod}n\) for \(n > 2\). The \(Q_{n}\) is also cyclic group of \(\frac{\varphi(n)}{2}\) generated by \(g^{2}\).
Pf
The condition \(n > 2\) ensure that \(\varphi(n)\) is even. We claim that \(Q_{n}\) precisely consists of elements of the form \(g^{2i}\). Clearly \(g^{2i} \in Q_{n}\). Conversely, if \(a \in Q_{n}\), then \(a{= \left( g^{j} \right)}^{2}\). Hence, \(Q_{n}\) is generated by \(g^{2}\) (and has order \(\frac{\varphi(n)}{2}\)).
Lemma 9.14
Let \(p\) be an odd prime. Then \(a \in Q_{p^{e}}\) iff \(a \in Q_{p}\).
Pf
We know from Theorem 9.1 that there is a primitive root \(g\operatorname{mod}p^{e}\). So \(Q_{p^{e}}\) consists of even powers of \(g\). But \(g\) is also a prim. root \(\operatorname{mod}p\). So \(Q_{p}\) also consists of even powers of \(g\).
Lemma 9.15
Let \(a\) be an odd integer. Then
-
\(a \in Q_{2}\)
-
\(a \in Q_{4}\text{ iff }a \equiv 1\operatorname{mod}4\)
-
\(a \in Q_{\left( 2^{e} \right)(e \geq 3)}\text{ iff }a \equiv 1\operatorname{mod}8\)
Pf
\(1\) and (2) are easy to be verified. For (3) we may write \(a = \pm 5^{i}\) according Prop. 8.13. So quad. res. are of the form \(5^{2i}\). Since \(5^{2} \equiv 1\operatorname{mod}8,5^{2i} \equiv 1\operatorname{mod}8\).
Both \(5^{i}\) and the elements \(a \equiv 1\operatorname{mod}8\) account for exactly one quarter of \(U_{2^{e}}\). The two sets must be equal.
Rmk. 9.16
To explicitly final the square roots of \(a \in U_{p^{e}}\), one can use Hensel's Lemma(Theorem 6.11).
HW: 7.15
Theorem 9.17
Let \(a \in U_{n}\). Then \(a \in Q_{n}\) iff
-
\(a \in Q_{p}\) for each odd prime dividing \(n\), and
-
\(a \equiv 1\operatorname{mod}4\) if \(2^{2}\| n\), and \(a \equiv 1\operatorname{mod}8\) if \(2^{3}|n\).
Pf
By Lemma 9.12, \(a \in Q_{n}\) iff \(a \in Q_{p}\) for each prime power \(p^{e}\) in the factorization of \(n\). For odd prime, this is equivalent to \(a \in Q_{p}\) by Lemma 9.14. For \(p = 2\), it is equivalent to condition (2) by Lemma 9.15.