In these notes, we assume that the reader is familiar with the set of integers, denoted by Z:={…,−2,−1,0,1,2,…}, along with the unary operation of negation−:Z→Z and the binary operations of addition and multiplication+,×:Z×Z→Z. As is usual in higher mathematics, we will not explicitly write the multiplication sign ×; instead, we denote the product of x and y simply by juxtaposition, as in xy. We will also write x−y to abbreviate the expression x+(−y).
We state without proof the following facts about the arithmetic operations +,−,× on Z. (Giving full proofs of these statements would require us to work with rigorous, axiomatic definitions of the set Z and the functions +, −, and ×, which are surprisingly both difficult to construct and cumbersome to understand. We refer the interested reader to the Wikipedia article on the construction of the integers.)
Elementary Properties of Integer Arithmetic
Theorem: The following statements hold for all a,b,c∈Z.
Commutative property of addition:a+b=b+a.
Cancellation property of addition:a+b=a+c if and only if b=c.
Additive identity property:a+0=a.
Additive inverse property:a−a=0.
Commutative property of multiplication:ab=ba.
Cancellation property of multiplication: If ab=ac and a=0, then b=c.
Multiplicative identity property:1a=a.
Zero-product property:ab=0 if and only if a=0 or b=0.
Distributive property:a(b+c)=ab+ac.
Definition: Divisibility, a∣b
Let a,b∈Z. We say that a divides b, denoted by a∣b, if there exists an integer c∈Z such that b=ac.
Elementary Properties of Divisibility
Theorem: The following statements hold for all k,m,n∈Z.
1∣n and −1∣n.
0∣n if and only if n=0.
If k∣m and k∣n, then k∣m+n.
If k∣m or k∣n, then k∣mn.
If k∣m and m∣n, then k∣n.
Proof: Let k,m,n∈Z be given.
n=1n=(−1)(−n).
0a=0 for all a∈Z, so we can write n=0a for some a∈Z if and only if n=0.
If m=ak and n=bk for some a,b∈Z, then m+n=(a+b)k.
If m=ak for some a∈Z, then mn=(an)k. Similarly, if n=bk for some b∈Z, then mn=(mb)k.
If m=ak and n=bm for some a,b∈Z, then n=(ab)k. □
Definition: Modular Congruence, x≡y(modk)
Let x,y,k∈Z. We say that x is congruent to y modulo k, denoted by x≡y(modk), if k∣x−y.
In this section, we will study the theory of quadratic residues, which answers the following question: when does an element of Z/pZ have a square root in Z/pZ?
Definition: Quadratic Residue
Let x,k∈Z. We say that x is a quadratic residue modulo k if there exists an integer y∈Z such that x≡y2(modk).
Quadratic Residues of Quadratic Forms
Theorem: Let a,b,c,k,x,y∈Z. If k∣ax2+bxy+cy2 and gcd(k,x)=1 or gcd(k,y)=1, then b2−4ac is a quadratic residue modulo k.
Proof: By swapping x and y if necessary, we may assume without loss of generality that gcd(k,y)=1. This implies that y has a modular inverse z∈Z satisfying yz≡1(modk). It follows that:
Thus, we have proven b2−4ac≡(2axz+b)2(modk), which shows that b2−4ac is a quadratic residue modulo k. □
Definition: Diophantine Equation
A Diophantine equation is a polynomial equation with integer coefficients, in any (finite) number of variables, for which we seek integer solutions.
For example, the following equations could all be Diophantine equations (if we add the stipulation that we are looking for integer solutions):
x+y=5a2+b2=c23x2y4+10z(5−xz)=6xyz2
However, the following equations are not considered Diophantine equations, even if we stipulate that we are only interested in integer solutions:
2x+y=31sin(a)+exp(b)=041x2+πy3z=2z
Note that, by moving all terms to the left-hand side, every Diophantine equation can be written in the form
P(x1,…,xn)=0
for some polynomial P∈Z[x1,…,xn]. Unless otherwise specified, we will assume that all Diophantine equations are presented in this form.
Definition: Solution, Satisfiable, Unsatisfiable
Let n∈N and P∈Z[x1,…,xn]. A solution of the Diophantine equation P(x1,…,xn)=0 is a point (s1,…,sn)∈Zn for which P(s1,…,sn)=0. We say that the Diophantine equation P(x1,…,xn)=0 is satisfiable if it has a solution in Zn; otherwise, we say that the equation P(x1,…,xn)=0 is unsatisfiable.
Definition: Linear Variable, Occurs Linearly
Let n∈N. We say that a polynomial P∈Z[x1,…,xn] contains a linear variable if, after some permutation of the variables x1,…,xn, we can write P(x1,…,xn) in the form
P(x1,…,xn)=ax1x2j2⋯xkjk+Q(xk+1,…,xn)
for some a∈Z, k,j2,…,jk∈N, and Q∈Z[xk+1,…,xn]. If this is the case, then we say that the variable x1occurs linearly in P.
Note that this notion of “linearity” is not equivalent to x1 having degree 1 in P, which is necessary but not sufficient.
If a polynomial P∈Z[x1,…,xn] contains a linear variable, say x1, then the corresponding Diophantine equation
P(x1,…,xn)=ax1x2j2⋯xkjk+Q(xk+1,…,xn)=0
is satisfiable if and only if it is possible for Q(xk+1,…,xn) to be a multiple of a. This can be tested algorithmically by computing Q(xk+1,…,xn) modulo a for all values of xk+1,…,xn∈{0,…,a−1}.
Definition: Divisible Variable, Occurs Divisibly
Let n∈N. We say that a polynomial P∈Z[x1,…,xn] contains a divisible variable if, after some permutation of the variables x1,…,xn, we can write P(x1,…,xn) in the form
P(x1,…,xn)=x1Q(x2,…,xn)+a
for some a∈Z and Q∈Z[x2,…,xn]. If this is the case, then we say that the variable x1occurs divisibly in P.
If a polynomial P∈Z[x1,…,xn] contains a divisible variable, say x1, then the corresponding Diophantine equation
P(x1,…,xn)=x1Q(x2,…,xn)+a=0
is satisfiable if and only if it is possible for Q(x2,…,xn) to be a (positive or negative) divisor of a. This reduces the original Diophantine equation P(x1,…,xn)=0 to a finite disjunction of Diophantine equations Q(x2,…,xn)−b=0 in one fewer variable, one for each divisor b of a.