notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

EuclideanAlgorithm.md (874B)

      1 # Euclidean Algorithm
      2 
      3 Ch 2.4
      4 
      5 **Definition:** The Euclidean algorithm is an algorithm used to determine the greatest common factor of two positive integers.
      6 
      7 This is done as an alternative to the prime factoziation method which is too slow.
      8 
      9 The euclidean algorithm is shown below in python:
     10 
     11 ```python
     12 
     13 # This has not been validated as working.
     14 
     15 def gcd(a,b):
     16     if(a > b):
     17         temp = b
     18         b = a
     19         a = temp
     20 
     21     r = 1
     22     while(r > 0):
     23         coeff  = int(a / b)
     24         r = a - (coeff*b)
     25         if r > 0:
     26             a = b
     27             b = r
     28     return b
     29 
     30 print(gcd(10, 3))
     31 
     32 ```
     33 
     34 # Extended Euclidean Algorithm
     35 
     36 **Definition:** Let a,b \in Z such that a,b > 0 & a >= b. Then there exists u,v \in Z such that gcd(a,b) = a * u + b * v.
     37 
     38 The extended Euclidean Algorithm is useful because is allows for us to solve for u which is the inverse of a modulo b.