CMSC 27100 — Lecture 9

Here is the proof of Lamé’s theorem.

We will prove that $a_n \geq f_n$, the $n$th Fibonacci number, by induction on $n$.

Base case. From the statement, we have $a_0 = 0 = f_0$ and $0 \lt a_1$ and $f_1 = 1 \leq a_1$.

Inductive case. Let $k$ be an arbitrary natural number. Assume that $a_j \geq f_j$ for all $j \lt k$. Let $n = k+1$. Recall that the $a_i$’s are the sequence of integers that we get from running Euclid’s algorithm. This means that the algorithm will try to compute $\gcd(a_{k+1}, a_k)$, which results in a recursive call to try to compute $\gcd(a_k, a_{k-1})$. Recall that this amounts to trying to “divide” $a_{k+1}$ by $a_k$, resulting in a remainder of $a_{k-1}$.

So by the Division Theorem, there exists an integer $q$ such that $a_{k+1} = q \cdot a_k + a_{k-1}$ and that $a_{k-1} \leq a_k$. Then $q \geq 1$ and \begin{align*} a_{k+1} &= q \cdot a_k + a_{k-1} & \text{Division Theorem} \\ & \geq a_{k} + a_{k-1} & \text{since $q \cdot a_k \geq a_k$} \\ & \geq f_{k} + f_{k-1} & \text{inductive hypothesis} \\ & = f_{k+1} & \text{Fibonacci numbers} \end{align*}

Ultimately, the question we want to answer is how big $n$ is compared to $\log a$.

Let $a \gt b \geq 0$ be natural numbers such that the representation of $a$ requires $d$ decimal digits and the calculation of $\gcd(a,b)$ via Euclid’s algorithm requires $k$ division steps. Then $k \leq 5 \cdot d$.

Since the decimal representation of $a$ requires $d$ digits, we have $a \lt 10^d$. If the computation of $\gcd(a,b)$ by Euclid’s algorithm requires $k$ steps, by Lamé’s Theorem, we have $a \geq f_k$. Then we have \begin{align*} f_k &\lt 10^d &\text{since $f_k \leq a \lt 10^d$}\\ \frac{\varphi^k}{\sqrt 5} &\leq 10^d &\text{since $\widetilde \varphi^k \to 0$ as $k \to \infty$}\\ k \log \varphi - \frac{\log 5}{2} &\leq d \log 10 &\text{apply $\log$ to both sides}\\ k &\leq \frac{d \log 10}{\log \varphi} - \frac{\log 5}{2 \log \varphi} &\text{isolate $k$}\\ k &\leq 4.789d + 1.673 \end{align*} That this implies $k \leq 5d$ is clear for large $d$.

This is a neat result that goes back to our brief discussion about the efficiency of trying to find a gcd. What Lamé’s theorem tells us is that Euclid’s algorithm executes operations roughly linearly to the number of digits of the largest number $a$. Intuitively, this result tells us that each division we perform usually knocks out one of the digits. The number of digits of a number turns out to be about $\log a$, so Euclid’s algorithm scales roughly logarithmically with $a$.

If we compare this to the computing all the divisors method, we would be executing approximately as many operations as there are numbers from 1 to $n$. This means that our naive algorithm scales roughly linearly with $a$. Comparing the two algorithms, we have an approximately exponential difference between the two.

Prime numbers

Here is an important definition.

An integer $p$ greater than 1 is called prime if the only positive divisors of $p$ are 1 and $p$. Otherwise, $p$ is called composite.

A large portion of number theory is devoted to the study of prime numbers and their properties. A big reason for this is that they are considered the building blocks for numbers. This idea is so important that the primary result concerning this is called the Fundamental Theorem of Arithmetic.

Every natural number $n \gt 1$ is a product of a unique weakly decreasing sequence of primes.

A weakly decreasing sequence is a sequence $a_1, \dots, a_n$, where $a_i \geq a_{i+1}$ for $1 \leq i \leq n$. Another term for this is “nonincreasing”. This formulation of the Theorem is found in the text, but it is often stated without the specification that the sequence is weakly decreasing. It’s not entirely necessary (just take your sequence and order it so that it’s nonincreasing), so we won’t concern ourselves with it too much.

Consider the following.

Note here the condition that $n \gt 1$. Sometimes there is some controversy among non-mathematicians over the fact that 1 is not considered a prime number. There are a number of reasons one can give to justify this idea. The main justification is due to this theorem: if 1 were a prime number, then we could no longer say that every number has a unique prime factorization.

This idea extends to other so-called unique factorization domains, which are a kind of $\mathbb Z$-like structure in abstract algebra where every non-zero and non-unit element has a unique factorization. Here, a unit is any element $x$ where one can find an element $y$ such that $xy = 1$. Obviously, in $\mathbb N$, the only one of these is 1, but in other structures, there are more elements that have these multiplicative inverses. One example you may be familiar with are the rational numbers, $\mathbb Q$.

In the end, no matter how you slice it, 1 is not a prime number. Do not fall into the trap.

The Fundamental Theorem of Arithmetic

Since the theorem claims that prime factorizations are unique, we will prove this in two parts, as is usual for uniqueness proofs. First we prove the fact that we can factor numbers into primes (existence) and then show that this factorization is unique.

Every natural number $n \gt 1$ can be written as a product of primes.

We will prove that for $n \gt 1$, $n$ can be written as a product of primes via strong induction on $n$.

Base case. Let $n = 2$. Then 2 is a product of primes because 2 is a prime number.

Inductive case. Let $k \in \mathbb N$. Assume that for all natural numbers $m$ with $2 \leq m \leq k$, that $m$ can be written as a product of primes. We want to show that $n = k+1$ can be written as a product of primes. There are two cases to consider.

First, we note that we would be stuck if we were to proceed with ordinary induction in the usual way: suppose $k$ has a factorization into primes. This can’t help us for $k+1$, since $k$ is never a factor of $k+1$, nor are the divisors of $k$ necessarily related to the divisors of $k+1$. For a quick example, consider the divisors of 5 and 6.

So we use strong induction, but notice that this is a more substantial use of strong induction than what we did for the proofs involving Fibonacci numbers. With the Fibonacci numbers, we know that we needed a fixed number of predecessor cases (the two right before). Here, we are in a situation where the required predecessor cases can be anywhere from 2 to $k$—we don’t know where the cases we need are and they’re not guaranteed to be some fixed constant away from $k+1$.

This also says something interesting about the structure of natural numbers. Right at the beginning, we had a very strict and fundamental definition for the natural numbers with zero and the successors—in other words, we built up the natural numbers very linearly, one after the other. Now, knowing a few more things about natural numbers and integers allows us to have a more rich, but still recursive, construction—they’re made up of prime numbers.

You will find such constructions in computer science. For example, insertion sort (see: Python (141), Racket (151)) is a sorting algorithm that is based on the recursive definition of a list. One can think of this as what we do with ordinary mathematical induction: it’s induction on the basic definition of the structure.

But mergesort (see: Python (141), Racket (151)) is a more complicated algorithm that depends on splitting the list in half—this doesn’t follow the definition of the list. In a sense, this is like strong induction: we assume that our program works on smaller pieces, not just the piece that comes right before it. Reasoning about algorithms like mergesort (which you’ll see in 272) uses strong induction.