Notes on Elementary Number Theory
Last Modified 2022-06-06
In these notes, we assume that the reader is familiar with the set of integers, denoted by , along with the unary operation of negation and the binary operations of addition and multiplication . As is usual in higher mathematics, we will not explicitly write the multiplication sign ; instead, we denote the product of and simply by juxtaposition, as in . We will also write to abbreviate the expression .
We state without proof the following facts about the arithmetic operations on . (Giving full proofs of these statements would require us to work with rigorous, axiomatic definitions of the set 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 .
- Commutative property of addition: .
- Cancellation property of addition: if and only if .
- Additive identity property: .
- Additive inverse property: .
- Commutative property of multiplication: .
- Cancellation property of multiplication: If and , then .
- Multiplicative identity property: .
- Zero-product property: if and only if or .
- Distributive property: .
Definition: Divisibility,
Let . We say that divides , denoted by , if there exists an integer such that .
Elementary Properties of Divisibility
Theorem: The following statements hold for all .
- and .
- if and only if .
- If and , then .
- If or , then .
- If and , then .
Proof: Let be given.
- .
- for all , so we can write for some if and only if .
- If and for some , then .
- If for some , then . Similarly, if for some , then .
- If and for some , then . ∎
Definition: Modular Congruence,
Let . We say that is congruent to modulo , denoted by , if .
In this section, we will study the theory of quadratic residues, which answers the following question: when does an element of have a square root in ?
Definition: Quadratic Residue
Let . We say that is a quadratic residue modulo if there exists an integer such that .
Quadratic Residues of Quadratic Forms
Theorem: Let . If and or , then is a quadratic residue modulo .
Proof: By swapping and if necessary, we may assume without loss of generality that . This implies that has a modular inverse satisfying . It follows that:
Thus, we have proven , which shows that is a quadratic residue modulo . ∎
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):
However, the following equations are not considered Diophantine equations, even if we stipulate that we are only interested in integer solutions:
Note that, by moving all terms to the left-hand side, every Diophantine equation can be written in the form
for some polynomial . Unless otherwise specified, we will assume that all Diophantine equations are presented in this form.
Definition: Solution, Satisfiable, Unsatisfiable
Let and . A solution of the Diophantine equation is a point for which . We say that the Diophantine equation is satisfiable if it has a solution in ; otherwise, we say that the equation is unsatisfiable.
Definition: Linear Variable, Occurs Linearly
Let . We say that a polynomial contains a linear variable if, after some permutation of the variables , we can write in the form
for some , , and . If this is the case, then we say that the variable occurs linearly in .
Note that this notion of “linearity” is not equivalent to having degree in , which is necessary but not sufficient.
If a polynomial contains a linear variable, say , then the corresponding Diophantine equation
is satisfiable if and only if it is possible for to be a multiple of . This can be tested algorithmically by computing modulo for all values of .
Definition: Divisible Variable, Occurs Divisibly
Let . We say that a polynomial contains a divisible variable if, after some permutation of the variables , we can write in the form
for some and . If this is the case, then we say that the variable occurs divisibly in .
If a polynomial contains a divisible variable, say , then the corresponding Diophantine equation
is satisfiable if and only if it is possible for to be a (positive or negative) divisor of . This reduces the original Diophantine equation to a finite disjunction of Diophantine equations in one fewer variable, one for each divisor of .