| 1. | Lecture 1 |
| 2. | Lecture 2 |
| 3. | Lecture 3 |
| 4. | Lecture 4 |
| 5. | Lecture 5 |
| 6. | Lecture 6 |
| 7. | Lecture 7 |
| 8. | Lecture 8 |
| 9. | Lecture 9 |
| 10. | Lecture 10 |
| 11. | Lecture 11 |
| 12. | Lecture 12 |
| 13. | Lecture 13 |
Example. The following table lists the primitive roots for the first six primes.
| \(p\) | \(\varphi(p-1)\) | primitive roots |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 1 | 2 |
| 5 | 2 | 2,3 |
| 7 | 2 | 3,5 |
| 11 | 4 | \(2,6,7,8\) |
| 13 | 4 | \(2,6,7,11\) |
Index with respect to the primitive roots.
Let \(p\in\mathbb P\) be a prime, and let \(g\) be a primitive root modulo \(p\). If \(a\in\mathbb Z\) is not divisible by \(p\), then there is a unique \(k \in\{0,1, \ldots, p-2\}\) so that \[a \equiv g^{k} \pmod p.\]
This integer \(k\) is called the index of \(a\) with respect to the primitive root \(g\), and is denoted by \(k=\operatorname{ind}_{g}(a)\).
If \(k_{1}, k_{2}\in\mathbb Z\) are such that \(k_{1} \leq k_{2}\) and \[a \equiv g^{k_{1}} \equiv g^{k_{2}} \pmod p,\] then \[g^{k_{2}-k_{1}} \equiv 1 \pmod p,\] and since \(g\) is a primitive root and \(\varphi(p)=p-1\), thus \[k_{1} \equiv k_{2} \pmod {p-1}.\]
If \(a \equiv g^{k} \pmod p\) and \(b \equiv g^{l} \pmod p\), then \[a b \equiv g^{k} g^{l}=g^{k+l} \pmod p\] and so \[\operatorname{ind}_{g}(a b) \equiv k+l \equiv \operatorname{ind}_{g}(a)+\operatorname{ind}_{g}(b) \pmod {p-1}.\]
The index map \(\operatorname{ind}_{g}\) is also called the discrete logarithm to the base \(g\) modulo \(p\).
For example, \(2\) is a primitive root modulo \(13\). Here is a table of \(\operatorname{ind}_{2}(a)\) for \(a\in[12]\):
| \(a\) | \(\operatorname{ind}_{2}(a)\) | \(a\) | \(\operatorname{ind}_{2}(a)\) |
|---|---|---|---|
| 1 | 0 | 7 | 11 |
| 2 | 1 | 8 | 3 |
| 3 | 4 | 9 | 8 |
| 4 | 2 | 10 | 10 |
| 5 | 9 | 11 | 7 |
| 6 | 5 | 12 | 6 |
By the structure theorem of subgroups in cyclic groups, if \(g\) is a primitive root modulo \(p\), then \(g^{k}\) is a primitive root iff \((k, p-1)=1\).
For example, for \(p=13\) there are \(\varphi(12)=4\) integers \(k\) such that \(0 \leq k \leq 11\) and \((k, 12)=1\), namely, \(k=1,5,7,11\), and so the four pairwise incongruent primitive roots modulo \(13\) are \[\begin{aligned} 2^{1} & \equiv 2 \pmod {13}, \\ 2^{5} & \equiv 6 \pmod {13}, \\ 2^{7} & \equiv 11 \pmod {13}, \\ 2^{11} & \equiv 7 \pmod {13}. \end{aligned}\]
Let \(a, k, m\in\mathbb Z\) be integers such that \(m \geq 2, k \geq 2\), and \((a, m)=1\). We say that \(a\) is a \(k\)-th power residue modulo \(m\) if there exists an \(x\in\mathbb Z\) such that \[x^{k} \equiv a \pmod m.\]
If this congruence has no solution, then \(a\) is called a \(k\)-th power nonresidue modulo \(m\).
Let \(k=2\) and \((a, m)=1\). If the congruence \(x^{2} \equiv a\pmod m\) is solvable, then \(a\) is called a quadratic residue modulo \(m\). Otherwise, \(a\) is called a quadratic nonresidue modulo \(m\).
For example, the quadratic residues modulo \(7\) are \(1,2\), and \(4\); the quadratic nonresidues are \(3,5\), and \(6\). The only quadratic residue modulo \(8\) is \(1\), and the quadratic nonresidues modulo \(8\) are \(3,5,4\) and \(7\).
Let \(k=3\) and \((a, m)=1\). If the congruence \(x^{3} \equiv a \pmod m\) is solvable, then \(a\) is called a cubic residue modulo \(m\). Otherwise, \(a\) is called a cubic nonresidue modulo \(m\).
For example, the cubic residues modulo \(7\) are \(1\) and \(6\); the cubic nonresidues are \(2,3,4\), and \(5\). The cubic residues modulo \(5\) are \(1,2,3\), and \(4\); there are no cubic nonresidues modulo \(5\).
Let \(p\in\mathbb P\) be a prime number, \(k \geq 2\), and \(d=(k, p-1)\). Let \(a\in\mathbb Z\) be not divisible by \(p\). Let \(g\) be a primitive root modulo \(p\).
Then \(a\) is a \(k\)-th power residue modulo \(p\) if and only if \[\operatorname{ind}_{g}(a) \equiv 0 \pmod d,\] if and only if \[a^{(p-1) / d} \equiv 1 \pmod p.\]
If \(a\) is a \(k\)-th power residue modulo \(p\), then the congruence \[\begin{align*} x^{k} \equiv a \pmod p \tag{*} \end{align*}\] has exactly \(d\) solutions that are pairwise incongruent modulo \(p\).
Moreover, there are exactly \((p-1) / d\) pairwise incongruent \(k\)-th power residues modulo \(p\).
Let \(l=\operatorname{ind}_{g}(a)\), where \(g\) is a primitive root modulo \(p\). Congruence (*) is solvable if and only if there exists \(y\in\mathbb Z\) such that \[g^{y} \equiv x \pmod p \quad \text{ and } \quad g^{k y} \equiv x^{k} \equiv a \equiv g^{l} \pmod p.\]
This is equivalent to \(k y \equiv l \pmod{ p-1}\), since \({\rm ord}_p(g)=p-1\).
This linear congruence in \(y\) has a solution if and only if \[\operatorname{ind}_{g}(a)=l \equiv 0 \pmod d, \quad \text{ where } \quad d=(k, p-1).\]
Thus, the \(k\)-th power residues modulo \(p\) are precisely the integers in the \((p-1) / d\) congruence classes \(g^{i d}+p \mathbb{Z}\) for \(i\in\{0,1, \ldots,(p-1)/d-1\}\).
Moreover, \[a^{(p-1) / d} \equiv g^{(p-1)l / d} \equiv 1 \pmod p\] if and only if \[\frac{(p-1) l}{d} \equiv 0 \pmod{ p-1} \quad \iff \quad \operatorname{ind}_{g}(a)=l \equiv 0 \pmod d\]
Finally, if the linear congruence \(k y \equiv l \pmod{ p-1}\) is solvable, then it has exactly \(d\) solutions \(y\) that are pairwise incongruent modulo \(p-1\), and so (*) has exactly \(d\) solutions \(x=g^{y}\) that are pairwise incongruent modulo \(p\). This completes the proof. $$\tag*{$\blacksquare$}$$
For example, let \(p=19\) and \(k=3\). Then \(d=(k, p-1)=(3,18)=3\).
We can check that \(2\) is a primitive root modulo \(19\), and so \(a\) is a cubic residue modulo \(19\) if and only if \(3\) divides \(\operatorname{ind}_{2}(a)\).
Since \(-1 \equiv 2^{9}\pmod 3\) and \(\operatorname{ind}_{2}(-1)=9\), it follows that \(-\)1 is a cubic residue modulo \(19\).
The solutions of the congruence \(x^{3} \equiv-1 \pmod {19}\) are of the form \(x \equiv 2^{y} \pmod {19}\), where \(0 \leq y \leq 17\) and \(3 y \equiv 9\pmod {18}\). Then \(y \equiv 3\pmod 6\), and so \(y=3,9\), and \(15\). These give the following three cube roots of \(-1\) modulo \(19\): \[\begin{gathered} 8 \equiv 2^{3} \pmod {19}, \\ 18 \equiv 2^{9} \pmod {19},\\ 12 \equiv 2^{15} \pmod {19}. \end{gathered}\]
Let \(p\in\mathbb P\) be an odd prime number, and let \(k \geq 2\) be an integer such that \((k, p-1)=1\). If \((a, p)=1\), then \(a\) is a \(k\)-th power residue modulo \(p\), and the congruence \(x^{k} \equiv a \pmod p\) has a unique solution modulo \(p\).
Let \(p\in\mathbb P\) be an odd prime and \(a\in\mathbb Z\) not divisible by \(p\). Then \(a\) is called a quadratic residue modulo \(p\) if there exists \(x\in\mathbb Z\) such that \[\begin{aligned} x^{2} \equiv a \pmod p. \qquad (*) \end{aligned}\]
If this congruence has no solution, then \(a\) is called a quadratic nonresidue modulo \(p\). Thus, an integer \(a\) is a quadratic residue modulo \(p\) if and only if \((a, p)=1\) and \(a\) has a square root modulo \(p\). By the previous theorem, exactly half the congruence classes relatively prime to \(p\) have square roots modulo \(p\).
We define the Legendre symbol for the odd prime \(p\) as follows: For any integer \(a\) we set \[\begin{aligned} (a\mid p)=\left\{\begin{aligned} 1 & \text { if }(a, p)=1 \text { and } a \text { is a quadratic residue modulo } p, \\ -1 & \text { if }(a, p)=1 \text { and } a \text { is a quadratic nonresidue modulo } p, \\ 0 & \text { if } p \text { divides } a .\end{aligned}\right. \end{aligned}\]
The solvability of congruence (*) depends only on the congruence class of \(a \pmod p\), that is, \[(a \mid p)=(b\mid p) \quad \text { if } \quad a \equiv b \pmod p,\] and so the Legendre symbol is a well-defined function on the congruence classes \(\mathbb{Z} / p \mathbb{Z}\).
We observe that if \(p\in\mathbb P\) is an odd prime, then, the only solutions of the congruence \(x^{2} \equiv 1 \pmod p\) are \(x \equiv \pm 1 \pmod p\).
If \(\varepsilon, \varepsilon^{\prime} \in\{-1,0,1\}\) and \(\varepsilon \equiv \varepsilon^{\prime}\pmod p\), then \(p\mid (\varepsilon-\varepsilon^{\prime})\), and so \(\varepsilon=\varepsilon^{\prime}\). In particular, if \((a\mid p) \equiv \varepsilon\pmod p\), then \((a\mid p) =\varepsilon\).
Let \(p\in\mathbb P\) be an odd prime. For every integer \(a\in\mathbb Z\), we have \[(a\mid p)\equiv a^{(p-1) / 2} \pmod p.\]
Proof.
If \(p\mid a\), then both sides of the congruence are \(0\).
If \(p\) does not divide \(a\), then, by Fermat’s theorem, we have \(\left(a^{(p-1) / 2}\right)^{2} \equiv a^{p-1} \equiv 1 \pmod p\) and so \(a^{(p-1) / 2} \equiv \pm 1 \pmod p\).
Applying the previous theorem with \(k=2\), we have \[a^{(p-1) / 2} \equiv 1 \pmod p \quad \text { if and only if } \quad (a\mid p)=1,\] and consequently we must have \[a^{(p-1) / 2} \equiv-1 \pmod p \quad \text { if and only if } \quad(a\mid p)=-1.\]
This completes the proof.$$\tag*{$\blacksquare$}$$
Let \(p\in \mathbb P\) be an odd prime, and let \(a, b\in\mathbb Z\). Then \((ab\mid p)=(a\mid p)(b\mid p).\)
Proof.
If \(p\) divides \(a\) or \(b\), then \(p\) divides \(a b\), and \[(ab\mid p)=0=(a\mid p)(b\mid p).\]
If \(p\) does not divide \(a b\), then, by the previous theorem, we obtian \[\begin{aligned} (ab\mid p) & \equiv(a b)^{(p-1) / 2} \pmod p \\ & \equiv a^{(p-1) / 2} b^{(p-1) / 2} \pmod p \\ & (a\mid p)(b\mid p) \pmod p. \end{aligned}\]
The result follows immediately from the observation that each side of this congruence is \(\pm 1\). See the remark before the previous theorem.
This completes the proof of the theorem.$$\tag*{$\blacksquare$}$$
Previous theorem implies that the Legendre symbol \((\cdot \mid p)\) is completely determined by its values at \(-1,2\), and odd primes \(q\).
If \(a\) is an integer not divisible by \(p\), then we can write \[a= \pm 2^{r_{0}} q_{1}^{r_{1}} q_{2}^{r_{2}} \cdots q_{k}^{r_{k}},\] where \(q_{1}, \ldots, q_{k}\) are distinct odd primes not equal to \(p\). Then \[(a\mid p)=(\pm 1 \mid p)(2\mid p)^{r_{0}}(q_1\mid p)^{r_{1}} \cdots(q_k\mid p)^{r_{k}}.\]
Let \(p\in\mathbb P\) be an odd prime number. Then \[\begin{aligned} (- 1 \mid p)=\left\{\begin{array}{rll} 1 & \text { if } & p \equiv 1 \pmod 4, \\ -1 & \text { if } & p \equiv 3 \pmod 4. \end{array}\right. \end{aligned}\] Equivalently, \[(- 1 \mid p)=(-1)^{(p-1) / 2}.\]
Proof.
We observe that \[(-1)^{(p-1) / 2}=\left\{\begin{array}{rlll} 1 & \text { if } & p \equiv 1 & \pmod 4, \\ -1 & \text { if } & p \equiv 3 & \pmod 4. \end{array}\right.\]
By the previous theorem with \(a=-1\), we obtain \[(- 1 \mid p) \equiv(-1)^{(p-1) / 2} \pmod p.\]
This completes the proof, since both sides of this congruence are \(\pm 1\).$$\tag*{$\blacksquare$}$$
Let \(p\in\mathbb P\) be an odd prime. Then \[(2\mid p)= \begin{cases} 1 & \text { if } p \equiv \pm 1 \pmod 8, \\ -1 & \text { if } p \equiv \pm 3 \pmod 8. \end{cases}\] Equivalently, \[(2\mid p)=(-1)^{(p^{2}-1) / 8}.\]
Consider the following congruences: \[\begin{aligned} p - 1 &\equiv 1(-1)^1 \pmod p,\\ 2 &\equiv 2(-1)^2 \pmod p,\\ p - 3 &\equiv 3(-1)^3\pmod p,\\ 4 &\equiv 4(-1)^4 \pmod p,\\ &\ \ \vdots\\ r&\equiv \frac{p-1}{2}(-1)^{\frac{p-1}{2}} \pmod p, \end{aligned}\] where \(r=p-\frac{p-1}{2}\) or \(r=\frac{p-1}{2}\).
Multiply both sides by each integer on the left, which is even. Then \[\begin{aligned} 2\cdot 4\cdot 6\cdots (p-1)\equiv \bigg(\frac{p-1}{2}\bigg)!(-1)^{1+2+\ldots+\frac{(p-1)}{2}} \pmod p, \end{aligned}\] or equivalently \(2^\frac{p-1}{2}\big(\frac{p-1}{2}\big)!\equiv \big(\frac{p-1}{2}\big)!(-1)^{\frac{(p^2-1)}{8}} \pmod p.\)
Since \(\big(\frac{p-1}{2}\big)!\not\equiv0\pmod p\) we obtain \(2^\frac{p-1}{2}\equiv (-1)^{\frac{(p^2-1)}{8}} \pmod p\)
By Euler’s criterion, \((2\mid p)=2^\frac{p-1}{2}\equiv (-1)^{\frac{(p^2-1)}{8}} \pmod p\) as desired. $$\tag*{$\blacksquare$}$$
Let \(p\in\mathbb P\) be an odd prime, and let \(S\) be a set of \((p-1) / 2\) integers. We call \(S\) a Gaussian set modulo \(p\) if \(S \cup-S=S \cup\{-s: s \in S\}\) is a reduced system of residues modulo \(p\).
Equivalently, \(S\) is a Gaussian set if for every integer \(a\) not divisible by \(p\), there exist unique \(s \in S\) and \(\varepsilon \in\{1,-1\}\) such that \(a \equiv \varepsilon s \pmod p\).
For example, the sets \(\{1,2, \ldots,(p-1) / 2\}\) and \(\{2,4,6, \ldots, p-1\}\) are Gaussian sets modulo \(p\) for every odd prime \(p\in\mathbb P\).
If \(S\) is a Gaussian set, \(s, s^{\prime} \in S\), and \(s \equiv \pm s^{\prime} \pmod p\), then \(s=s^{\prime}\).
Let \(p\in \mathbb P\) be an odd prime, and let \(a\in\mathbb Z\) be not divisible by \(p\). Let \(S\) be a Gaussian set modulo \(p\). For every \(s \in S\) there exist unique integers \(u_{a}(s) \in S\) and \(\varepsilon_{a}(s) \in\{1,-1\}\) such that \[a s \equiv \varepsilon_{a}(s) u_{a}(s) \pmod p.\]
Moreover, \[(a\mid p)=\prod_{s \in S} \varepsilon_{a}(s)=(-1)^{m},\] where \(m\) is the number of \(s \in S\) such that \(\varepsilon_{a}(s)=-1\).
Since \(S\) is a Gaussian set, for every \(s \in S\) there exist unique integers \(u_{a}(s) \in S\) and \(\varepsilon_{a}(s) \in\{1,-1\}\) such that \(a s \equiv \varepsilon_{a}(s) u_{a}(s) \pmod p.\)
We show that \(s\mapsto u_{a}(s)\) is one-to-one. Indeed, if \(u_{a}(s)=u_{a}\left(s^{\prime}\right)\) for some \(s, s^{\prime} \in S\), then \[\begin{aligned} a s^{\prime} & \equiv \varepsilon_{a}\left(s^{\prime}\right) u_{a}\left(s^{\prime}\right) \equiv \varepsilon_{a}\left(s^{\prime}\right) u_{a}(s) \pmod p \\ & \equiv \varepsilon_{a}\left(s^{\prime}\right) \varepsilon_{a}(s) \varepsilon_{a}(s) u_{a}(s) \pmod p \equiv \pm a s \pmod p. \end{aligned}\]
Dividing by \(a\), we obtain \(s^{\prime} \equiv \pm s \pmod p\) and so \(s^{\prime}=s\). It follows that the map \(u_{a}: S \rightarrow S\) is a permutation of \(S\), and so \(\prod_{s \in S} s=\prod_{s \in S} u_{a}(s)\).
Therefore, \[\begin{aligned} a^{(p-1) / 2} \prod_{s \in S} s & \equiv \prod_{s \in S} a s \pmod p \equiv \prod_{s \in S} \varepsilon_{a}(s) u_{a}(s) \pmod p \\ & \equiv \prod_{s \in S} \varepsilon_{a}(s) \prod_{s \in S} u_{a}(s) \pmod p \\ & \equiv \prod_{s \in S} \varepsilon_{a}(s) \prod_{s \in S} s \pmod p \end{aligned}\]
Dividing by \(\prod_{s \in S} s\), the proof follows, as we obtain \[(a\mid p) \equiv a^{(p-1) / 2} \equiv \prod_{s \in S} \varepsilon_{a}(s) \pmod p. \qquad \tag*{$\blacksquare$}\]
We shall use Gauss’s lemma to compute the Legendre symbol \((3\mid 11)\).
Let \(S\) be the Gaussian set \(\{2,4,6,8,10\}\). We have \[\begin{aligned} 3 \cdot 2 & \equiv 6 \pmod {11}, \\ 3 \cdot 4 & \equiv(-1) 10 \pmod {11}, \\ 3 \cdot 6 & \equiv(-1) 4 \pmod {11}, \\ 3 \cdot 8 & \equiv 2 \pmod {11}, \\ 3 \cdot 10 & \equiv 8 \pmod {11}. \end{aligned}\]
The number of \(s \in S\) with \(\varepsilon_{3}(s)=-1\) is \(m=2\), and so \[(3\mid 11)=(-1)^{2}=1,\] that is, \(3\) is a quadratic residue modulo \(11\).
There are exactly two incongruent solutions of \(x^2\equiv 3 \pmod{11}\), namely \[5^{2} \equiv 6^{2} \equiv 3 \pmod {11}.\] and so \(5\) and \(6\) are the square roots of \(3\) modulo \(11\).
Let \(\mathbb G\) be a finite abelian group, written additively, and let \(A_{1}, \ldots, A_{k}\subseteq \mathbb G\). The sum of these sets is the set \[A_{1}+\cdots+A_{k}=\left\{a_{1}+\cdots+a_{k}: a_{i} \in A_{i} \text { for } i\in[k]\right\}.\]
If \(\mathbb G_{1}, \ldots, \mathbb G_{k}\) are subgroups of \(\mathbb G\), then the sumset \(\mathbb G_{1}+\cdots+\mathbb G_{k}\) is a subgroup of \(\mathbb G\).
We say that \(\mathbb G\) is the direct sum of the subgroups \(\mathbb G_{1}, \ldots, \mathbb G_{k}\), written \(\mathbb G=\mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}\), if every element \(g \in \mathbb G\) can be written uniquely in the form \(g=g_{1}+\cdots+g_{k}\), where \(g_{i} \in \mathbb G_{i}\) for \(i\in [k]\).
If \(\mathbb G=\mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}\), then \(|\mathbb G|=\left|\mathbb G_{1}\right| \cdots\left|\mathbb G_{k}\right|\).
The order of an element \(g\) in an additive group is the smallest positive integer \(d\in\mathbb Z_+\) such that \(d g=0\). We know that \(d\) divides \(|\mathbb G|\).
Let \(p\in\mathbb P\) be a prime number. A \(p\)-group is a group each of whose elements has an order that is a power of \(p\).
For every prime number \(p\in\mathbb P\), let \[\mathbb G(p):=\{g\in\mathbb G: {\rm ord}_{\mathbb G}(g)=p^l\text{ for some } l\in\mathbb Z_+\}.\] Then \(\mathbb G(p)\) is a subgroup of the abelian group \(\mathbb G\).
Every finite abelian group is a direct sum of cyclic groups.
This result will be a consequence of the next two theorems.
Let \(\mathbb G\) be a finite abelian group, written additively, and let \(|\mathbb G|=m\). For every prime number \(p\in\mathbb P\), let \(\mathbb G(p)\) be the set of all elements \(g \in \mathbb G\) whose order is a power of \(p\). Then \[\mathbb G=\bigoplus_{p \mid m} \mathbb G(p).\]
Proof.
Let \(m=\prod_{i\in[k]} p_{i}^{r_{i}}\), and define \(m_{i}=m p_{i}^{-r_{i}}\) for \(i\in [k]\).
Then \(\left(m_{1}, \ldots, m_{k}\right)=1\), and by the GCD theorem there exist \(u_{1}, \ldots, u_{k}\in\mathbb Z\) such that \(m_{1} u_{1}+\cdots+m_{k} u_{k}=1\).
Let \(g \in \mathbb G\), and
define \(g_{i}=m_{i} u_{i} g \in \mathbb
G\) for \(i\in [k]\). Since
\(p_{i}^{r_{i}} g_{i}=m u_{i} g=0\), it
follows that \(g_{i} \in \mathbb
G(p_i)\). Moreover, \[\begin{aligned}
g & =\left(m_{1} u_{1}+\cdots+m_{k} u_{k}\right) g=m_{1} u_{1}
g+\cdots+m_{k} u_{k} g \\
& =g_{1}+\cdots+g_{k} \in \mathbb G\left(p_{1}\right)+\cdots+\mathbb
G\left(p_{k}\right).
\end{aligned}\]
Thus we have proved that \(\mathbb G=\mathbb G\left(p_{1}\right)+\cdots+\mathbb G\left(p_{k}\right).\)
Suppose that \[g_{1}+\cdots+g_{k}=0,\] where \(g_{i} \in \mathbb G\left(p_{i}\right)\) for \(i\in [k]\).
There exist \(r_{1}, \ldots, r_{k}\in\mathbb N\) such that \(g_{i}\) has order \(p_{i}^{r_{i}}\) for \(i\in [k]\). Let \[d_{j}=\prod_{\substack{i\in[k] \\ i \neq j}} p_{i}^{r_{i}}.\]
Since \(d_{j} g_{i}=0\) for \(i\in[k]\) with \(i \neq j\), it follows that \[0=d_{j}\left(g_{1}+\cdots+g_{k}\right)=d_{j} g_{j}.\]
We proved that \(d_{j} g_{j} = 0\) for all \(j\in[k]\), thus \(p_{j}^{r_{j}}\mid d_j\), but \((p_{j}^{r_{j}}, d_j)=1\), which is only possible when \(r_{1}= \ldots= r_{k}=0\)
Hence, \(g_{j}=0\) for all \(j\in [k]\).
Thus, \(0\) has no nontrivial representation in \(\mathbb G=\mathbb G\left(p_{1}\right)+\cdots+\mathbb G\left(p_{k}\right)\).
We conclude that \(\mathbb G\) is the direct sum of the subgroups \(\mathbb G\left(p_{i}\right)\).$$\tag*{$\blacksquare$}$$
Let \(\mathbb G\) be a finite abelian p-group. Let \(g_{1} \in \mathbb G\) be an element of maximum order \(p^{r_{1}}\), and let \(\mathbb G_{1}=\left\langle g_{1}\right\rangle\) be the cyclic subgroup generated by \(g_{1}\). Let \(h \in \mathbb G\) and suppose that \(h+\mathbb G_{1} \in \mathbb G / \mathbb G_{1}\) has order \(p^{r}\), then there exists an element \(g \in \mathbb G\) such that \(g+\mathbb G_{1}=h+\mathbb G_{1}\) and \(g\) has order \(p^{r}\) in \(\mathbb G\).
Proof.
If \(h+\mathbb G_{1}\) has order \(p^{r}\) in \(\mathbb G / \mathbb G_{1}\), then the order of \(h\) in \(\mathbb G\) is at most \(p^{r_{1}}\) (since \(p^{r_{1}}\) is the maximum order in \(\mathbb G\)) and at least \(p^{r}\).
Since \(\mathbb G_{1}=p^{r}\left(h+\mathbb G_{1}\right)=p^{r} h+\mathbb G_{1}\), it follows that \(p^{r} h \in \mathbb G_{1}\), and so \(p^{r} h=u g_{1}\) for some positive integer \(u \leq p^{r_{1}}\) (since \(g_{1}\) has order \(p^{r_{1}}\)).
Write \(u=p^{s} v\), where \((p, v)=1\) and \(0 \leq s \leq r_{1}\). Then \(v g_{1}\) also has order \(p^{r_{1}}\), and so \(p^{s} v g_{1}\) has order \(p^{r_{1}-s}\) in \(\mathbb G\). Then \(p^{r} h=p^{s} v g_{1}\) has order \(p^{r_{1}-s}\) in \(\mathbb G\), and so \(h\) has order \(p^{r_{1}+r-s} \leq p^{r_{1}}\). It follows that \(r \leq s\), and \[p^{r} h=p^{s} v g_{1}=p^{r}\left(p^{s-r} v g_{1}\right)=p^{r} g_{1}^{\prime},\] where \(g_{1}^{\prime}=p^{s-r} v g_{1} \in \mathbb G_{1}\). Taking \(g=h-g_{1}^{\prime}\), we see \(g+\mathbb G_{1}=h+\mathbb G_{1}\).
Moreover, \(p^{r} g=p^{r} h-p^{r} g_{1}^{\prime}=0\), and so the order of \(g\) is at most \(p^{r}\). On the other hand, \(g+\mathbb G_{1}\) has order \(p^{r}\) in the quotient group \(\mathbb G / \mathbb G_{1}\), and so the order of \(g\) is at least \(p^{r}\). Therefore, \(g\) has order \(p^{r}\) as desired. $$\tag*{$\blacksquare$}$$
Every finite abelian \(p\)-group is a direct sum of cyclic groups.
Proof.
The proof is by induction on the cardinality of \(\mathbb G\). Let \(\mathbb G\) be a finite abelian \(p\)-group. If \(\mathbb G\) is cyclic, we are done. If \(\mathbb G\) is not cyclic, let \(g_{1} \in \mathbb G\) be an element of maximum order \(p^{r_{1}}\), and let \(\mathbb G_{1}:=\langle g_1\rangle\).
The quotient group \(\mathbb G / \mathbb G_{1}\) is a finite abelian \(p\)-group, and \[1<\left|\mathbb G / \mathbb G_{1}\right|=\frac{|\mathbb G|}{p^{r_{1}}}<|\mathbb G|\]
Therefore, the induction hypothesis holds for \(\mathbb G / \mathbb G_{1}\), and so \[\mathbb G / \mathbb G_{1}=\mathbb H_{2} \oplus \cdots \oplus \mathbb H_{k}\] where \(\mathbb H_{i}\) is a cyclic subgroup of \(\mathbb G / \mathbb G_{1}\) of order \(p^{r_{i}}\) for \(i\in[k]\setminus\{1\}\).
Moreover, \[\frac{|\mathbb G|}{p^{r_{1}}}=\left|\mathbb G / \mathbb G_{1}\right|=\prod_{i=2}^{k} p^{r_{i}}\]
By the previous lemma, for each \(i\in[k]\setminus\{1\}\) there exists \(g_{i} \in \mathbb G\) such that \(g_{i}+\mathbb G_{1}\) generates \(\mathbb H_{i}\) and \({\rm ord}_{\mathbb G}(g_{i})=p^{r_{i}}\). Let \(\mathbb G_{i}:=\langle g_i\rangle\).
Then \(\left|\mathbb G_{i}\right|=p^{r_{i}}\) for \(i\in [k]\). We shall prove that \(\mathbb G=\mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}\).
We begin by showing that \(\mathbb G=\mathbb G_{1}+\cdots+\mathbb G_{k}\). If \(g \in \mathbb G\), then \(g+\mathbb G_{1} \in\) \(\mathbb G / \mathbb G_{1}\), and there exist \(u_{2}, \ldots, u_{k}\in\mathbb Z\) such that \(0 \leq u_{i} \leq p^{r_{i}}-1\) for each \(i\in[k]\setminus\{1\}\), and \[g+\mathbb G_{1}=u_{2}\left(g_{2}+\mathbb G_{1}\right) \oplus \cdots \oplus u_{k}\left(g_{k}+\mathbb G_{1}\right)=\left(u_{2} g_{2}+\cdots+u_{k} g_{k}\right)+\mathbb G_{1}.\]
It follows that we can find \(u_{1}\in\mathbb Z\) such that \(0 \leq u_{1} \leq p^{r_{1}}-1\) and \[g-\left(u_{2} g_{2}+\cdots+u_{k} g_{k}\right)=u_{1} g_{1} \in \mathbb G_{1},\] and so \[g=u_{1} g_{1}+u_{2} g_{2}+\cdots+u_{k} g_{k} \in \mathbb G_{1}+\cdots+\mathbb G_{k}.\]
Therefore, \(\mathbb G=\mathbb G_{1}+\cdots+\mathbb G_{k}\). Since \[|\mathbb G|=\left|\mathbb G_{1}+\cdots+\mathbb G_{k}\right| \leq\left|\mathbb G_{1}\right| \cdots\left|\mathbb G_{k}\right|=\prod_{i=1}^{k} p^{r_{i}}=|\mathbb G|\] it follows that every element of \(\mathbb G\) has a unique representation as an element in the sumset \(\mathbb G_{1}+\cdots+\mathbb G_{k}\), and so \(\mathbb G=\mathbb G_{1} \oplus+\cdots+\oplus \mathbb G_{k}\).
This completes the proof. $$\tag*{$\blacksquare$}$$
Let \(\mathbb G\) be a finite abelian group, written additively. A group character is a homomorphism \(\chi: \mathbb G \rightarrow \mathbb{C}^{\times}\), where \(\mathbb{C}^{\times}\)is the multiplicative group of nonzero complex numbers.
Then \(\chi(0)=1\) and \(\chi\left(g_{1}+g_{2}\right)=\chi\left(g_{1}\right) \chi\left(g_{2}\right)\) for all \(g_{1}, g_{2} \in \mathbb G\).
If \(\chi\) is a character of a multiplicative group \(\mathbb G\), then \(\chi(1)=1\) and \(\chi\left(g_{1} g_{2}\right)=\chi\left(g_{1}\right) \chi\left(g_{2}\right)\) for all \(g_{1}, g_{2} \in \mathbb G\).
We define the character \(\chi_{0}\) on \(\mathbb G\) by \(\chi_{0}(g)=1\) for all \(g \in \mathbb G\). If \(\mathbb G\) is an additive group of order \(n\) and if \(g \in \mathbb G\) has order \(d\), then \[\chi(g)^{d}=\chi(d g)=\chi(0)=1,\] and so \(\chi(g)\) is a \(d\)-th root of unity, and also \(\chi(g)\) is an \(n\)-th root of unity for every \(g \in \mathbb G\), since \(d\mid n\). Hence, we have \(|\chi(g)|=1\) for all \(g \in \mathbb G\).
We define the product of two characters \(\chi_{1}\) and \(\chi_{2}\) by \[\chi_{1} \chi_{2}(g)=\chi_{1}(g) \chi_{2}(g) \quad \text{ for all } \quad g \in \mathbb G.\] In is not difficult to see that this product is associative and commutative.
The character \(\chi_{0}\) is a multiplicative identity, since \[\chi_{0} \chi(g)=\chi_{0}(g) \chi(g)=\chi(g)\] for every character \(\chi\) and \(g \in \mathbb G\).
The inverse of the character \(\chi\) is the character \(\chi^{-1}\) defined by \[\chi^{-1}(g)=\chi(-g),\] and indeed we have \(\chi \chi^{-1}=\chi_{0}\), since \[\begin{aligned} \chi \chi^{-1}(g) & =\chi(g) \chi^{-1}(g)=\chi(g) \chi(-g) \\ & =\chi(g-g)=\chi(0)=1 \\ & =\chi_{0}(g). \end{aligned}\]
The complex conjugate of a character \(\chi\) is the character \(\bar{\chi}\) defined by \[\overline{\chi}(g)=\overline{\chi(g)} .\]
Since \(|\chi(g)|=1\) for all \(g \in \mathbb G\), we have \[\chi \overline{\chi}(g)=\chi(g) \overline{\chi}(g)=|\chi(g)|^{2}=1=\chi_{0}(g),\] and so for every character \(\chi\) and all \(g \in \mathbb G\) we have \[\chi^{-1}(g)=\overline{\chi}(g).\]
It follows that the set \(\widehat{\mathbb G}\) of all characters of a finite abelian group \(\mathbb G\) is an abelian group, called the dual group or character group of \(\mathbb G\).
We prove that \(\mathbb G\) is isomorphic to \(\widehat{\mathbb G}\) for every finite abelian group \(\mathbb G\).
The dual of a cyclic group of order \(n\) is also a cyclic group of order \(n\).
Proof.
Recall that \(e(x)=e^{2 \pi i x}\) for any \(x\in\mathbb R\) and we will write \(e_{n}(x)=e(x / n)\).
The \(n\)th roots of unity are the complex numbers \(1, e_{n}(1), \ldots, e_{n}(n-1)\).
Let \(\mathbb G=\{j g_{0}: j\in \mathbb N_{<n}\}\) be a cyclic group of order \(n\) with generator \(g_{0}\).
For every \(a\in \mathbb Z\), we define \(\psi_{a} \in \widehat{\mathbb G}\) by \(\psi_{a}\left(j g_{0}\right):=e_{n}(a j).\)
We can easily verify that \(\psi_{a} \psi_{b}=\psi_{a+b}\), and \(\psi_{a}^{-1}=\psi_{-a}\), and \(\psi_{a}=\psi_{b}\) if and only if \(a \equiv b \pmod n\). It follows that \(\psi_{a}=\psi_{1}^{a}\) for any \(a\in\mathbb Z\).
If \(\chi\in\widehat{\mathbb G}\), then \(\chi\) is completely determined by its value on \(g_{0}\). Since \(\chi\left(g_{0}\right)\) is an \(n\)-th root of unity, we have \(\chi\left(g_{0}\right)=e_{n}(a)\) for some \(a\in\mathbb N_{<n}\), and so \(\chi\left(j g_{0}\right)=e_{n}(a j)\) for all \(j\in\mathbb Z\). Thus, \(\chi=\psi_{a}\) and
\[\widehat{\mathbb G}=\left\{\psi_{a}: a\in\mathbb N_{<n}\right\}=\left\{\psi_{1}^{a}: a\in\mathbb N_{<n}\right\}\] is also a cyclic group of order \(n\), and the map \(\mathbb G\ni a\mapsto \psi_q \in \widehat{\mathbb G}\) defines the isomorphism between \(\mathbb G\) and \(\widehat{\mathbb G}\).
It is a simple but critical observation that if \(g\) is a nonzero element of a cyclic group \(\mathbb G\), then \(\psi_{1}(g) \neq 1\).
$$\tag*{$\blacksquare$}$$
Let \(\mathbb G\) be a finite abelian group and let \(\mathbb G_{1}, \ldots, \mathbb G_{k}\) be subgroups of \(\mathbb G\) such that \(\mathbb G=\mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}\). For every character \(\chi \in \widehat{\mathbb G}\) there exist unique characters \(\chi_{i} \in \widehat{\mathbb G_{i}}\) such that if \(g \in \mathbb G\) and \(g=g_{1}+\cdots+g_{k}\) with \(g_{i} \in \mathbb G_{i}\) for \(i\in [k]\), then \[\chi(g)=\chi_{1}\left(g_{1}\right) \cdots \chi_{k}\left(g_{k}\right). \tag{*}\] Moreover, \(\widehat{\mathbb G}\) and \(\widehat{\mathbb G_{1}} \times \cdots \times \widehat{\mathbb G_{k}}\) are isomorphic.
Proof.
If \(\chi_{i} \in \widehat{\mathbb G_{i}}\) for \(i\in[k]\), then we can construct a map \(\chi: \mathbb G \rightarrow\mathbb{C}^{\times}\) as follows. For each \(g \in \mathbb G\) there exist unique elements \(g_{i} \in \mathbb G_{i}\) such that \(g=g_{1}+\cdots+g_{k}\). Define \[\begin{aligned} \chi(g)=\chi\left(g_{1}+\cdots+g_{k}\right)=\chi_{1}\left(g_{1}\right) \cdots \chi_{k}\left(g_{k}\right). \qquad (**) \end{aligned}\]
Then \(\chi\) is a character in \(\widehat{\mathbb G}\), and this construction induces a map \[\Psi: \widehat{\mathbb G_{1}} \times \cdots \times \widehat{\mathbb G_{k}} \rightarrow \widehat{\mathbb G},\] defined by \(\Psi(\chi_1, \ldots, \chi_k):=\chi\), where \(\chi\) is given as in (**).
If is easy to see that \(\Psi\) is a one-to-one homomorphism. Indeed, if \((\chi_1, \ldots, \chi_k)\neq (\chi_1', \ldots, \chi_k')\), then without loss of generality we can assume that \(\chi_1\neq \chi_1'\). This means that there exists \(g_1\in\mathbb G_1\) such that \(\chi_1(g_1)\neq \chi_1'(g_1)\). It suffices to take \(g=g_1+0+\ldots+0\) to see that \(\Psi(\chi_1, \ldots, \chi_k)(g)=\chi_1(g_1)\neq \chi_1'(g_1)=\Psi(\chi_1', \ldots, \chi_k')(g)\).
We shall show that the \(\operatorname{map} \Psi\) is onto. Let \(\chi \in \widehat{\mathbb G}\). We define the function \(\chi_{i}\) on \(\mathbb G_{i}\) by \[\chi_{i}\left(g_{i}\right)=\chi\left(g_{i}\right) \quad \text { for all } \quad g_{i} \in \mathbb G_{i}.\]
Then \(\chi_{i}\) is a character in \(\widehat{\mathbb G_{i}}\). If \(g \in \mathbb G\) and \(g=g_{1}+\cdots+g_{k}\) with \(g_{i} \in \mathbb G_{i}\), then \[\chi(g)=\chi\left(g_{1}+\cdots+g_{k}\right)=\chi\left(g_{1}\right) \cdots \chi\left(g_{k}\right)=\chi_{1}\left(g_{1}\right) \cdots \chi_{k}\left(g_{k}\right).\]
It follows that \[\Psi\left(\chi_{1}, \ldots, \chi_{k}\right)=\chi\] and so \(\Psi\) is onto. $$\tag*{$\blacksquare$}$$
Let \(\mathbb G\) be a finite abelian group. If \(0\neq g\in\mathbb G\), then there is \(\chi \in \widehat{\mathbb G}\) so that \(\chi(g) \neq 1\).
Proof.
We write \(\mathbb G=\mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}\) as a direct product of cyclic groups.
If \(g \neq 0\), then there exist \(g_{1} \in \mathbb G_{1}, \ldots, g_{k} \in \mathbb G_{k}\) such that \(g=g_{1}+\cdots+g_{k}\), and \(g_{j} \neq 0\) for some \(j\in[k]\).
Since the group \(\mathbb G_{j}\) is cyclic, there is \(\chi_{j} \in \widehat{\mathbb G_{j}}\) such that \(\chi_{j}\left(g_{j}\right) \neq 1\). For \(i\in [k]\setminus \{j\}\), let \(\chi_{i} \in \widehat{\mathbb G_{i}}\) be the character defined by \(\chi_{i}\left(g_{1}\right)=1\) for all \(g_{i} \in \mathbb G_{i}\). If \(\chi=\Psi\left(\chi_{1}, \ldots, \chi_{k}\right) \in \widehat{\mathbb G}\), then \(\chi(g)=\chi_{j}\left(g_{j}\right) \neq 1\).
This completes the proof of the theorem.$$\tag*{$\blacksquare$}$$
A finite abelian group \(\mathbb G\) is isomorphic to its dual, that is, \(\mathbb G \equiv \widehat{\mathbb G}\).
Proof.
We know the dual of a finite cyclic group of order \(n\) is also a finite cyclic group of order \(n\). We also know that a finite abelian group \(\mathbb G\) has cyclic subgroups \(\mathbb G_{1}, \ldots, \mathbb G_{k}\) such that \(\mathbb G=\mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}\). Finally we see that \[\widehat{\mathbb G} \equiv \widehat{\mathbb G_{1}} \times \cdots \times \widehat{\mathbb G_{k}} \equiv \mathbb G_{1} \times \cdots \times \mathbb G_{k} \equiv \mathbb G_{1} \oplus \cdots \oplus \mathbb G_{k}=\mathbb G. \] This completes the proof.
$$\tag*{$\blacksquare$}$$
Let \(\mathbb G\) be a finite abelian group of order \(n\), and \(\Gamma_n\) be the group of \(n\)th roots of unity. There is a pairing map \(\langle \cdot , \cdot \rangle: \mathbb G \times \widehat{\mathbb G}\to \Gamma_n\) defined by \[\langle a, \chi\rangle=\chi(a).\]
This map is nondegenerate in the sense that:
\(\langle a, \chi\rangle=1\) for all group elements \(a \in \mathbb G\) if and only if \(\chi=\chi_{0}\);
\(\langle a, \chi\rangle=1\) for all characters \(\chi \in \widehat{\mathbb G}\) if and only if \(a=0\) by the separation points property.
For each \(a \in \mathbb G\), the function \(\langle a, \cdot \rangle\) is a character of the dual group \(\widehat{\mathbb G}\), that is, \(\langle a,\cdot \rangle \in \widehat{\widehat{\mathbb G}}\). The map \(\Delta: \mathbb G \rightarrow \widehat{\widehat{\mathbb G}}\) defined by \(a \mapsto\langle a, \cdot \rangle\) or, equivalently, \[\Delta(a)(\chi)=\langle a, \chi\rangle=\chi(a),\] is a homomorphism of the group \(\mathbb G\) into its double dual \(\widehat{\widehat{\mathbb G}}\).
Since the pairing is nondegenerate, this homomorphism is one-to-one.
Since \(|\mathbb G|=|\widehat{\mathbb G}|=|\widehat{\widehat{\mathbb G}}|\), it follows that \(\Delta\) is a natural isomorphism of \(\mathbb G\) onto \(\widehat{\widehat{\mathbb G}}\).
Let \(\mathbb G\) be a finite abelian group of order \(n\), and let \(\widehat{\mathbb G}\) be its dual group.
If \(\chi \in \widehat{\mathbb G}\), then \[\sum_{a \in \mathbb G} \chi(a)= \begin{cases} n & \text { if } \chi=\chi_{0},\\ 0 & \text { if } \chi \neq \chi_{0}. \end{cases}\]
If \(a \in \mathbb G\), then \[\sum_{\chi \in \widehat{\mathbb G}} \chi(a)= \begin{cases} n & \text { if } a=0, \\ 0 & \text { if } a \neq 0. \end{cases}\]
Proof.
For \(\chi \in \widehat{\mathbb G}\), let \[S(\chi)=\sum_{a \in \mathbb G} \chi(a).\]
If \(\chi=\chi_{0}\), then \(S\left(\chi_{0}\right)=|\mathbb G|=n\). If \(\chi \neq \chi_{0}\), then \(\chi(b) \neq 1\) for some \(b \in \mathbb G\), and so \(S(\chi)=0\), since \[\begin{aligned} \chi(b) S(\chi) =\chi(b) \sum_{a \in \mathbb G} \chi(a) =\sum_{a \in \mathbb G} \chi(b a) =\sum_{a \in \mathbb G} \chi(a) =S(\chi). \end{aligned}\]
For \(a \in \mathbb G\), let \[T(a)=\sum_{\chi \in \widehat{\mathbb G}} \chi(a)\]
If \(a=0\), then \(T(a)=|\widehat{\mathbb G}|=n\). If \(a \neq 0\), then \(\chi^{\prime}(a) \neq 1\) for some \(\chi^{\prime} \in \widehat{\mathbb G}\) (by the separation point property), hence \[\begin{aligned} \chi^{\prime}(a) T(a) & =\chi^{\prime}(a) \sum_{\chi \in \widehat{\mathbb G}} \chi(a) \\ & =\sum_{\chi \in \widehat{\mathbb G}} \chi^{\prime} \chi(a) \\ & =\sum_{\chi \in \widehat{\mathbb G}} \chi(a) \\ & =T(a) \end{aligned}\] and so \(T(a)=0\). This completes the proof. $$\tag*{$\blacksquare$}$$
Let \(\mathbb G\) be a finite abelian group of order \(n\), and let \(\widehat{\mathbb G}\) be its dual group.
If \(\chi_{1}, \chi_{2} \in \widehat{\mathbb G}\), then \[\sum_{a \in \mathbb G} \chi_{1}(a) \overline{\chi_{2}}(a) = \begin{cases} n & \text { if } \chi_{1}=\chi_{2}, \\ 0 & \text { if } \chi_{1} \neq \chi_{2}. \end{cases}\]
If \(a, b \in \mathbb G\), then \[\sum_{\chi \in \widehat{\mathbb G}} \chi(a) \overline{\chi}(b) = \begin{cases} n & \text { if } a=b, \\ 0 & \text { if } a \neq b. \end{cases}\]
Proof.
These identities follow immediately from the previous theorem, since \[\chi_{1}(a) \overline{\chi_{2}}(a)=\chi_{1} \chi_{2}^{-1}(a), \quad \text{ and } \quad \chi(a) \overline{\chi}(b)=\chi(a-b).\]
This completes the proof.$$\tag*{$\blacksquare$}$$
The character table for a group has one column for each element of the group and one row for each character of the group.
For example, if \(C_{4}\) is the cyclic group of order \(4\) with generator \(g_{0}\), then the characters of \(C_{4}\) are the functions \[\psi_{a}\left(j g_{0}\right)=e_{4}(a j)=i^{a j}\] for \(a\in \{0,1,2,3\}\), and the character table is the following: \[\begin{aligned} \begin{array}{|l|l|r|r|r|} \hline & 0 & g_{0} & 2 g_{0} & 3 g_{0} \\ \hline \psi_{0} & 1 & 1 & 1 & 1 \\ \hline \psi_{1} & 1 & i & -1 & -i \\ \hline \psi_{2} & 1 & -1 & 1 & -1 \\ \hline \psi_{3} & 1 & -i & -1 & i \\ \hline \end{array} \end{aligned}\]
Note the that sum of the numbers in the first row is equal to the order of the group, and the sum of the numbers in each of the other rows is \(0\).
Similarly, the sum of the numbers in the first column is the order of the group, and the sum of the numbers in each of the other columns is \(0\). This is a special case of the orthogonality relations.