# 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

**negation***and*

**addition**

**multiplication**We state without proof the following facts about the arithmetic operations

**Elementary Properties of Integer Arithmetic**

**Theorem:** The following statements hold for all

**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:**$a b = b a$ .**Cancellation property of multiplication:**If$ab = ac$ and$a \ne 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 \mid b$**

Let , denoted by

**Elementary Properties of Divisibility**

**Theorem:** The following statements hold for all

$1 \mid n$ and$-1 \mid n$ .$0 \mid n$ if and only if$n = 0$ .- If
$k \mid m$ and$k \mid n$ , then$k \mid m + n$ . - If
$k \mid m$ or$k \mid n$ , then$k \mid mn$ . - If
$k \mid m$ and$m \mid n$ , then$k \mid n$ .

*Proof:* Let

$n = 1n = (-1)(-n)$ .$0a = 0$ for all$a \in \Z$ , so we can write$n = 0a$ for some$a \in \Z$ if and only if$n = 0$ .- If
$m = ak$ and$n = bk$ for some$a, b \in \Z$ , then$m + n = (a + b)k$ . - If
$m = ak$ for some$a \in \Z$ , then$mn = (an)k$ . Similarly, if$n = bk$ for some$b \in \Z$ , then$mn = (mb)k$ . - If
$m = ak$ and$n = bm$ for some$a, b \in \Z$ , then$n = (ab)k$ . □

**Definition: Modular Congruence, $x \equiv y \pmod{k}$**

Let , denoted by

In this section, we will study the theory of quadratic residues, which answers the following question: when does an element of

**Definition: Quadratic Residue**

Let if there exists an integer

**Quadratic Residues of Quadratic Forms**

**Theorem:** Let

*Proof:* By swapping

Thus, we have proven

**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

**Definition: Solution, Satisfiable, Unsatisfiable**

Let * solution* of the Diophantine equation

*if it has a solution in*

**satisfiable***.*

**unsatisfiable****Definition: Linear Variable, Occurs Linearly**

Let * linear variable* if, after some permutation of the variables

for some * occurs linearly* in

Note that this notion of “linearity” is **not** equivalent to

If a polynomial

is satisfiable if and only if it is possible for

**Definition: Divisible Variable, Occurs Divisibly**

Let * divisible variable* if, after some permutation of the variables

for some * occurs divisibly* in

If a polynomial

is satisfiable if and only if it is possible for