Quadratic reciprocity deals with the solvability of quadratic equations modulo prime numbers. It deals with solving the congruence . Quadratic reciprocity is an important and interesting part of mathematics with many practical uses in computer science and cryptography. For example, the first probabilistic public-key encryption scheme relies on calculations that can only be done efficiently using the law of quadratic reciprocity. This paper presents a proof of quadratic reciprocity. To make the paper self-contained and accessible for high school readers unfamiliar with number theory, we have included all necessary background, including novel explanations and examples. This sets our paper apart from the majority of expository work on the subject, which assumes greater mathematical knowledge on the reader’s part.
Quadratic reciprocity is a fundamental theorem of number theory, the part of mathematics that focuses on whole numbers. It was initially formulated by Euler and Legendre in the 18th century and given two complete proofs by Gauss in 1801. Euler was studying earlier results of Fermat relating to Pell’s equation, which led him to the preliminary form of the law of quadratic reciprocity. However, it wasn’t until Gauss published a proof of the quadratic reciprocity that it became a theorem. It was the first nontrivial result in number theory; it had no uses then, but applications of it were found later in the 20th century. Quadratic reciprocity is a theorem in number theory that has greatly advanced our understanding of prime numbers and congruences. It deals with the solvability of quadratic equations modulo prime numbers; in particular, this concept is often used to determine whether congruences of the form have a solution. However, it is difficult to grasp without the prerequisite knowledge. The purpose of this text is to explain quadratic reciprocity and the prerequisite knowledge in a way that can be understood by readers who may not have an extensive background in mathematics. There are many proofs of quadratic reciprocity and many texts explaining them; however, many of these texts were written for experienced mathematicians and are quite difficult to understand. This expository note differs from others in that, unlike other reviews on quadratic reciprocity, its target audience is high schoolers interested in the topic who may not possess the prerequisite knowledge.
The general topics covered are modular arithmetic, quadratic residues, quadratic reciprocity, and Hensel’s lemma. Modular arithmetic and congruences (section 3) are essential for learning about quadratic reciprocity, as quadratic reciprocity is based on the solvability of congruences. Fermat’s theorem (Section 4) is key to our understanding of congruences and will be utilized to solve congruences involving prime numbers throughout this text. Prime moduli and power quadratic residues (sections 5 and 6) are essential to quadratic reciprocity, as they provide useful information regarding quadratic congruences and their solutions. Hensel’s lemma (Section 8) is not directly used in the proof of quadratic reciprocity presented; however, it is quite useful in dealing with modular arithmetic and the applications of quadratic reciprocity.
The reader should be familiar with derivatives/higher derivatives (only used in the section regarding Hensel’s lemma) and prime factorization of integers. However, the reader does not have to be familiar with multivariable calculus, differential equations, or linear algebra, as this text does not utilize these areas of mathematics. Additionally, this text utilizes basic proof techniques like contradiction and induction, but they are used in a way such that readers unfamiliar with these techniques will likely be able to understand the relevant passages.
Learning Objectives: After reading this paper, the reader should
- Understand modular arithmetic (which is used in cryptography/computer science) and be able to apply it
- Understand what quadratic residues and non-residues are
- Be able to follow the proof of the law of quadratic reciprocity and be able to apply it to calculate legendre symbols modulo prime numbers
- Understand the connection between calculus and number theory through the use of the Taylor expansion in the proof of Hensel’s lemma
- Be familiar with the structure of mathematical proofs.
Modular Arithmetic, Congruence, and Integers
Modular arithmetic is quite similar to normal arithmetic: it is arithmetic on remainders when numbers are divided by a fixed positive integer called a modulus. When doing modular arithmetic, every number is divided by the modulus (m), which must be a positive integer and denoted by . To repeat, the integer (m) is greater than 1, and the remainder upon division by (m) is always in the range . We are setting a fixed positive integer (m) and then reducing everything to its remainder by dividing by (m). For example, if (m = 5), then . Similarly, . Thus, in modular arithmetic, there are only finitely many values, in contrast to the infinite range of integers. In modular arithmetic, numbers are generally related by congruences (denoted by (\equiv)), which are essentially the equal signs of the modular world.
Definition 1 Let integers a and b be integers. We say that a divides b if there is an integer c so that . This is written ; we refer to a as a divisor of b and b as a multiple of a. If a does not divide b, when we write .
Definition 2 Let m be a positive integer, which we call the modulus. Then we say that a and b are equivalent modulo m if a-b is a multiple of m. In other words, if a and b, when divided by m, result in the same reminder, then they are congruent modulo m. This is denoted as .
Example 3.1 because the difference 19-7=12 is a multiple of 4. By the same logic, we know that , (mod 6), and (mod 3) as well
In modular arithmetic, the operations of addition, subtraction, and multiplication remain much the same, with the exception that new relations like now result. However, the operation of division is much different, as we will see later in this text. While the functions other than division don’t change much, they are not exactly equivalent to their non-modular counterparts. For example, , while , and , while . Modular arithmetic is key to understanding the other topics in this text: quadratic reciprocity and many of the topics surrounding it, such as Fermat’s little theorem, Hensel’s lemma, and quadratic residues, are extensions of modular arithmetic and congruences.
The following simple theorem allows us to replace numbers in modular arithmetic.
Theorem 1 If and , then .
Proof. If , then we can write a=b+tm, and if , then we can write c=d+sm. This means that
Theorem 2 If and , then .
Proof. As in the proof of theorem 1, we can write a=b+tm and c=d+sm. Then, multiplying the two gives us
completing the proof.
This means that all
Lemma 3 Fix an integer m. Then x and y have the same remainder when divided by m if and only if .
Proof. Suppose that and x=am+r, where the remainder r is in the range . Then y=x+sm for some integer s, and so y=am+r+sm=(a+s)m+r, showing that y has the same remainder. On the other hand, if x=am+r, then , and if y has the same remainder, then
Definition 3 Let m,n be two nonzero integers. A common divisor of m and n is an integer d so that and . The greatest common divisor of m and n is denoted gcd(m,n) or just (m,n). If (m,n)=1 then we say that m and n are coprime.
Example 3.2 16 and 9 are co-prime to each other. The only positive factors of 16 are 1, 2, 4, 8, and 16, and the only factors of 9, are 1, 3, and 9, meaning that the only common factor they share in 1.
The following lemma allows us to confirm the existence of modular inverses (discussed later in this section) and will be used in the proof of Euclid’s lemma.
Lemma 4 Let m and n be non-zero integers. Then there exist integers x and y so that xm+ny=(m,n). In particular, if (m,n)=1, there exists an integer x so that .
Proof. Consider the smallest positive combination b=xm+yn where m and n are integers. Then, b must divide x because if it didn’t, we could write x=bs+r where r must be less than b. This means we could express r as a smaller combination of x and y, which cannot be true because b is already the smallest combination of x and y. If d is any other common divisor of m and n, then , because and . So d has to divide b, which means that , proving that b is the greatest common divisor of x and y. Since b=xm+yn where b is the gcf of x and y, when b=1, we can write 1=xm+yn. Then, we can write xm=1-yn. Because , we get .
Euclid’s lemma is extremely useful for dividing prime numbers and prime factorization. This will be extremely important for working with prime moduli, which are the basis of quadratic reciprocity and the theorems surrounding it.
Lemma 5 (Euclid’s lemma) Suppose that p is prime and . Then or . In particular, if and , then .
Proof. Because p is prime, the greatest common denominator of a and p is 1. By lemma 4, we can write 1=ax+py. Then, we can multiply both sides of the equation by b, giving us b=bax+bpy. since , , and p must divide bpy. Because p divides both of these terms, it must also divide their sum, b, completing the proof.
Definition 4 Let (m,n)=1 and let x be an integer so that (such an x must exist by the previous lemma). Then we say that x is the inverse of m modulo n, i.e. .
Example 3.3 because . Similarly, because .
The reverse Euclidean algorithm is an efficient method of finding these modular inverses; however, it is unnecessary for the proof of quadratic reciprocity presented in this text.
Modular arithmetic is essential to understanding Quadratic reciprocity. The law of quadratic reciprocity is a theorem about congruences, so it would not exist if not for modular arithmetic. The rest of this text also contains theorems and lemmas based on modular arithmetic and congruences.
Fermat’s Little Theorem
Fermat’s little theorem simplifies the process of dealing with prime powers, which are quite prevalent in the proofs and applications of quadratic reciprocity.
Definition 5 Let m be a positive integer. A set of integers is called a reduced residue system modulo m if the following are all true:
- Every is coprime with m, for i=1, \ldots ,k.
- No two with are equivalent modulo m.
- Every integer n that is coprime to m is equivalent modulo m to exactly one
Each individual number in a reduced residue set is often called a residue.
For any prime p, the set is a reduced residue system. This is because every natural number less than p is co-prime to it. Any other integer not divisible by p is equivalent to exactly one number in the range. modulo p.
The following lemma is quite useful as it provides us with a straightforward method of determining a reduced residue system for some prime p.
Lemma 6 Suppose that p is prime and . Then is a reduced residue system.
Proof. Since , we know that (a,p)=1, and so we have an inverse for a modulo p, say . Now, the prime number p will not divide ja for (by the fundamental theorem of arithmetic) because it does not divide either factor j or a. So, the first condition for a reduced residue set is satisfied, (ja,p)=1. If , we can multiply by the inverse x and use our theorems from Section 4 to infer . So, no two of the residues ja,ka are equivalent. Also, if n is any integer coprime to p, then nx is coprime to p (by the fundamental theorem of arithmetic) because p does not divide either n or x, so it is equivalent to some j in the range . This means that , so every integer coprime to p is equivalent to some number in the set .
The following result is extremely useful when dealing with congruence modulo p and primes in general. It will be essential to many of the proofs in this text.
Theorem 7 Fermat’s little theorem: Suppose that p is a prime number, and a is any integer. Then . If in addition we know that (a,p)=1, then .
Proof. : If , then a is divisible by p. This means that . Additionally, , meaning that . To prove this theorem when (a,p)=1, we can look at the sequence . By lemma 6, we know that is a reduced residue system as well, so when every term in the sequence is multiplied by some number a, every term will remain distinct modulo p, so the set will still be a reduced residue system modulo p). All the terms of any reduced residue system modulo p, when multiplied together, must result in the same product modulo p; this is because any reduced residue set modulo p can be obtained by adding or subtracting some multiple of p from every term in any other reduced residue system modulo p, and . Adding to every term will not affect its product modulo p. Thus, we can write (both sides of the congruence are products of every term in a reduced residue system modulo p). Then, we can factor out an a from each term, giving us (each term in the sequence was multiplied by a, and there were p-1 terms in the sequence, so, because we factored out an a from each term, we have to multiply by ). Then, we can rewrite as (p-1)!, giving us . Then, we can divide both sides of the congruence by (p-1)!, giving us (This is supported by lemma 4) because p does not divide any integer in the set , meaning that it does not divide (p-1)!, so there is some inverse of (p-1)! modulo p), completing the proof.
Fermat’s Theorem is essential to the proof of Euler’s criterion, which is necessary for proving quadratic reciprocity and calculating Legendre symbols.
If we take an integer-coefficient polynomial and examine its values modulo p, we obtain a polynomial modulo p. While the introduction of congruences makes polynomials more difficult to work with, we can still transfer some of our knowledge of polynomials over real numbers. The degree of a congruence is n so long as a isn’t divisible by p.
Definition 6 Consider the integer-coefficient polynomial . Let j be the largest integer such that ; the degree of the congruence is equal to j. If no such value of j exists (all coefficients in the function are congruent to ), then the congruence has no degree. For example, the degree of the congruence is 2.
A congruence like has infinitely many integer solutions (all odd integers). but only 1 solutions modulo 2 (namely 1).
The following theorem can be used to determine the maximum number of solutions a congruence can have based on its degree. This result is somewhat similar to the fundamental theorem of algebra.
Theorem 8 If the polynomial congruence is of degree n, then there are at most n solutions
Proof. If a congruence has a degree of 0, then it has 0 solutions because the congrence could be written as . If a congruence only is of degree 1, then it only has one solution. We will assume that this is true for all degrees (this will be our induction hypothesis). We assume by way of contradiction that , of degree n, has more than n solutions. Then, let be a congruence of degree n that has more than n solutions. The leading term of f(x) is , and the solutions to the congruence are where each solution is unique. Then let
g(x) must have a lower degree than f(x) because is the leading term in f(x), and , so g(x) must be at least one degree lower than f(x). The polynomial g(x) must have at least n solutions (because must be solutions). We can look at two cases: where every coefficient in g(x) is divisible by p, and where not every coefficient of g(x) is divisible by p. In the first case, every integer x satisfies the congruence . Additionally, as stated earlier, is a solution to the congruence . Plugging to the equation above gives us , or . However, , meaning that the congruence is false, thus disproving the statement that every coefficient of g(x) is divisible by p.
Then, we must look at the second case, in which at least one coefficient of g(x) is not divisible by p (meaning that the degree of the congruence has a degree less than n). Since we know that the congruence can have at most n-1 solutions by induction because its degree is at most n-1, we obtain a contradiction because all of the numbers are solutions to . Thus, the congruence of degree n can have at most n solutions.
It is important to understand Quadratic Residues before learning about the law of quadratic reciprocity because its purpose is to relate to quadratic congruences modulo a prime. Quadratic residues are used to determine whether quadratic congruences have solutions.
Definition 7 An integer a is a quadratic residue modulo m if the congruence has a solution; otherwise, a is a quadratic non-residue.
Example 6.1 3 is a quadratic residue modulo 11 because . Conversely, 8 is not a quadratic residue modulo 11. We can take the residue set 0,1,2,3,4,5,6,7,8,9,10, square each of them, and reduce them modulo 11, giving us 0,1,4,9,5,3,3,5,9,4,1=0,1,3,4,5,9. 8 is not in this final set, meaning that it isn’t a quadratic residue modulo 11. Additionally, the residues repeat after they reach For example, taking the residues of modulo 11, we get 1,4,9,5,3,3,5,9,4,1. The residues modulo 11 repeat after reaching , which is equal to
It is important to note that while all perfect squares are quadratic residues modulo any m, not all quadratic residues are perfect squares. For example, (this works for any perfect square), while even though 21 is not a perfect square.
The following lemma shows that there are as many quadratic residues as there are non-residues modulo p. This is quite useful in general when working with quadratic residues and will aid in the proof of other theorems in this text.
Lemma 9 Let p be an odd prime. Then there are exactly (p-1)/2 quadratic residues mod p, and they are
All of these residues are distinct mod p, and any quadratic residue mod p must be equivalent to one of these. There are (p-1)/2 quadratic nonresidues.
Proof. By construction all the numbers are perfect squares so they are quadratic residues. Also if any a is chosen with (a,p)=1 and , then b is either in the range or it is in the range . But these are the negatives of the integers in the original range, so if b=p-k, we can take b’=k and then . So, all the quadratic residues are in that range.
It remains to show that none of the are repeats. If and , then using sum of squares we have . This means that . But the numbers are distinct (mod p) (their difference is at most and their sum m+n is likewise bounded by . So neither or . Thus it is impossible for if m,n are distinct integers from the list .
This shows there are exactly (p-1)/2 quadratic residues. As there are p-1 nonzero residues mod p, there must exist quadratic nonresidues.
Definition 8 If a and p are coprime, and if a is a quadratic residue modulo p, then we define ; if a,p are coprime and a is a quadratic non-residue modulo p, we define . Finally, if , we define .
Legendre symbols are used to communicate whether quadratic congruences have solutions. Using the theorems and lemma surrounding these symbols, we can more easily determine whether quadratic congruences have a solution and relate the solvability of different quadratic congruences to each other. It is also important to note that the Legendre symbol is p-periodic, so (This is a consequence of the results in section 4). For example, .
The following result is quite useful when working with Legendre symbols. It has many practical restrictions, but it theoretically can be used to calculate any Legendre symbol.
Theorem 10 Euler’s Criterion: Let p be an odd prime and a be an integer coprime to p. Then, .
Proof. By Fermat’s theorem, we know that for any a coprime to p, Factoring this, we get
Then, we can write
This means that every integer must satisfy either or . Then, by theorem 8, we know that each of these congruences has at most solutions. There are quadratic residues modulo p; we will show that all of them are solutions to the congruence . If a is a quadratic residue, then . p cannot divide b because p does not divide a (since a is a quadratic residue modulo p). So, we get . This means that all quadratic residues must be a solution to the congruence If a is a quadratic non-residue, then it must satisfy either
However, we have already established solutions to the congruence , and we know that it can have a maximum of solutions (by theorem 8), so there must be solutions to the congruence (because . When (a is divisible by p), . This means that the congruence is always true, proving Euler’s criterion.
For small primes p, Euler’s criterion is a reliable method of determining the value of a Legendre symbol. For example, without this extremely useful theorem, it would be quite strenuous to determine whether or not 6 is a quadratic residue modulo 37. Instead of plugging in 37 different values into the congruence , we can simply determine the value of . We know that , so , meaning that . Additionally, because the Legendre symbol is periodic, we know that
Euler’s criterion can be extremely useful, but it cannot be used to determine the values of Legendre symbols involving very large primes. For example, take the largest prime number, . Euler’s criterion could never be used to calculate the value of by hand. However, the weakness of Euler’s criterion is solved by the law of quadratic reciprocity.
The following lemma shows that Legendre symbols are multiplicative. This fact is extremely useful for simplifying Legendre symbols.
Lemma 11 Let p be an odd prime. Then,
Proof. By Euler’s criterion, we know that
Then means that . Since
Because the only possible values of a Legendre symbol are -1, 0, and 1, both sides of the congruence lie within the set -1,0,1. This means that the difference of both sides must lie in the set -2,0,2. p is an odd prime, so it can only divide the difference of both sides if the difference is zero, meaning that they are equal. Thus, we can replace the congruence sign in the previous equation with an equal sign, giving us
In view of the previous lemma, we say that Legendre symbols are multiplicative. This is quite useful in conjunction with Euler’s criterion. It allows us to divide Legendre symbols into multiple parts that are easier to calculate and multiply them. For example, to determine the value of , instead of calculating , we can calculate , which only requires us to determine the value of . Since , we know that
The following theorem allows us to Legendre symbols involving negative values.
Theorem 12 If p is an odd prime, then
Proof. This theorem is essentially an extension of the fact that (Euler’s Criterion). We know that and are equal to . If they are congruent, then their difference must be divisible by p, but p is odd, so their difference must be equal to 0 (because the only possible values of their difference are (-2, 0, and 2). Two quantities with a difference of 0 must be equal to each other, so we can write
It is important that we are able to easily calculate the values of Legendre symbols involving -1 because it makes it much easier to work with Legendre symbols involving negative numbers. As established earlier, ; we can easily calculate the value of by determining the value of . We know that , so
While Euler’s criterion, in principle, can find all Legendre symbols modulo p, the following theorem is a more precise result we will use in the proof of Quadratic Reciprocity.
For the proof of the following result, known as lemma of Gauss, we follow the proof laid out in1 adding details for ease of reading.
Theorem 13 Lemma of Gauss: Take some prime p and some integer a that is coprime to p. Consider the sequence and their least positive reminders modulo p.If x denotes the number of these remainder that exceed , then
Proof. This proof is somewhat lengthy, but the idea is to show that and are equivalent modulo p and then use Euler’s criterion to show . As in the proof of Theorem 12, this will show that . Let denote the number of remainders that exceed and let represent the remainders that do not exceed . Each of the terms in each sequence is distinct, and there are terms, so . To prove that the terms are distinct, take two terms in the sequence and . j and k must be distinct integers between 1 and because and are terms in the sequence a,2a, \ldots a . If and are equivalent (mod p), then . This can only be true of since j and k are both less than p. If , then j=k, so no two terms in the sequence can be equivalent. Because Each is greater than , we have .
The first step in the proof is to show that no p- is equal to any . To prove this, let and and are congruent to some multiple of a modulo p because they are derived from the sequence . So, if , then . We can rewrite this as . , so the previous equation would imply that . However, this cannot be true because and (meaning that p cannot divide z+v).
To review, none of the numbers are repeats. We also know that they all fall in the range , and there are of them. Thus the list is simply a re-arrangement of the sequence .
Then, take the sequence . Each term in this sequence must be greater than 0 and less than (because and ). This means that
Since , we can rewrite the equation above as a congruence:
Then, we can rewrite this as
Because each of the remainders is equivalent to exactly one of the terms in the sequence the product is equivalent to the product modulo p, so we can write
Simplifying this gives us
Then we can write . Thus, by Euler’s criterion, we get
The only possible values of a Legendre symbol are 1 ,0,-1, and the only possible values of . The only possible values of their difference are -2,0,2 and because they are equivalent modulo p, their difference must be equivalent to 0 modulo p. This means that the difference must be zero (note that this is essentially the method used in theorem 12). Thus, we get
Definition 9 For any number m, [m] equals the integer less than or equal to m and is known as the floor of m.
The floor function is used to round down. For example, [5.78]=5. If we rounded 5.78 to the nearest integer, we would get 6, but because we are rounding the down using the floor function, we get an answer of 5. Additionally, where r is the remainder when m is divided by q. For example, .
Consider some s that is equal to for any integer x. The average term in the sequence , and there are x terms in this sequence. Thus, . For example, . This result will be used in the proof of the following theorem.
The following theorem is essentially a sequel of Gauss’s lemma. It builds on the same idea and is extremely important to proving quadratic reciprocity.
Theorem 14 If p is an odd prime and (a,2p)=1, then .
Proof. We are going to build on the lemma of Gauss and show that the number x from the lemma is equal to t plus a multiple of 2, and since raising -1 to an even power results in 1, the result follows. We are going to calculate the sum in two different ways, and the equation between them will provide the relation we need. Recall the situation in the proof of Theorem 13: we have formed the products and taken their remainders mod p, arranged into according to whether they are greater than or less than . As shown in the previous proof, we know there are no repeats in this list and that is actually just a rearrangement of the list . More specifically, we will take each of the products ja and write it in the form according to the discussion after Definition 9. Those remainders greater than will be in the list and those remainders less than will be in the list and others will be among the . So,
(this equation is breaking up into its quotient and remainder) where runs overall values for which is defined and runs over all values for which is defined. The sequence has no repeats and is a rearrangement of the sequence , so we can write
and then we can break up into . So we get
Then, using subtraction, we get
is the sum of all integers between 1 and (inclusive), so we can write
This summation gives us
Then, simplifying this ( , using we get
Now we can outline two cases: if is odd, we get even, and so differs from by a multiple of 2, so, by Gauss’s Lemma,
If , then for all , so the quotients are all 0 . Thus in this case, using , we get . So
completing the proof.
This result has two aspects. First, we get an alternate expression for the number in the statement of Gauss’s lemma, valid for any odd number . This alternate expression is absolutely critical for our method of proving Quadratic Reciprocity. Secondly, we obtain the precise value of as a power of -1 , which we will simplify even further in the sequel. While this isn’t considered a part of the law, it’s still a useful result for simplifying Legendre symbols involving even numbers.
The following lemma simplifies the task of dealing with Legendre symbols involing two,
and its proof provides and example of a use case of theorem 14. \\
Lemma 15 if is an odd prime then when , and -1 when .
Proof. By theorem 14, we know that , so (mod 2) (because -1 to any even power is equal to 1). Then, we can multiply both sides of the congruence by 8 and adjust the modulus, giving us (mod 16). Then, we can plug in and . This means that when and when . Then, because 16 is divisible by 8 , we get when and when , completing the proof.
Law of Quadratic Reciprocity
Using the multiplicatively of Legendre symbols and factoring, we can find the value of any Legendre symbol (excluding , even those of the form where is not prime. We can do this by factoring into symbols of the form where is prime. The law of quadratic reciprocity states that unless both and are equivalent to 3 modulo 4 , in which case either or is equal to 1 while the other is not.
For example, take the Legendre symbol . Because (mod 4 ), we know that ; calculating the values of both Legendre symbols confirms this (both are equal to 1). While it is true in this case, a Legendre symbol and its reciprocal are not always equal. For example, take . Both 7 and 11 are equivalent to 3 modulo 4 , so . We confirm this by calculating the value of both Legendre symbols: (mod 11) while . So, and .
Theorem 16 Law of Quadrotic Reciprocity:
where and are distinct odd primes. Proof. With Gauss’s Lemma and its sequel (theorems 13 and 14), we have already laid most of the technical groundwork for the proof of Quadratic Reciprocity. What remains is comparatively simple, although it may be difficult to determine the motivation at first glance. For ease of reading, we will cover a brief outline of the proof beforehand. By Theorem 14. We know that where and we know that , where . Thus . We will mark out a rectangular grid of exactly points and divide it by a straight line into a subset with points and another subset with points. The result will then follow.
Let be the set of ordered pairs such that , and . The set is just a rectangular grid of lattice points in the first quadrant, with its bottom left corner at and its top right corner at . There are such values of and values of , meaning that this set has elements.
Imagine that all these points are plotted in the plane; we will divide them into those that lie above the line and those that lie below. Separate into two subsets, and , where contains all points such that (those that lie below the line) and contains all points such that (those that lie above the line). If , then, by Euclid’s lemma, . cannot divide because they are distinct primes, if , then ; however, this cannot be true due to the range restriction placed on (because is less than ). If is in the set , then and , just by the range restriction on and rearrangement of the inequality . Also, any point satisfying these inequalities belongs to , so the number of points in set is equal to
We get this by looking at the graph formed by inequalities that define . The number of integers in the interval is equal to the number of integers in the range because is the largest integer in that range. 50 the number of integers in is . Then, we sum up the value of for every -value in the interval to get the total amount of elements in subset Then, we can set up in the same way, so consists of ordered pairs such that and . Since is defined by reversing the roles of and , we know that the number of points in is equal to
Recall that the total number of points in is as calculated in the beginning of this proof. Thus, the number of ordered pairs in the set is equal to
Then, we can raise -1 to the power of both sides, giving us Finally, by theorem 14, we get
Finally, by theorem 14, we get
One of the most convenient uses for this theorem is the simplification of complex Legendre Symbols. Returning to our previous example, take . This integer is extremely large, having over digits. Using the law of quadratic reciprocity, we can easily calculate the value of the Legendre . Using Euler’s criterion, we would have to calculate value of which is not feasible. By the law of quadratic reciprocity, . For the rest of this calculation, we will let . Then, because , and . Additionally, , so , meaning that can be written in the form . This means that is an odd number. Thus, because is equal to the product of two odd numbers, meaning that it must be odd, and -1 to an even power is always equal to -1 . Finally, we can write . Although this calculation was a little tedious, it was made possible by the law of quadratic reciprocity.
In this section, we present a self-contained proof of Hensel’s lemma, which provides us a method of “lifting” the solutions of congruence modulo some prime to solutions of a congruence modulo for some integer . Before we derive the main result, we develop a few lemmas that are important for dealing with polynomials. This section, unlike the others in this text, includes calculus. Recall that if is a function, then is the th derivative (this notation will be used later in this section).
The following results prowdes a method of proving two functions are equal as long as all their derivatives are equal. It will be used in the proof of Hensel’s lemma.
Lemma 17 suppose that and are two polynomials with degrees less than or equal to . If there is point such thot for all values of , then the polynomiols and are equal.
Proof. If , then both and are constants, so if they are equal at one point, they are equal everywhere. Then, assume that this lemma holds for polynomials of degrees less than or equal to . If the polynomials and are of degrees less than or equal to , then polynomials and are of degrees less than or equal to . Then, let and . polynomials and are of degrees less than or equal to , and
for all values . By induction, we know that , so that , meaning that and can only differ by a constant. This means that for some constant . However, , so , so . Thus, , completing the proof.
The following expansion is a familiar expansion from calculus; however, the proof in this text will remain purely algebraic. \
Lemma 18 For any polynomial with degree ,
for all values of , given that is any real number.
Proof. Let . This means that is a polynomial of degree (Because will be of degree when ). Then, to prove this lemma, we need to prove that for all values (because lemma 17 will teccosh. This means that
Because this works for , lemma 17 tells us that , completing the proof.
The product of any two consecutive integers is always even because the two integers must be even. By the same logic, the product of any three consecutive integers must always be divisible by because one of the integers must be even, and one of the other integers must be divisible by 3 . The following result is a generalization of this observation, although the proof is different. This lemma will be used to prove that the coefficients of a polynomial used in the proof of Hensel’s lemma are whole numbers.
Lemma 19 The product of any consecutive positive integers is alwoys divisible by !
Proof. We can express the product of any consecutive integers as 2)…- where is the first term in the sequence of consecutive integers. If the product of consecutive integers is divisible by !, then
must be an integer.
so we can rewrite the previous fraction as
This fraction is equal to the binomial coefficient , meaning it must be equal to an integer because binomial coefficients are always integers.
Hensel’s lemma enables us to “extend” the solutions of congruences so that they apply to congruences with a modulus of a higher degree. This lemma makes the process of finding the solution to congruences with a modulus of the form much more efficient. \
Theorem 20 Hensel’s Lemma: Let be o polynomial with integrol coefficients of degree , and let and be positive integers such that . If , there must be a unique such that
Proof. Using the Taylor expansion (lemma 18) to rewrite , we get
where is the point we are expanding at. We can then rewrite this as
We want to find some such that . Then, to find the value of , we can plug into the Taylor expansion above, giving us
We want to be congruent to 0 (mod ), so we can write
If we can find some value of for which this is true, we will have proved Hensel’s lemma. Every term in this Taylor expansion beyond the second term has as a divisor, and , so we can rewrite the sum of every term in the sequence beyond the second term as
If is an integer, then the sum above must be congruent to 0 ( . To prove that is an integer, let be a term in . The th derivative of is equal to . By lemma 19, the product of any consecutive terms must be divisible by !, so must be divisible by !, proving that is an integer. This means that all the terms in the Taylor sequence beyond the second term are congruent to , so we can write
Then, we can write
substituting in gives us
Some value of that satisfies this congruence will exist as long as
not being equivalent to also guarantees the existence of its inverse modulo (referred to later in this section as )
The main use of Hensel’s lemma is to solve congruences with moduli of a high degree. Given the congruence , as long , we can find some such that using the values of , and . As established in the proof of Hensel’s lemma,
To find the value of , normally, we would divide both sides of the congruence by , but, in this case, we cannot guarantee that is a whole number. Instead, because we are working with congruences, we can multiply both sides of the congruence by some such that (mod p). This gives us
and , so we get
Then, we can multiply both sides of the congruence by and add to both sides, giving us
This congruence is satisfied if both sides of the congruence are equal, so when trying to lift a congruence, we use the equation
This equation is quite useful as it allows us to “lift” the solution of congruence of some degree to a higher degree. With repeated use of this process, you can find a solution of congruence with a modulus of any degree without having to test every possible value. For example, consider the congruence
To find the solutions to this congruence, we would normally have to plug in all values between 0 and 27 . Hensel’s lemma makes this process much easier, requiring us to only plug in values between 0 and 3.
The only solution to the congruence modulo 3 is 1, so we can lift this root to find solutions to the same congruence modulo 9 and 27 . Normally, we would have to find the inverse of modulo 3, but , so . Then, we get , meaning that 4 is a solution to the congruence . Then, we can lift this solution again; and . This inverse of f'(4) modulo 9 is 4, so we get , meaning that 13 is a solution to the congruence . We can test this by plugging 13 into the congruence, giving us . It is important to note that we can only lift roots if .
It is remarkable that such varied and rich results can be derived using very little beyond ordinary addition and multiplication. The proofs of quadratic reciprocity given here are quite elementary, given that they require no complex analysis. However, as shown by this paper, they involve the use of extensive mathematical terminology and inference. From modular arithmetic to Quadratic Reciprocity, the study of integers and number theory involves the use of a variety of methods and constructs.
Number theory is not a “solved” field; many unsolved problems are still present (such as the Riemann zeta hypothesis), so the reader should not hesitate to pursue number theory further. In addition, there are many topics in number theory, like the Chinese remainder theorem and linear congruences, that haven’t been covered in this text, which can be found in works like Introduction to Analytic Number Theory by Tom. M. Apostol2.
Readers interested in further pursuing the topics presented in this paper should consult books like “An Introduction to the Theory of Numbers” by Ivan Nivan, Hubert S. Zuckerman, and Hugh L. Montgomery, and “Algebraic Number Theory” by Kenneth Ireland and Michael Rosen. The present paper has not covered some fundamental parts of number theory (namely the prime number theorem), but the reader can find an in-depth discussion of these un-solved topics in books like Unsolved Problems in Number Theory3.
I would like to acknowledge and thank Doctoral Student at Cambridge University (UK) Lukas Kofler for his advice and guidance in writing this paper. Additionally, I would like to thank Mr. Cryster for his generous assistance in composing and refining this paper.
- Ivan Niven and Herbert S. Zuckerman, An introduction to the theory of numbers, 1960. [↩]
- A. Tom M., Introduction to Analytic Number Theory | SpringerLink, https://link.springer.com/book/10.1007/978-1-4757-5579-4. [↩]
- R. K. Guy, Unsolved Problems in Number Theory, Springer, New York, NY,2004, pp. 1–2. [↩]