bookmark_borderWhen is the group of units in the integers modulo n cyclic?

It is easy to see with the help of Bezout’s identity that the integers co-prime to $n$ from the set $\{0,1,\cdots, n-1\}$ form a group under multiplication modulo $n$. This group is denoted by $(\mathbb{Z}/n\mathbb{Z})^*$ and it’s order is given by the Euler’s Totient function: $\varphi(n) = |(\mathbb{Z}/p\mathbb{Z})^*|$. Gauss showed that $(\mathbb{Z}/n\mathbb{Z})^*$ is a cyclic group if and only if $n=1,2,4,p,p^k$ or $2p^k$, where $p$ is an odd prime and $k > 0$. It is very easy to verify this for $n=1,2$ and $4$, as one can simply list out all positive integers less than and co-prime to $n$. So, we will only focus on proving that $(\mathbb{Z}/n\mathbb{Z})^*$ is cyclic for the remaining three cases.

Theorem 1: $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic if $p$ is a prime.

Proof: Let $d_1, d_2, \cdots , d_r$ be all the possible orders of the elements of $(\mathbb{Z}/p\mathbb{Z})^*$. Let $e=\text{lcm}(d_1, d_2, \cdots, d_r)$ and factor $e=p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k}$ as a product of distinct prime powers. By the definition of $\text{lcm}$, for each $p_i^{a_i}$ there is some $d_j$ divisible by it. Since the $d_j$‘s are orders of elements of $(\mathbb{Z}/p\mathbb{Z})^*$, there is an element $x_i$ whose order is $p_i^{a_i} t$. Then, the element $y_i = x_i^t$ has order $p_i^{a_i}$. Hence, $y_1 y_2\cdots y_k$ has order $e$. Thus, we have found an element of order $e$. Therefore, $e|p-1$. But the polynomial $x^e-1$ has $p-1$ roots $(\text{mod }p)$. Since $\mathbb{Z}/p\mathbb{Z}$ is a field, any polynomial of degree $e$ cannot have more than $e$ roots. Therefore, $p-1\leq e$ and we deduce that $e=p-1$. Thus, we have found an element of order $p-1$.

Theorem 2: $(\mathbb{Z}/p^a \mathbb{Z})^*$ is cyclic for any $a\geq 1$ if $p$ is an odd prime.

Proof: For $a=1$, we are done by Theorem 1. Let $g$ be a primitive root $(\text{mod }p)$. We first find a $t$ such that $(g+pt)^{p-1}\not\equiv 1 \; (\text{mod }p^2)$. If $g^{p-1}\not\equiv 1 \; (\text{mod }p^2)$, then we can take $t=0$. Otherwise, we can choose $t=1$. Indeed, we have $(g+p)^{p-1}\equiv 1+p(p-1) g^{p-2} \not \equiv 1 \; (\text{mod }p^2)$. Let $g+pt$ have order $d\; (\text{mod }p^a)$. Then, $d|p^a (p-1)$. Since $g$ is a primitive root modulo $p$, $(p-1) | d$. So, $d=p^{r-1} (p-1)$ for some $r\leq a$. We also know that $(g+pt)^{p-1} = 1+p s$ where $s \nmid p$. Thus, \begin{aligned} (g+pt)^{p(p-1)} &= (1+ps)^{p} \\ &= \sum_{i=0}^{p} \binom{p}{i} (ps)^i \\ &\equiv 1+p^2 s \; (\text{mod }p^3) \end{aligned} By induction, it follows that $$(g+pt)^{p^{b-1}(p-1)} \equiv 1+p^b s \; (\text{mod }p^{b+1})$$ Now, $g+pt$ has order $d=p^{r-1}(p-1)\; (\text{mod } p^a)$ which implies $(g+pt)^{p^{r-1}(p-1)} \equiv 1 \; (\text{mod }p^a)$. But then $1+p^r s \equiv 1 \; (\text{mod } p^{r+1})$ if $r\leq a-1$, which implies $p | s$, a contradiction. Thus, $r=a$.

Theorem 3: $(\mathbb{Z}/2p^a \mathbb{Z})^*$ is cyclic for any $a\geq 1$ if $p$ is an odd prime.

Proof: This follows immediately from Theorem 2 and the Chinese remainder theorem.

The fact that $(\mathbb{Z}/n\mathbb{Z})^*$ can be cyclic only for the cases discussed above can also be verified easily using the Chinese remainder theorem.

References

• M. Ram Murty. Problems in analytic number theory. Springer New York, 01-Nov-2008

bookmark_borderWeyl’s Equidistribution Theorem

In this post, we will prove the Weyl’s Equidistribution theorem. A sequence of real numbers $x_1, x_2, \cdots$ is said to be equidistributed (mod 1) if for every sub-interval $(a,b)\subset [0,1]$, we have $$\lim_{N\to \infty}\frac{|\{1\leq n\leq N:\; \langle x_n \rangle\in (a,b)\}|}{N} = b-a$$ where $\langle x \rangle$ denotes the fractional part of $x$. Weyl’s equidistribution criteria states that the following statements are equivalent:

1. $x_1, x_2, \cdots$ are equidistributed (mod 1).
2. For each non-zero integer $k$, we have $$\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^N e^{2\pi i k x_n}=0$$
3. For each Riemann integrable function $f:[0,1]\to\mathbb{C}$, we have $$\lim_{N\to \infty}\frac{1}{N}\sum_{n=1}^N f(\langle x_n \rangle) = \int_0^1 f(x) dx$$

Proof: (1) ⇒ (3)

Let $I=[a,b)\subseteq [0,1]$ and note that $$\frac{|\{1 \leq n \leq N: \langle x_n \rangle\in [a,b) \}|}{N}=\frac{1}{N}\sum_{n=1}^N \chi_{[a,b)}(\langle x_n \rangle)$$ where $\chi_{[a,b)}(x)$ equals 1 if $x\in [a,b)$ and 0 otherwise. This shows that (3) holds for the case when $f$ is a characteristic function. Now, let $\lambda_1, \lambda_2\in \mathbb{R}$ and $f_1$, $f_2$ be functions for which (3) holds. Then, \begin{aligned}\lim_{N\to \infty}\sum_{n=1}^N (\lambda_1 f_1 + \lambda_2 f_2)(\langle x_n \rangle) &= \lim_{N\to \infty} \frac{\lambda_1}{N}\sum_{n=1}^N f_1(\langle x_n\rangle) + \lim_{N\to \infty}\frac{\lambda_2}{N}\sum_{n=1}^Nf_2(\langle x_n\rangle) \\ &= \lambda_1\int_0^1 f_1(x) dx + \lambda_2 \int_0^1 f_2(x) dx \\ &= \int_0^1 (\lambda_1 f_1 + \lambda_2 f_2)(x) dx\end{aligned} Thus, (3) holds for all linear combinations of characteristic functions of subintervals of $[0,1]$.

Now, let $f:[0,1]\to \mathbb{R}$ be an integrable function, and let $\epsilon >0$. Choose step functions $f_1$ and $f_2$ such that:

• $f_1\leq f\leq f_2$ pointwise
• $\int_0^1 (f_2(x)-f_1(x))dx < \frac{\epsilon}{2}$
• There exists $N_0$ such that $\left|\int_0^1 f_1(x)dx - \frac{1}{N}\sum_{n=1}^N f_1(\langle x_n\rangle) \right| < \frac{\epsilon}{2}$ and $\left|\int_0^1 f_2(x)dx - \frac{1}{N}\sum_{n=1}^N f_2(\langle x_n\rangle) \right| < \frac{\epsilon}{2}$ for all $N\geq N_0$
It follows that for $N\geq N_0$, \begin{aligned} \int_0^1 f(x) dx - \frac{1}{N}\sum_{n=1}^N f(\langle x_n\rangle) &\leq \int_0^1 f(x) dx - \frac{1}{N}\sum_{n=1}^N f_1(\langle x_n\rangle) \\ &< \int_0^1 f(x) dx -\int_0^1 f_1(x) dx +\frac{\epsilon}{2} \\ &< \int_0^1 (f_2(x)-f_1(x)) dx + \frac{\epsilon}{2} \\ &< \epsilon \end{aligned} In a similar way, we can prove that $$\int_0^1 f(x) dx - \frac{1}{N}\sum_{n=1}^N f(\langle x_n\rangle) > -\epsilon \quad \forall\; N\geq N_0$$ Therefore, we have $$\left|\int_0^1 f(x) dx - \frac{1}{N}\sum_{n=1}^N f(\langle x_n\rangle) \right| < \epsilon \quad \forall\; N\geq N_0$$ To see that (3) holds when $f$ is complex valued, we need only consider the real and imaginary parts separately.

(2) ⇒ (3)

Let $f:[0,1]\to \mathbb{R}$ be continuous, and let $\epsilon > 0$. The Stone-Weierstrass Theorem allows us to choose a trigonometric polynomial $p$ such that: $$\sup_{x\in [0,1]} |f(x) - p(x)| < \frac{\epsilon}{3}$$ Also, (2) implies the existence of an $N_0$ such that for $N\geq N_0$, we have $$\left|\frac{1}{N}\sum_{n=1}^N p(\langle x_n \rangle)-\int_0^1 p(x) dx \right| < \frac{\epsilon}{3}$$ Now, \begin{aligned} &\; \left|\frac{1}{N}\sum_{n=1}^N f(\langle x_n\rangle) - \int_0^1 f(x) dx\right| \\ &= \left|\frac{1}{N}\sum_{n=1}^N (f(\langle x_n \rangle) - p(\langle x_n \rangle)) + \int_0^1 (p(x)-f(x))dx + \frac{1}{N}\sum_{n=1}^N p(\langle x_n \rangle) - \int_0^1 p(x) dx\right| \\ &< \frac{1}{N}\sum_{n=1}^N\left|f(\langle x_n \rangle) - p(\langle x_n \rangle) \right| + \int_0^1 \left|p(x)-f(x) \right| dx + \left|\frac{1}{N}\sum_{n=1}^N p(\langle x_n \rangle) - \int_0^1 p(x) dx \right| \\ &< \frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{\epsilon}{3} \\ &= \epsilon \end{aligned} for all $N\geq N_0$. Thus, (3) holds for continuous functions on $[0,1]$. By the proof of (1) ⇒ (3), it is sufficient to show that (3) holds for all step functions on $[0,1]$. If $g$ is a step function on $[0,1]$, we can find continuous functions $g_1, g_2$ such that $g_1\leq g\leq g_2$ and $\int_0^1 (g_1(x)-g_2(x))dx < \epsilon$. We again conclude that (3) holds for $g$.

The implications (3) ⇒ (1) and (3) ⇒ (2) are obvious.

References

• Stein, Elias M. and Shakarchi, Rami. Fourier Analysis: An Introduction. Princeton University Press, 2003

In this post, we take a look at an interesting proof of the Quadratic Reciprocity theorem by Gotthold Eisenstein.

Definition: The Legendre symbol is a function $\left(\frac{a}{p}\right)$ which takes the values $\pm 1$ depending on whether $a$ is a quadratic residue modulo $p$. $$\left(\frac{a}{p}\right) = \begin{cases}0 \quad \text{if }p|a \\ 1 \quad \text{if }a\text{ is a quadratic residue modulo }p \\ -1 \quad \text{if }a\text{ is a quadratic non-residue modulo }p\end{cases}$$ Theorem (Quadratic Reciprocity Law): If $p$ and $q$ are distinct odd primes, then the quadratic reciprocity theorem states that the congruences \begin{aligned} x^2 \equiv q \quad (\text{mod }p) \\ x^2 \equiv p \quad (\text{mod }q) \end{aligned} are both solvable or both unsolvable unless both $p$ and $q$ leave the the remainder $3$ when divided by $4$. Written symbolically, $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}$$

We will start by proving two important results about quadratic residues that will be useful later on.

Lemma 1: Let $n\not\equiv 0 \;(\text{mod }p)$. Then $n$ is a quadratic residue modulo $p$ iff $n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p)$.

Proof: Fermat’s little theorem tells us that $n^{p-1}\equiv 1 \;(\text{mod }p)$ whenever $p \not| n$. Since, $$n^{p-1}-1\equiv (n^{\frac{p-1}{2}}-1)(n^{\frac{p-1}{2}}+1)\equiv 0 \; (\text{mod }p)$$ we have $n^{\frac{p-1}{2}}\equiv \pm 1\; (\text{mod }p)$. Therefore, it suffices to prove that $n$ is a quadratic residue modulo $p$ if and only if $n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p)$.

Suppose that $\left(\frac{n}{p} \right)=1$. Then, there is an integer $x$ such that $n\equiv x^2 \; (\text{mod p})$. Now, we have $$n^{\frac{p-1}{2}}\equiv x^{p-1} \equiv 1 \equiv \left(\frac{n}{p} \right) \; (\text{mod }p)$$

Conversely, assume that $n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p)$. Let $g$ be a primitive root of $p$. Then, we have $n\equiv g^k \; (\text{mod }p)$ for some integer $k$. Since $n^{\frac{p-1}{2}}\equiv g^{\frac{k(p-1)}{2}} \equiv 1 \; (\text{mod }p)$, the order of $g$ must divide the exponent $\frac{k(p-1)}{2}$. Therefore, $p-1 | \frac{k(p-1)}{2}$ and thus $k$ is an even integer. Let’s say $k=2j$ for some integer $j$. Then, we have $$n \equiv g^k \equiv g^{2j} \equiv (g^j)^2 \; (\text{mod }p)$$ This proves that $n$ is a quadratic residue modulo $p$.

Lemma 2 (Gauss’s Lemma): For any odd prime $p$, let $a$ be an integer that is co-prime to $p$. Consider the integers $$S = \left\{ a,\ 2a,\ 3a,\cdots, \frac{p-1}{2}a \right\}$$ and their least positive residues modulo $p$. Let $n$ be the number of these residues that are greater than $p/2$. Then $$\left(\frac{a}{p}\right)=(-1)^n$$

Proof: Since $p\not | a$, none of the integers in $S$ are congruent to 0 and no two of them are congruent to each other modulo $p$. Let $r_1, \cdots, r_m$ be the residues modulo $p$ smaller than $\frac{p}{2}$, and let $s_1, \cdots, s_n$ be the residues modulo $p$ greater than $\frac{p}{2}$. Then $m+n=\frac{p-1}{2}$ and the integers $$r_1, \cdots, r_m, p-s_1, \cdots , p-s_n$$ are all positive and less than $\frac{p}{2}$. Now, we will prove that no two of these integers are equal. Suppose that for some choice of $i$ and $j$ we have $p-s_i = r_j$. We can choose integers $u$ and $v$, with $1 \leq u,v \leq \frac{p-1}{2}$ and satisfying \begin{aligned} s_i &\equiv u a \; (\text{mod }p) \\ r_j &\equiv v a \; (\text{mod }p) \end{aligned} Now, we have $$s_i+r_j \equiv a(u+v) \equiv p \equiv 0 \; (\text{mod }p)$$ This implies that $u+v \equiv 0 \; (\text{mod }p)$. However, this is not possible because $1\leq u+v \leq p-1$. Thus, we have proven that the numbers $r_1,\cdots, r_m, p-s_1, \cdots p-s_n$ are simply a rearrangement of the integers $1,2,\cdots, \frac{p-1}{2}$. Their product is equal to $\left(\frac{p-1}{2} \right)!$. Therefore, \begin{aligned} \left(\frac{p-1}{2}\right)! &= r_1 \cdots r_m (p-s_1)\cdots (p-s_n) \\ &\equiv (-1)^n r_1 \cdots r_m s_1\cdots s_n \; (\text{mod }p) \\ &\equiv (-1)^n a\cdot 2a\cdots \left(\frac{p-1}{2}\right)a \; (\text{mod }p) \\ &\equiv (-1)^n a^{\frac{p-1}{2}} \left( \frac{p-1}{2}\right)! \; (\text{mod }p) \end{aligned} The $\left( \frac{p-1}{2}\right)!$ term can be cancelled from both sides as $p\not| \left( \frac{p-1}{2}\right)!$. In other words, we have $a^{\frac{p-1}{2}}\equiv (-1)^n \; (\text{mod }p)$. This completes the proof of Gauss’s lemma.

Using the periodicity properties of $\sin$ and Gauss’s lemma, it is easy to verify the following result:
Lemma: Let $p$ and $q$ be distinct odd primes and let $A = \left\{ \alpha\in \mathbb{Z} | 1\leq \alpha \leq \frac{p-1}{2}\right\}$ be a half system modulo $p$. Then, $$\left(\frac{q}{p}\right) = \prod_{\alpha\in A}\frac{\sin\left(\frac{2\pi}{p}q\alpha\right)}{\sin\left(\frac{2\pi}{p}\alpha\right)} \quad\quad (1)$$
We start by examining the right hand side of equation $(1)$. The addition theorem for trigonometric functions yields $\sin 2\alpha = 2\sin\alpha\cos\alpha$ and $\sin 3\alpha = \sin\alpha(3-4\sin^2\alpha)$. Induction shows that $\sin q\alpha = \sin\alpha P(\sin\alpha)$ for all odd $q\geq 1$, where $P\in \mathbb{Z}[X]$ is a polynomial of degree $q-1$ and highest coefficient $(-4)^{\frac{q-1}{2}}$. Thus there exist $a_i \in \mathbb{Z}$ such that \begin{aligned}\frac{\sin qz}{\sin z} &= (-4)^{\frac{q-1}{2}} \left( (\sin z)^{q-1}+a_{q-2} (\sin z)^{q-2}+\cdots + a_0 \right) \\ &= (-4)^{\frac{q-1}{2}} \psi(X), \quad \text{where }X=\sin z\end{aligned} Since $\phi(z)=\frac{\sin qz}{\sin z}$ is an even function, so is $\psi(X)$, hence $a_{q-2}=\cdots = a_1 = 0$. Now $\phi(z)$ has zeros $\left\{ \pm \frac{2\pi}{q}\beta, \ 1\leq \beta \leq \frac{q-1}{2}\right\}$. Since $\psi$ is monic of degree $q-1$, we may write $$\psi(X) = \prod_{\beta\in B}\left(X^2-\sin^2\frac{2\pi\beta}{q} \right)$$ where $B=\left\{1,\cdots,\frac{q-1}{2} \right\}$ is a half system modulo $q$. Replacing $X$ by $\sin z$, we get $$\frac{\sin qz}{\sin z} = (-4)^{\frac{q-1}{2}} \prod_{\beta\in B }\left( \sin^2z -\sin^2\frac{2\pi\beta}{q}\right) \quad \quad (2)$$ Put $z=\frac{2\pi\alpha}{p}$ in equation $(2)$ and plug the result into equation $(1)$. \begin{aligned} \left(\frac{q}{p}\right) &= \prod_{\alpha\in A} (-4)^{\frac{q-1}{2}} \prod_{\beta\in B} \left( \sin^2\frac{2\pi\alpha}{p} -\sin^2\frac{2\pi\beta}{q}\right)\\ &= (-4)^{\frac{q-1}{2} \frac{p-1}{2}} \prod_{\alpha\in A}\prod_{\beta\in B} \left( \sin^2\frac{2\pi\alpha}{p} -\sin^2\frac{2\pi\beta}{q}\right)\quad\quad (3) \end{aligned} Exchanging $p$ and $q$ on the right side of $(3)$ give rise to factor of $(-1)^{(p-1)(q-1)/4}$. Therefore, $$\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}\left(\frac{p}{q}\right) \tag{4}$$ which is the quadratic reciprocity law.