When 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 (\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). Also, 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. (\mathbb{Z}/2p^a \mathbb{Z})^* \simeq (\mathbb{Z}/2\mathbb{Z})^* \times (\mathbb{Z}/p^a \mathbb{Z})^* \simeq (\mathbb{Z}/p^a \mathbb{Z})^*

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

Weyl’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

  • Hannigan-Daley, Brad. Equidistribution and Weyl’s criterion. Retrieved from http://individual.utoronto.ca/hannigandaley/equidistribution.pdf. Accessed 5 Feb. 2020.
  • Stein, Elias M. and Shakarchi, Rami. Fourier Analysis: An Introduction. Princeton University Press, 2003

Eisenstein’s Proof of Quadratic Reciprocity

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.

We are now ready to prove the Quadratic reciprocity theorem.

Proof of the Quadratic Reciprocity Theorem:

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.

References

  • Lemmermeyer, Franz. “Reciprocity Laws: From Euler to Eisenstein”. New York, Springer, 2000
  • Burton, David M. “Elementary Number Theory”. New Delhi, Tata McGraw-Hill Publishing Company Limited, May 1 2006