Class 20: Number Theory

Divisibility

Number theory is a study of integers $\mathbb{Z}={0,-1,1,-2,2,\dots}$. Adding, multiplying, and negating, are 3 operators on integers that we can define in a straight-forward way. Dividing is more tricky. For that, we first define the notation $a \mid b$ to denote the simpler situation where $b = k \cdot a$ for some $k \in \mathbb{Z}$. In this case, we say that $a$ is a divisor of $b$ and that $b$ is a multiple of $a$.

Show that if we assume $a \mid b$ and $a \mid c$ (for any integers $a,b,c$), then for all integers $x,y$ it will hold that $a \mid xa + yb$.

#

When $b$ is \emph{not} a multiple of $a$, we can still have some form of division, stated in the following theorem.

Theorem [Division Theorem] For all integers $n,d$, there are integers $q$ (called the quotiont) and $r$ (called the remainder, denoted by $rem(m,d)$) such that $$n = q \cdot d + r \text{and} 0\leq r < |d|.$$ Note that the remainder, as defined here, is always non-negative. For example when dividing $-3$ by $5$ we get $q=-1$ and $r=2$.

Definition A prime $p$, is an integer $p>1$ such that $1$ and $p$ are the only positive divisors of $p$. Other $n>1$ numbers (that are not prime) are called composite.

The following well-known theorem can be proved by strong induction on $n$.

Theorem [Fundamental theorem of arithmetic]. Any $n>1$ has a unique represention in the following form: $$ n = p_1^{a_1} \dots p_k^{a_k}$$ where $pi < p{i+1}$ and $p_i$ is prime for all $i$.

Hint for proof: Use strong induction on $n$, and try to show that any two different representations for $n$ will have the same `smallest’ prime $p_1$ and the same power $a_1$ for $p_1$.

Easy-to-state, but hard-to-solve problems

In number theory, we can easily state problems that are super hard to solve. These are some examples.

Goldbach’s conjecture: Any even integer $n>2$ can be written as $n=p+q$ where $p,q$ are both primes. The conjecture is still open, though we know that it is correct for all $n \leq 10^{18}$.

Twin prime’s conjecture: There infinite prime numbers $p$ where $p+2$ is also prime. Note that we cannot `check the conjecture up to $n$’ anymore! And it is still open…

Fermat’s last theorem: For any integer $n>2$ there are no integers $a,b,c$ where $a^n + b^n = c^n$. Note that for $n=2$ there are integer solutions like $3^2 + 4^2 = 5^2$. Fermat claimed to have a proof, but nobody knows if he really did or not. Andrew Wiles eventually proved this in 1994, hence we call it a theorem and not a conjecture anymore.

Greatest Common Divisor

Definition For natural numbers $m,n>0$ we call $d>0$ their \emph{greatest common divisor}, denoted by $d=gcd(m,n)$ if $d$ is the largest number such that $d \mid m$ and $d \mid n$. (Make sure to verify why we can always say that such $d$ exists.)

We can use the fundamental theorem of arithmetic, to compute the gcd of any given pairs of integers. But how efficient is it? The problem is that factoring numbers $m,n$ into their prime factors is not something we know how to do efficiently. In particular, no known algorithm is guaranteed to factor all numbers with $1000,000$ digits in less than an (estimated) thousand years! The conjecture is that no such `efficient’ algorithm exists, and many cryptographic algorithms assume this is the case!

Euclid’s Algorithm

Despite not knowing how to factor integers efficiently, Euclid showed how to find gcd quite efficiently. This shows, even if the most ``natural” algorithm fails for doing something efficiently, we should always consider the possibility that an alternative way could still exist.

def Euclid_gcd(m, n):
   while n > 0:
      r = rem(m,n)
      m = n
      n = r
   return m

What is a good state machine modeling the behavior of Euclid’s algorithm?

Suppose $d$ is any integer (in particular, it could be the gcd of the original state $(m,n)$ of the state machine for Eclid’s algorithm). Show that $gcd(a,b)=d$ is a preserved invariant for the transition graph of this state machine. Namely, if we go from one state to another state, the gcd does not change.

#

If the Euclid’s algorithm ends, at the very last step we will have $n=0$ which means $m$ is indeed the right gcd for that particular (final) state. Together with the preserved invariant (that you proved above), argue that the program has \emph{partial correctness}. Namely: if it ends, it outputs correctly.

#

Now prove the termination. Namely, show that the Euclid’s gcd algorithm will always end. Hint, look at $a+b$ for any state $(a,b)$ that we are in, and show that it always decreases.

#

Amazing thing about Euclid’s algorithm is that it is indeed quite efficient. A better analysis shows that it will always terminate in $\log (m+n)$ steps. (Hint: show that after two steps, $m$ will be at most half of what it was before..)