211Lecture5

Euclidean Algorithm

In this section we provide the well known Euclidean algorithm that appeared around 300 BC. The algorithm determines the greatest common divisor of two integers. The algorithm is used frequently in programming, integer arithmetic, number theory, and other areas of computing and mathematics. In this section our goal is to learn the algorithm and prove its correctness. We start with the following definition.

The algorithm

1. If n = m then output n as gcd(n,m) and stop
2. If n > m then initialize a = n and b = m. Otherwise, initialize a = m and b = n.
3. Apply the division theorem to a and b by finding integers q and r such that a = q · b + r, where 0 � r < b.
4. If r = 0 then output b as gcd(n,m) and stop. Otherwise, set a = b and b = r. Go to line 3.

Example

n=123, m=156

a=156, b=123

156= 1.123+33

First remainder is r=33, q =1

a2=123, b2=33

123= 3.33+24

Second value of r=24, q=3

a3=33, b3=24

33=1.24+9

24=2.9+6

9=1.6+3

a5=9 b5=6, r5=3,15=1

6=2.3+0 r=0 so output b

Modulo Arithmatic

In this section we introduce the modulo arithmetic discovered by Gauss at the end of the eighteenth century. Modulo arithmetic is nowadays applied in number theory, abstract algebra, cryptography, etc. The fundamental arithmetic operations performed by most computers are actually modulo arithmetic operations, where the modulus is 232. For example, arithmetic operations on integers of most programming languages such as Java or C are all taken modulo 232. Therefore, for us it is useful to understand and learn some of the basics of modulo arithmetic.

0 +¯0 =¯0, ¯0 +¯1 =¯1, ¯1 +¯0 =¯1, and ¯1 +¯1 =¯0, and ¯0 ·¯0 =¯0, ¯0 ·¯1 =¯0, ¯1 ·¯0 =¯0, and ¯1 ·¯1 =¯1.

Definition 3. Say that integers n and m are congruent modulo p if p is a factor of n − m.

say for p=3

{0,3,-3,6,-6,9,-9,12,-12}

{1,4,-2,7,-5,10,-8}<- such that when divided by 3 the remainder is 0.

Theorem 6. Integers n and m are congruent modulo p if and only if when divided by p both give the same remainder.

To prove the theorem we must show that

1. If A then B
2. If B then A

Take n,m congrigent mod. p n-m=kp fore some k. We want to show that when divided by p, m,n give the same remainder.

Divide n,m by p.

n=q1.p+r1
m=q2.p+r2

We want to show r1=r2

n-m=(q1-q2).p+(r1-r2) [can be divided through by p]

rest in lecture notes.