Some Elementary Number Theory

Bézout's Identity and The Euclidean Algorithm

Theorem:

Let $\QTR{Large}{a}$ and $\QTR{Large}{b}$ be two integers. Let , the greatest common divisor of $\QTR{Large}{a}$ and $\QTR{Large}{b}$ . We can find integers $\QTR{Large}{i}$ and $\QTR{Large}{j}$ and such that

Proof:

By reordering if necessary, we can assume and since,

if $\QTR{Large}{a}$ or , the statement is trivial.
if then and
if we can prove it under this assumption then the general case follows, using $\QTR{Large}{-a}$ and/or $-\QTR{Large}{b}$ .

Let be the smallest integer such that there are integers $\QTR{Large}{i}$ and $\QTR{Large}{j}$ and .

We need to show

$\QTR{Large}{c\ }$ is a common divisor of $\QTR{Large}{a}$ and $\QTR{Large}{b}$ . If not, assume it does not divide $\QTR{Large}{a}$ ( $\QTR{Large}{c}\$ does not divide $\QTR{Large}{b}$ is essentially the same argument) , we have with

and

On the other hand, If $\QTR{Large}{d\ }$ is a common divisor of $\QTR{Large}{a}$ and $\QTR{Large}{b}$ then $\QTR{Large}{d\ }$ divides $\QTR{Large}{c}$ . Since

Therefore $\QTR{Large}{c}$ is the greatest common divisor

The Algorithm:

Again assume , if $\QTR{Large}{b\ }$ divides $\QTR{Large}{a}$ we are done since . If not letwith .

If divides $\QTR{Large}{b\ }$ , it must also divide $\QTR{Large}{a\ }$ , so let , and

Suppose does not divide $\QTR{Large}{b\ }$ then with .

If divides , as before, it also divides $\QTR{Large}{b}$ and hence $\QTR{Large}{a}$ . By back substitution

Suppose does not divide then with and so on. The process must terminiate in a finite number of steps.

Corrollary:

In the setting above, again assuming we can select $\QTR{Large}{\ j}$ such that

Proof: Exercise. If ,begin by finding an $\QTR{Large}{n\ }$ and such that

__________________________________________________________________________________________

Prime Numbers:

Definition:

Let $\QTR{Large}{a}$ and $\QTR{Large}{b\ }$ be two integers such that $\QTR{Large}{|a|}$ $\QTR{Large}{>0}$ , ,and then $\QTR{Large}{a}$ and $\QTR{Large}{b}$ are said to be relatively prime

Theorem:

Let $\QTR{Large}{a}$ and $\QTR{Large}{b\ }$ be relatively prime Let $\QTR{Large}{p}$ be a prime such that $\QTR{Large}{p}$ divides . Then divides $\QTR{Large}{p}$ divides $\QTR{Large}{a}$ or $\QTR{Large}{p}$ divides $\QTR{Large}{b}$
.

Proof:

Suppose $\QTR{Large}{p}$ does not divide $\QTR{Large}{a}$ , then we can find $\QTR{Large}{i\ }$ and $\QTR{Large}{\ j}$ such that

Multiplying both sides of the equation by $\QTR{Large}{b}$ , we have

Since $\QTR{Large}{p}$ divides both terms on the left side of the equation, $\QTR{Large}{p}$ divides

Theorem:

Every integer $\QTR{Large}{a\ }$ such that $\QTR{Large}{|a|}$ $\QTR{Large}{>1}$ can be uniquely factored into a product of primes (perhaps times $\QTR{Large}{-1}$ )

Proof:

First show by an inductive argument that every such integer is either a prime or a product of primes. Then use the previous Theorem to show that the product is unique.

Godel Numbers - An Example:

Working with {A,B,C....,Z} coded as $\QTR{Large}{\ }$ {1,2,3....,25,26} and the sequence of prime numbers $\QTR{Large}{\ }$ {2,3,5,7,11,.......} where the $\QTR{Large}{i}$ th prime is denoted by .

encode a sequence of letters ,again as numbers, as a single integer . Because of unique factorization we can recover the original sequence.

_____________________________________________________________________________________________

The Integers mod n:

Below, sometime our calculations will be in and sometimes in the integers $\QTR{Large}{Z}$ . Hopefully, use of the phases " In " and " In $\QTR{Large}{Z\ }$ " will clarify where the computations are taking place

and the conclusions that can be draw::

Some Examples

In the equation $\QTR{Large}{a+}$ is uniquely solvable for $\QTR{Large}{x\ }$ and therefore, in , we can also define the operation $\QTR{Large}{b\ -}$ $\QTR{Large}{a}$ .

If then, in , the solution to the equation $\QTR{Large}{5-}$ is :
In in general the equation is not solvable, however: If $\QTR{Large}{a\ }$ and $\QTR{Large}{n\ }$ are relatively prime, as Integers then there is a unique with In $\QTR{Large}{Z\ ,}$ just solve , in particular In let

Exercise: We are assuming that, in let " makes sense in terms of existance and, uniqueness, why?:
and , as Integers, then in the equation is uniquely solvable

_________________________________________________________________________________________

Affine Encryption (in :

Choose with , $\QTR{Large}{a>1,}$ as Integers.

Encryption -
Decryption -

Representing the letters of the alphabet (A,B,....,Z) as and looking at with , $\QTR{Large}{a>1,}$ as Integers,

Advantages: It is easy to compute and slightly better than the Caesar Cyper in that there are $\QTR{Large}{25}$ choices for $\QTR{Large}{s}$ and $\QTR{Large}{11\ }$ choices for $\QTR{Large}{a}$ (not ) or (. That is $\QTR{Large}{275}$ possible codes.

Disadvantages: It is really just a Substitution Cypher!

Plan B: Encode the entire character ASCII table, and look at with , $\QTR{Large}{a>1,}$ as Integers.you would want to do this anyway. Still easy to compute and now there are approximately possible codes. A bit harder but still subject to frequency analysis attacks.