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}$ essentially the same argument) , we have with

And so

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 So 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.

_____________________________________________________________________________________________

The Integers mod n:

A Convention:

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 :

Affine Encryption: Choose with , as Integers

Encryption -
Decryption -

Focusing on the letters of the alphabet (A,B,....,Z) and looking at with

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}{22}$ choices for $\QTR{Large}{a}$ (not or $\QTR{Large}{13}$ ).

That is $\QTR{Large}{550}$ possible codes.

Disadvantages: It is just a Substitution Cypher!

Plan B: Encode the entire character ASCII table, and look at with 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.