THE ART AND SCIENCE OF MATHEMATICS
Wednesday, November 2, 2005

Some Number Theory

Number theory concerns the study of integers. It is over 2000 years old and is still being actively researched today. It is famous for simply stated conjectures that have eluded proof for hundreds of years, but the theory is also vital to various applications. For example, data encryption is based on theories, conjectures, and algorithms that arise from number theory; it is used every time you send your credit card number over the internet. It is not possible to understand how the data encryption algorithms work without knowing some number theory.

Typically in number theory, we use the phrase ``$b$ divides $a$'' to mean that $b$ divides $a$ without remainder. That is, there exists an integer $m$ with $b \times m = a$. The greatest common divisor of two positive integers $c$ and $d$ is the largest positive integer that divides both $c$ and $d$. For example, $gcd(8,12)=4$, $gcd(12,25)=1$, $gcd(a,a)=a$.

Exercise: Compute $gcd(45,75)$, $gcd(1,a)$, $gcd(a,2a)$.

One way to find greatest common divisors is to compute all the factors of each number, but that is very slow for large numbers. Much of the utility of number theory is derived from the fact that there is a simple and fast algorithm to find the greatest common divisor known as the Euclidean Algorithm. In general, for many large numbers, the Euclidean Algorithm is conjectured to be a million (or more) times faster than any algorithm that tries to find all the factors of each number individually. There are important data encryption algorithms that take advantage of this.

The Euclidean Algorithm:

• Let $a$ and $b$ be two positive integers with $a \geq b$.
• Divide $b$ into $a$ and find the remainder $r_1$.
• Divide $r_1$ into $b$ and find the remainder $r_2$.
• Divide $r_2$ into $r_1$ and find the remainder $r_3$.
• While the remainder is nonzero, divide the last remainder into the previous one to get a new remainder.
• The last nonzero remainder is $gcd(a,b)$.

Example: Find the greatest common divisor of $a=252$ and $b=198$:

• Divide 198 into 252, get remainder $r_1=252-198=54$.
• Divide 54 into 198, get remainder $r_2=198-3 \times 54=36$.
• Divide 36 into 54, get remainder $r_3=54-36=18$.
• Divide 18 into 36, get remainder $r_4=36-2 \times 18=0$.
• Since we have a remainder of zero, the last nonzero remainder is the greatest common divisor, that is, $gcd(252,198)=18$.

Exercise: Use the Euclidean Algorithm to find $gcd(57,133)$ and $gcd(981,1234)$.

The Game of Euclid:

This is a game played by two people. Beginning with two positive integers, the players alternate turns making moves of the following type:

A player can move from the pair of positive integers $\{x,y\}$ to any of the pairs $\{x-ty,y\}$ where $t \geq 1$ is an integer and $x-ty \geq 0$. Thus, you can subtract any multiple of the smaller number from the larger number, provided you still have two nonnegative numbers.

The winner is the one that first makes one element zero.

Play the game of Euclid with a partner and for different starting pairs of integers $\{a,b\}$. Verify that you always end up with the pair $\{0,gcd(a,b)\}$ at the end of the game. Can you prove that this is always the case?

Can player 1 always win the game of Euclid? Can player 2 always win? What is the best strategy?

Further topics:

• If two positive integers have a greatest common divisor equal to 1, then these two integers are said to be relatively prime.

  Exercise: For each integer $n$ from 2 to 12, find all positive integers less than $n$ that are relatively prime to $n$.

• The Euler phi-function $\phi(n)$ is defined to be the number of positive integers not exceeding $n$ that are relatively prime to $n$.

  Exercise: Use the result from the previous exercise to determine the values of the Euler phi-function for $n$ from 1 to 12. Do you see a pattern? (You can generate this sequence using Maple: with(numtheory): [ seq(phi(n),n=1..100)]; )

• Two numbers are congruent modulo $m$ (written $a \equiv b\pmod m$) if $m$ divides $a-b$.

  Exercise: For each integer from 0 to 3 find two other integers congruent to it modulo 4.

  Exercise: Suppose that $a \equiv b\pmod m$ and $c \equiv d\pmod m$. Is it true that $a+c \equiv b+d\pmod m$? Can you prove it? Can you prove that $ac \equiv bd\pmod m$?

• A famous and nontrivial result that is also used in data encryption algorithms is Euler's Theorem: If $m$ is a positive integer and $a$ is a positive integer relatively prime to $m$ then
  

  $$a^{\phi(m)} \equiv 1\pmod m.$$
  
  

  Exercise: Verify Euler's Theorem for $m=4$ and $a=9$ and for $m=5$ and $a=3$.

• More on the Game of Euclid
• More on Euler's phi-function

Other resources:

• Strategies for the Euclidean game, and variants of the game.
• The MathWorld page on the Euler's phi function.
• Two other pages on Euler's phi function and Euler's theorem.