Homework 2
Euler’s theorem, quadratic residues, and quadratic reciprocity
Instructions
For each problem, please write a complete argument, not only intermediate calculations. Answers without justification may receive zero credit. Collaboration is encouraged, but you must write your own final solutions independently.
1 Fermat’s little theorem. Fermat’s little theorem asserts that for any prime \(p\) and any \(a\in\mathbb{Z}\), we have \(a^{p}\equiv a\pmod{p}\). In class we deduced this result from Euler’s theorem. Here we give a direct proof.
(1) Consider the binomial coefficients \[ \binom{p}{k}=\frac{p!}{k!(p-k)!},\qquad 1\le k\le p-1, \] which are all positive integers. Prove that \(p\) divides \(\displaystyle\binom{p}{k}\) for every \(1\le k\le p-1\).
(2) Show that for any \(x,y\in\mathbb{Z}\), \[ (x+y)^p\equiv x^p+y^p\pmod{p}. \] Then use this and induction to show that for any \(x_1,\ldots,x_n\in\mathbb{Z}\), \[ \bigg(\sum_{i=1}^{n}x_i\bigg)^p\equiv \sum_{i=1}^{n}x_i^p\pmod{p}. \]
(3) Deduce Fermat’s little theorem.
2 Euler’s theorem. Let \(\phi(m)\) be the Euler totient function, which, for every positive integer \(m\), counts the number of positive integers \(n\le m\) with \(\gcd(n,m)=1\). In class we proved Euler’s theorem that if \(\gcd(a,m)=1\), then \(a^{\phi(m)}\equiv1\pmod{m}\).
(1) Show that if \(p^k\) is a prime power, then \(\phi(p^k)=p^{k-1}(p-1)\). This is a natural generalization of \(\phi(p)=p-1\) discussed in class.
(2) Compute the following residues. For each part, your final answer should be a nonnegative integer less than the given modulus.
(a) \(18^{20}\pmod{25}\)
(b) \(3^{2026} \pmod{49}\)Hint
You may find \(3^5=3^4\cdot 3=81\cdot3\equiv 32\cdot3\equiv 96 \equiv -2\pmod{49}\) useful.Hint
\(4^{137}8^{93}=2^{553}\).(3) Euler’s theorem can also be stated in the form \[ \bar{a}\equiv a^{\phi(m)-1}\pmod{m}, \] where \(\bar{a}\) is the least positive multiplicative inverse of \(a\pmod{m}\), meaning that it is the least positive integer satisfying \(a\bar{a}\equiv 1\pmod{m}\). Use this to find the least positive multiplicative inverse of \(3\pmod{25}\).
(4) For an odd positive integer \(m\) with prime factorization \(m=p_1^{n_1}\cdots p_k^{n_k}\), where \(p_1,\ldots,p_k\) are distinct primes and \(n_1,\ldots,n_k\) are positive integers, the Carmichael function \(\lambda(m)\) is defined as the least common multiple of \(\phi(p_1^{n_1}),\ldots,\phi(p_k^{n_k})\), namely, the least positive integer divisible by each of these numbers, with the convention that \(\lambda(1)=1\). Assuming the property that \(\phi(n)\mid\phi(m)\) whenever \(n\mid m\), show that \(\lambda(m)\mid\phi(m)\) and that if \(\gcd(a,m)=1\), then \[ a^{\lambda(m)}\equiv 1\pmod{m}. \] For comparison, when \(m=15\), we have \(\phi(15)=8\) and \(\lambda(15)=4\). So the above becomes \(a^4\equiv 1\pmod{15}\), while Euler’s theorem gives the weaker conclusion \(a^8\equiv 1\pmod{15}\).Hint
For the second part, you may use the fact that if \(\gcd(m,n)=1\), then \[a\equiv b \pmod{m},~a\equiv b \pmod{n}\iff a\equiv b \pmod{mn}.\] The backward implication follows immediately from transitivity of divisibility. To prove the forward implication, let \(c=a-b\) and suppose that \(m\mid c\) and \(n\mid c\). Multiplying the first divisibility relation by \(n\) and the second divisibility relation by \(m\) gives \(mn\mid nc\) and \(mn\mid mc\). Since \(\gcd(m,n)=1\), Bézout’s lemma ensures that there are some \(x,y\in\mathbb{Z}\) such that \(mx+ny=1\). Multiplying both sides of this equation by \(c\), we have \(mcx+ncy=c\). It follows by linearity that \(mn\mid c\), which is equivalent to \(a\equiv b \pmod{mn}\).3 Lagrange’s theorem. Recall that \(\mathbb{Z}[x]\) denotes the ring of polynomials with integer coefficients. For any nonzero \(m\in\mathbb{Z}\), we may extend the congruence relation modulo \(m\) to \(\mathbb{Z}[x]\) by defining \(f(x)\equiv g(x)\pmod{m}\) if \(m\) divides every coefficient of \(f(x)-g(x)\). It is easy to check that \(\equiv\) is an equivalence relation on \(\mathbb{Z}[x]\).
(1) Let \(a\in\mathbb{Z}\) and \(f(x)\in\mathbb{Z}[x]\). Show that \(f(a)\equiv0\pmod{m}\) if and only if there is some \(g(x)\in\mathbb{Z}[x]\) such that \[ f(x)\equiv(x-a)g(x)\pmod{m}. \]
Hint
For the necessity part, you may start with \(f(x)\equiv f(x)-f(a)\pmod{m}\) and take advantage of the identity \(x^k-a^k=(x-a)g_k(x)\), where \(k\) is a nonnegative integer and \[g_k(x):=x^{k-1}+ax^{k-2}+a^2x^{k-3}+\cdots+a^{k-2}x+a^{k-1}\in\mathbb{Z}[x].\] In calculus, this exact identity can be combined with the limit defintion of derivative to prove the integer power rule: \[\frac{d}{dx}(x^k)=kx^{k-1}.\]Hint
Induction on \(n\) or proof by contradiction. If \(f(a)\equiv 0\pmod{p}\), then part (1) produces some \(g(x)\in\mathbb{Z}[x]\) such that \[ f(x)\equiv(x-a)g(x)\pmod{p}. \] What can you say about the leading coefficient and degree of \(g(x)\)? If \(b\) is another root of the congruence \(f(x)\equiv 0\pmod{p}\), how is it related to \(g(x)\) in view of Euclid’s lemma?4 Euler’s criterion. Euler’s criterion states that if \(p>2\) is prime and \(a\in\mathbb{Z}\) with \(p\nmid a\), then \[ \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}. \] We proved this in class based on Lagrange’s theorem. The purpose of this problem is to obtain a different proof. Consider the set \(A=\{1,\ldots,p-1\}\).
(1) Show that when \(a\) N \(p\), \(A\) can be partitioned into \(\frac{p-1}{2}\) pairs of distinct numbers, such that each pair \(\{x,y\}\) satisfies \(xy\equiv a\pmod{p}\), and that when \(a\) R \(p\), \(A\) can be partitioned into \(\frac{p-1}{2}\) pairs of distinct numbers, such that one pair is of the form \(\{x_0,p-x_0\}\) satisfying \(x_0^2\equiv a\pmod{p}\) and every other pair \(\{x,y\}\) satisfies \(xy\equiv a\pmod{p}\).
Hint
Use the theorem on linear congruences to show that the function \(f:A\to A\) defined by \[x f(x)\equiv a\pmod{p}\] is well-defined and bijective.(2) Prove, by multiplying the numbers \(1,\ldots,p-1\) in two ways and reducing the product modulo \(p\), that \[ (p-1)!\equiv -\left(\frac{a}{p}\right)a^{\frac{p-1}{2}}\pmod{p}. \]
(3) Deduce Wilson’s theorem that \((p-1)!\equiv-1\pmod{p}\) and then Euler’s criterion.
5 Gauss’s lemma. Use Gauss’s lemma to show that \(-3\) R \(p\) if \(p\equiv 1\pmod{6}\) and \(-3\) N \(p\) if \(p\equiv 5\pmod{6}\).
6 Quadratic reciprocity. Evaluate the following Legendre symbols.
(1) \(\displaystyle\left(\frac{17}{41}\right)\)
(2) \(\displaystyle\left(\frac{15}{43}\right)\)
(3) \(\displaystyle\left(\frac{280}{293}\right)\)
7 Jacobi symbol. For any \(a\in\mathbb{Z}\) and any positive odd integer \(n=p_1\cdots p_k\), where \(p_1,\ldots,p_k\) are odd primes, define the Jacobi symbol \[ \left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)\cdots \left(\frac{a}{p_k}\right) \] with the convention that \(\left(\frac{a}{1}\right)=1\). It is understood that each \((\frac{a}{p_i})\) on the right-hand side is a Legendre symbol. In particular, the Jacobi symbol agrees with the Legendre symbol when \(n\) is a prime. Verify the following properties for the Jacobi symbol.
(1) (Periodicity) For any positive odd integer \(n\) and any \(a,b\in\mathbb{Z}\) such that \(a\equiv b\pmod{n}\), \[ \left(\frac{a}{n}\right)=\left(\frac{b}{n}\right). \]
(2) (Complete multiplicativity) For any positive odd integers \(m,n\) and any \(a,b\in\mathbb{Z}\), \[\begin{align*} \left(\frac{ab}{n}\right)&=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right),\\ \left(\frac{a}{mn}\right)&=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right). \end{align*}\]
(3) (\(-1\) mod \(n\)) For any positive odd integer \(n\), \[ \left(\frac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}. \]Hint
You may first consider proving by induction that \[\frac{a_1a_2\cdots a_k-1}{2}\equiv\sum_{i=1}^{k}\frac{a_i-1}{2}\pmod{2}\] for any odd integers \(a_1,\ldots,a_k\).(4) (\(2\) mod \(n\)) For any positive odd integer \(n\), \[ \left(\frac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}. \]
Hint
You may first consider proving by induction that \[\frac{(a_1a_2\cdots a_k)^2-1}{8}\equiv\sum_{i=1}^{k}\frac{a_i^2-1}{8}\pmod{2}\] for any odd integers \(a_1,\ldots,a_k\).(5) (Quadratic reciprocity) For any positive odd integers \(m,n\) with \(\gcd(m,n)=1\), \[ \left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}=\begin{cases} -1, & \text{if } m,n \equiv 3\pmod{4}, \\ 1, & \text{otherwise}. \end{cases} \] Thus the Jacobi symbol retains all the key properties of the Legendre symbol. These properties often make evaluation of Legendre symbols a lot easier. For instance, \[ \left(\frac{15}{43}\right)=-\left(\frac{43}{15}\right)=-\left(\frac{43}{5}\right)\left(\frac{43}{3}\right)=-\left(\frac{3}{5}\right)\left(\frac{1}{3}\right)=-\left(\frac{5}{3}\right)=-\left(\frac{2}{3}\right)=1. \]
8 Sum of two squares. Determine which of the following integers can be expressed as a sum of two squares. For each one that can, find such a representation.
Hint
To find a representation of a large number \(n\) as a sum of two squares, it is often convenient to write it as \(n=u^2v\), where \(v\) is not divisible by any square greater than 1. For each prime \(p\mid v\), find a representation \(p=x_p^2+y_p^2\) and then use the formula \[(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\] repeatedly to get a representation \(v=x_v^2+y_v^2\). As a result, \(n=(ux_v)^2+(uy_v)^2\).(1) 605
(2) 2026
(3) 6174
9 Quadratic congruence equations. Solve the quadratic congruence \(x^2+x+3\equiv0\pmod{15}\).
10 Sum of three squares. Show that no integer of the form \(4^a(8b+7)\), where \(a,b\ge0\) are integers, can be expressed as a sum of three squares.
Hint
Prove the case \(a=0\) first by examining the possible residues of a sum of three squares modulo 8. Then prove the remaining case \(a\ge1\) using proof by contradiction and examining the minimal integer of the form \(4^a(8b+7)\) that can be written as a sum of three squares.Optional challenge
11 Half factorials mod \(p\). Let \(p>2\) be prime.
(1) Prove \[ \left[\left(\frac{p-1}{2}\right)!\right]^2\equiv (-1)^{\frac{p+1}{2}}\pmod{p}. \]
(2) Show that if \(p\equiv 3\pmod{4}\), then \[ \left(\frac{p-1}{2}\right)!\equiv (-1)^{n}\pmod{p}, \] where \(n\) is the number of integers \(1\le k<p/2\) that are quadratic nonresidues modulo \(p\).