Mark: 1 revision(s)

2008-03-08T22:35:28Z

1 revision(s)

← Older revision		Revision as of 22:35, 8 March 2008
(No difference)

Mark at 03:47, 24 July 2006

2006-07-24T03:47:48Z

New page

==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===

# If n = m then output n as gcd(n,m) and stop
# If n > m then initialize a = n and b = m. Otherwise, initialize a = m and b = n.
# Apply the division theorem to a and b by finding integers q and r such that a = q · b + r, where 0 � r < b.
# 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
# If A then B
# 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.

211Lecture5 - Revision history

Mark: 1 revision(s)

Mark at 03:47, 24 July 2006