Number Theory

Based on 21-127 Concepts of Mathematics

The division theorem states that for integers $a, b \in \mathbb{Z}$ with $b \neq 0$, there exists unique pair $(q,r) \in \mathbb{Z}^2$ s.t.
$$(a=qb+r) \wedge (0 \leq r< |b|)$$
We often understand $q$ as the quotient and $r$ as the remainder when $a$ is divided by $b$.

Sketch of proof: existence part by constructing the set $X = { n \in \mathbb{N} \mid \exists q \in \mathbb{Z}, a = qb+n }$ and using WOP to show it has a least element and show that it is less than $|b|$. Uniqueness part by assuming two pairs fit the definition and showing they are equal.

We write $b \mid a$ to say $a \in \mathbb{Z}$ is divisible $b \in \mathbb{Z}$.

When $b \neq 0$, $b \mid a$ iff the remainder when $a$ divided by $b$ is equal to $0$.

Take $a, b \in \mathbb{Z}$.

A common divisor of $a$ and $b$ is $c \in \mathbb{Z}, (c \mid a \wedge c \mid b)$. Viz. an integer that divides both $a$ and $b$.

A greatest common divisor of $a$ and $b$ is $d \in \mathbb{Z}$ s.t.

• $d$ is a common divisor of $a$ and $b$ viz. $d \mid a \wedge d \mid b$
• $d$ can be divided by all other common divisors $\forall c \in \mathbb{Z}, ((c \mid a \wedge c \mid b) \Rightarrow c \mid d)$.

Take $a, b \in \mathbb{Z}$. If $d_{1}$ is a GCD, then $-d_{1}$ is a GCD. In other words, if $d_{1}$ and $d_{2}$ are GCDs, then $d_{1} = d_{2} \vee d_{1} = -d_{2}$.

(Proof should be straightforward)

But then it means that $(a,b)$ has a unique non-negative GCD. We write $\text{gcd}(a, b)$ to refer to the non-negative GCD.

1. Show that an expression satisfies the definition of a GCD

Theorem: given $a, b, q, r \in \mathbb{Z}$, $a=qb+r \Rightarrow \text{gcd}(a,b) = \text{gcd}(b, r)$. Note that $q$ and $r$ do not have to be the quotient and remainder. This theorem allows us to “reduce” a gcd expression (and give rise to the Euclidean algorithm).

Euclidean algorithm can be used to find gcd! It’s given as follows

int Euclidean(int a, int b) {
	// clean up
	if (a < 0) a = -a;
	if (b < 0) b = -b;
	if (a < b) { 
		int temp = a; a = b; b = temp; // swap the vars
	}

	// do stuff
	if (b == 0) return a;
	int r = a % b;
	Euclidean(b, r);
}

Let $a, b \in \mathbb{Z}$. We say they are coprime (write $a \perp b$) if $\text{gcd}(a, b) = 1$.

Lemma: $n \perp n +1$ for all $n \in \mathbb{Z}$. Proof we can instead show $nx+(n+1)y=1$ has integer solution. Well, $n(-1)+(n+1)(1) = 1$ works $\square$.

Useful:
$a \perp b \Leftrightarrow$

• $\text{gcd}(a, b) = 1$
• $a$ and $b$ have no common prime divisor
• $a$ has multiplicative inverse mod $b$
• $b$ has multiplicative inverse mod $a$

Equations that take the form of $ax + by = c$ where $a,x,b,y,c \in \mathbb{Z}$.

Let $a,b,c \in \mathbb{Z}$. The diophantine equation $ax+by=c$ has integer solution(s) iff $\text{gcd}(a,b) \mid c$.

This helps us to find a solution for $ax + by = c$ with $a,b,c \in \mathbb{Z}$.

The algorithm:

1. Do the Euclidean algorithm but keep track of remainders.
2. If $\text{gcd}(a,b) \mid c$, continue. Else, break since no solution.
3. Isolate remainders and substitute back repeatedly.
4. Scale equation to get $c$ on one side.

Let $p \in \mathbb{Z}$

$p$ is ring theoretically prime if $|p| > 0$ and $\forall a,b \in \mathbb{Z}, p \mid ab \Rightarrow (a \mid a \vee p \mid b)$.

$p$ is irreducible prime if $|p| > 0$ and $\forall a,b \in \mathbb{Z}, p = ab \Rightarrow (a = ± 1 \vee b = ± 1)$. Alternatively, $\forall a \in \mathbb{Z}, a \mid p \Rightarrow (a = ± 1 \vee a = ± p)$.

Useful: it follows that a positive prime $p > 0$ is irreducible iff its only positive divisors are $1$ and $p$.

Informally, it says that every non-zero integer have a unique prime factorisation.

Formally, let $n \in \mathbb{Z}$ with $n \neq 0$.

Then $n = up_{1}p_{2}\dots p_{r}$ s.t.

• $r \in \mathbb{Z}$
• $u \in {-1,1}$
• $p_{i}$ is for all $1\leq i \leq r$
• $0\leq p_{1}\leq p_{2}\leq\dots\leq p_{r}$

The expansion $up_{1}p_{2}\dots p_{r}$ is the prime factor expansion of $n$. And $(u, p_{1},p_{2},\dots, p_{r}) \in \mathbb{Z}^{r+1}$ is unique.

For example, $-12 = (-1) \cdot 2 \cdot 2 \cdot 3$.

Proof: Let $X$ be set of $r \in \mathbb{N}$ primes. So $X = {p_{1}, \dots ,p_{r}}$. It’s sufficient to find another prime $p$ that is not in $X$. Well, let $n$ be the product of all primes in $X$. Then $n+1 \perp n$ so $n+1$ have no common prime factor with $n$. But $n+1 \geq 2$ and so by FTA $n+1$ has some prime factor that is not in $X$. So we found a new prime.

(For programmers, forget about the % operation for now)

Let $a, b, n \in \mathbb{Z}$, we say that $a$ is congruent to $b$ modulo $n$ if either (note these imply each other):

• $n \mid a - b$
• $n \mid b-a$
• $a = kn + b$ for some $k \in \mathbb{Z}$

We denote this by writing $a \equiv b \text{ mod } n$ or $a \equiv_{n} b$. We call the number $n$ the modulus of the congruence.

Fun fact $\equiv_{n}$ is an equivalence relation. See Pure Math - Relations.

Unlike normal arithmetic with $=$, there are certain things cannot do with $\equiv_{n}$. Let $x, y, a, b \in \mathbb{Z}$ with $x \equiv_{n} y$ and $a \equiv_{n} b$, here are three allowed operations:

1. addition: $x + a \equiv_{n} y + b$
2. multiplication: $xa \equiv_{n} yb$
3. subtraction: $x - a \equiv_{n} y - b$ (basically adding the after multiplying $-1 \equiv_{n} -1$)

Warning: division and square root don’t always work.

Let $a, n \in \mathbb{Z}$, the multiplicative inverse of $a$ mod $n$ is $u \in \mathbb{Z}$ such that $au \equiv_{n} 1$. Think of this as the number that “cancels” the $a$ in a congruence expression (e.g. $ax \equiv_{n} b \Leftrightarrow x \equiv_{n} ub$ for some $b \in \mathbb{Z}$).

Theorem: such multiplicative inverse exists only iff $a \perp n$. (There is a short proof using Bézout)