Number Theory – Fundamental Theorem of Arithmetic.

This is an exposition of the main results in ch1, ch2 of George Andrew’s book on Number Theory. Presentation will discuss the Basis Representation Theorem, Euclid’s Division Lemma, Divisibility, greatest common divisors, solutions to linear equations and the main result of ch2, the claim that every positive integer is a unique product of prime factors.

First, the BRT is a basic result from number theory. For the purposes of exposition, all variables are assumed to be integer-valued.

theorem: [basis representation theorem] Let $k > 1$ be a given base. For any $n > 0$ there is a unique base $k$ representation $a_0,\ldots,a_s$ , where $a_i \in 0..(k-1)$ such that

$n = \sum_{i = 0..s} a_i k^i$

proof:

Note that y $1 = 1 k^{0}$ has a unique representation in base $k$ . Assume the representations of $1,\ldots,n-1$ in base $k$ exist and are unique. Let $n-1 = \sum_{i = 0..s} a_i k^i$ . Then

$n = n-1 + 1 = \sum_{i = 0..s} a_i k^i + 1$

Let $j$ be the first index for which $a_j < k-1$ and for all $h < j, a_h = k-1$ . Then

$a_j k^j + (k-1) k^{j-1} + \ldots + (k-1) k^0 + 1 = (a_j + 1) k^j$ . Hence

$n = \sum_{i = j+1..s} a_i k^i + (a_j +1) k^j$

and so $n$ has a representation in base $k$ . To establish uniqueness, suppose that $n$ has two distinct representations in base $k$ .

$n = \sum_{i=0..m} a_i k^i = \sum_{i = 0..p} b_i k^i$ .

Where $m \ge p$ . if $m > p$ ,

$0 = \sum_{i=p+1..m} a_i k^i + \sum_{i = 0..p} (a_i - b_i) k^i$

$\sum_{i=p+1..m} a_i k^i = \sum_{i = 0..p} (- a_i + b_i) k^i$

Note that $\sum_{i=p+1..m} a_i k^i \ge k^{p+1}$ . Since $-k + 1 \le a_i - b_i \le k-1$ when $i = 0..p$ and $k^w - 1 = \sum_{i = 0..w-1} (k-1) k^i$ ,

$\text{LHS} \ge k^{p+1} > \text{RHS}$

which is false. So $m = p$ . Assume wlog that $a_m \ge b_m$ . If $a_m > b_m$ , then

$(a_m - b_m) k^m = \sum_{i=0..m-1} (b_i - a_i) k^i$

but $(a_m - b_m) k^m \ge k^m > \sum_{i = 0..m-1} (k-1) k^i \ge \sum_{i=0..m-1} (b_i - a_i) k^i = (a_m - b_m) k^m$ , which is false. So $a_m = b_m$ , and by induction $a_i = b_i$ for all $i = 0..m$ . Hence the representation is unique.

A result sometimes useful

lemma: if $n,m > 0$ and $m > 1$ then $m^n > n$ and $\frac{1}{n} m^n > m + 1/n - 1$

Since $m > 1$ it follows by induction that for all $k \ge 0$ , $m^k > 1$ . Hence by induction $n \le (m - 1) n = (m-1) \sum_{i=0..n-1} 1 < (m-1) \sum_{i=0..n-1} m^i = m^n - 1 < m^n$

Euclid’s Division Lemma

theorem: [Euclid] Let $k > 0$ . For any $j$ there is a unique quotient $q$ and remainder $r \in 0..k-1$ such that $j = qk + r$ .

Either $k = 1$ or $k > 1$ . If $k = 1$ then $j = q + 0$ and so the claim is valid. If $k > 1$ , if $j > 0$ , then by the BRT there is a unique representation

$j = \sum_{i=0..s} a_i k^i = k \sum_{i =1..s} a_i k^{i-1} + a_0$ .

Choose $q = \sum_{i =1..s} a_i k^{i-1}$ and $r = a_0$ , and so there is a quotient $q$ and remainder $r$ such that $j = kq + r$ . If there is a second representation $j = kq' + r'$ , then $k(q' - q) = r - r'$ . But $|r - r'| \le k-1$ and so $k|q' - q|<k$ and so $q = q'$ and $r = r'$ , so the second representation is identified with the first representation (ie. representation is unique).

If $j = 0$ , then $0 = 0 k + 0$ is the only possible representation satisfying the constraints and so is unique.

If $j < 0$ then $-j > 0$ and by the prior result there is a unique $q,r$ such that $-j = kq + r$ . But then $j = k(-q) + (-r)$ . If $r = 0$ the representation exists and is unique. If $r < 0$ , then $k - r \in 0..k-1$ and $j = k(-q-1) + k-r$ is a unique representation satisfying the constraints.

Divisibility

definition: [divisor] Let $a | b$ iff $a$ divides $b$ . That is if $ka = b$ for some integer $k$ . If $a | b$ then $a$ is said to be a divisor or $b$ .

Note that divisibility is not independent of the sign of the numbers, since $a | b \iff -a | b \iff a | -b \iff -a | -b$ and to answer questions about divisibility it is sufficient to consider only non-negative numbers.

Note that $1 | a$ for any integer $a$ . Furthermore $|$ is a binary relation on integers that is reflexive, transitive and anti-symmetric (if restricting to positive numbers):

$a | a$ since $a = 1 a$
if $a | b | c$ then $a | c$ since $ka = b$ and $mb = c$ and so $mka = c$ .
$a | b | a$ implies $a = b$ since $ka = b, lb = a$ and so $kla = a$ , so $kl = 1$ and so $k = l = 1$ .

So $|$ is a partial order on positive integers.

definition: [greatest common divisor] Given two integers $a,b$ the greatest common divisor $d = gcd(a,b)$ is the positive integer such that

$d | a$ and $d | b$
if $d' | a$ and $d' | b$ then $d' | d$ .

lemma: if $a,b$ are positive integers then the gcd exists and is unique.

for uniqueness, consider two gcds $d,d'$ . Then $d' | d | d'$ and so $d = d'$ .

for existence, EL may be used. Suppose $a > b$ . Choose base $k_0 = a$ . Note that there are unique $q_0,r_0$ such that $a = q_0 k_0 + r_0$ where $q_0 > 0$ and $r_0 \in 0..k_0-1$ . If $r_0 > 0$ define $k_1 = r_0$ and by EDL there are unique $q_1,r_1$ such that $k_0 = q_1 k_1 + r_1$ and $r_1 \in 0..r_0 - 1$ . Note that this process can be repeated at most $i \le r_0$ steps until $k_{i-1} = q_i k_i$ . But then $k_i | k_{i-1}$ . Since

$k_{i-2} = q_{i-1} k_{i-1} + r_{i-1} = q_{i-1} k_{i-1} + k_i$ it follows that $k_i | k_{i-1},k_{i-2}$ and by induction, $k_i | k_0 = a$ and $k_i | b$ . Hence $k_i$ is a common divisor of $a,b$ .

To estalish it is the greatest such divisor, suppose $d | a,b$ . Then $d | k_0,k_1$ and by induction $d | k_0,\ldots.k_i$ . Hence $d | k_i$ and so $k_i = gcd(a,b)$ .

example: gcd(341,527) = 31

$527 = 1\cdot 341 + 186$

$341 = 1\cdot 186 + 155$

$186 = 1\cdot 155 + 31$

$155 = 5\cdot 31$

corollary: if $d = gcd(a,b)$ then there are $x,y$ such that $ax + by = d$

Define $x_1 = -q_0$ and $y_1 = 1$ . Note that $k_1 = 1\cdot b +(-q_0) a = ax_1 + by_1$ . Assume that for all $h \le j$ , $k_h = x_h a + y_h b$ . Define $x_{j+1} = x_{j-1} -q_j x_j$ and $y_{j+1} = y_{j-1} - q_j x_j$ . Then

$k_{j+1} = k_{j-1} - q_j k_j = a(x_{j-1} -q_j x_j) + b(y_{j-1} - q_j x_j) = ax_{j+1} + by_{j+1}$

Since $d = k_i$ , by induction the claim is valid.

example: determine $x,y$ such that $341x + 527y = 31$ .

$186 = 527 - 341$

$155 = 341 - 186 = (-1) \cdot 527 + 2 \cdot 341$

$31 = 186 - 155 = (2) \cdot 527 + (-3) \cdot 341$

corollary: there are $x,y$ such that $ax + by = c$ iff $gcd(a,b) | c$ .

Let $d = gcd(a,b)$ . Then there are $x,y$ such that $ax + by = d$ . If $d | c$ , then $dk = c$ and so $axk + bky = kd = c$ and sufficiency is demonstrated. For necessity, suppose that there are $x,y$ such that $ax + by = c$ . Since $a = dk$ and $b = dh$ , it follows that $dkx + dhy = c$ , and so $d | c$ , establishing necessity.

definition: [prime number] A positive number distinct from $1$ is a prime number if $d | p$ iff $d = 1$ or $d = p$ .

definition: [coprime/relatively prime] Two numbers are coprime if $gbd(a,b) = 1$ .

The next result says that factors coprime with a candidate divisor can be deleted in a test for divisbility.

lemma: If $c | ab$ and $c,a$ are coprime, then $c | b$ .

Since $a,c$ are coprime, there are $x,y$ such that $ax + cy = 1$ . But then $ab x + c(by) = b$ and so $gcd(ab,c) | b$ . But if $c | ab$ , then $c = gcd(ab,c)$ and so $c | b$ .

corollary: of $p$ is prime and $p | ab$ and $p \not | a$ then $p | b$ .

If $p$ is not a divisor of $a$ then the common divisors of $a$ and $p$ is contained in the intersection of a set not containing $p$ and a set consisting of only $p$ and $1$ , that is the set $\{1\}$ . Hence $a,p$ are coprime and so by prior lemma $p | b$ .

corollary: when $p | a_1 \ldots a_n$ then $p | a_i$ for some $i = 1..n$ .

proof: either $p | a_1$ or $p \not | a_1$ . In the latter case $p | a_2,\ldots a_n$ . Repeating this analysis, in the latter case either $\exists i < j$ such that $p | a_j$ or $p | a_{j+1} \ldots a_n$ . At the final step, either $\exists i < n$ such that $p | a_i$ or $p | a_n$ . Hence the claim of the corollary is valid.

Linear Diophantine Equation

A linear diophantine equation is an linear equation whose terms are all integers:

$ax + by = c$ . A solution is identified with the equation specified by integers $a,b,c$ is the pair $x,y$ satisfying the equation.

The approach to solving this type of equation is to use the fact that if $ax + by = c$ , then $gcd(a,b) | c$ . That is, if $x,y$ is a solution, then $d= gcd(a,b) | c$ . This condition is independent of the solution, meaning that no solution exists if the divisibility condition is not satisfied. If satisfied, then there is an integer $k$ such that $c = dk$ and we may identify a solution $x_0,y_0$ such that $ax_0 + by_0 = kd = c$ . But for any other solution,

$ax + by = c = ax_0 + by_0$

$a(x - x_0) = b(y_0 - y)$

$a/d(x - x_0) = b/d (y_0 - y)$

since $a/d,b/d$ are coprime, there is an integer $t$ such that $x - x_0 = b/d \cdot t$ . But then $a/d \cdot b/d \cdot t = b/d (y_0 - y)$ , and so $-a/d \cdot t = y - y_0$ . But since

$a \left(x_0 + b/d \cdot t \right) + b \left(y_0 - a/d \cdot t \right) = c$

every value of $t$ results in a solution.

Fundamental Theorem of Arithmetic

theorem: for any $n > 1$ there is a unique non-decreasing list of prime numbers whose product is identical to $n$ .

The claim is true when $n = 2$ . Assume it to be true for all $k \le n$ . Then either $n+1$ is prime or it is not prime. In the first case there are numbers $a,b$ such that $n+1 = ab$ where $1 < a,b < n+1$ . But by hypothesis, $a,b$ have unique non-decreasing lists of prime numbers whose product is identical to each. Since the product of two ordered lists is a list that can be arranged in order, the existence of an ordered list whose product is $n+1$ is assured. To establish uniqueness, suppose $n+1$ has two ordered lists of prime numbers whose product is $n+1$ . Then

$p_1 \ldots p_u = q_1 \ldots q_v$ .

the assertion to establish is that $u = v$ and $p_i = q_i$ for all $i = 1..u$ . Let $j\le u$ be the first index for which $p_j \neq q_j$ . Assume wlog $p_j < q_j$ . Since $p_j | \prod_{k =j..v} q_k$ , there is $k \ge j$ such that $p_j | q_k$ . But this is not possible since $q$ is an ordered list. So $p_i = q_i$ for all $i \le u$ . Hence $u \le v$ . Applying the same argument with $q$ transposed with $p$ , conlude that $v \le u$ . Hence the lists are identical, establishing uniqueness.