Geek Culture
Published in

Geek Culture

Euclidean Algorithm using Python

Euclidean algorithm, one of the most important algorithm of number theory, is going to be written using python. This article is straight to the point so that you don’t have to wait for the real context for a while. Good luck.

Let’s go.

If you have searched for this algorithm then you should probably know what gcd(greatest common divisor) is.

a. is to find gcd of two non-negative integers and
b. later have been extended to find linear combination of gcd of those two numbers.

Now, after knowing its uses , let’s delve right into algorithm.
We will separately write euclidean algorithm and extended euclidean algorithm for better understanding.

Use:
This algorithm only finds gcd of two non negative integers.

Code:

print(“Input two non-negative integers a and b such that a>=b”)
a,b= map(int, input().split())
x,y=a,b # Store temporarily

while b>0:
r=a%b
a=b
b=r
print(f”gcd({x},{y})={a}”)

You provide the input as given condition and get the desired gcd between any two non-negative integers.

Now the most important algorithm which is extended from previous algorithm is below:

Uses:
a. Used to find gcd between two non-negative integers.
b. Find gcd(a,b) as linear combination of a and b i.e.
gcd(a,b)=sa+tb where ,
a and b are non-negative integers
s and t are any

Note: gcd(a,b)=sa+tb is also known as bezout’s identity . s and t are bezout’s coefficients.

def extended_euclidean(a, b):  if b == 0:    gcd, s, t = a, 1, 0    return (gcd, s, t)  else:    s2, t2, s1, t1 = 1, 0, 0, 1    while b > 0:      q= a // b      r, s, t = (a - b * q),(s2 - q * s1),( t2 - q * t1)      a,b,s2,t2,s1,t1=b,r,s1,t1,s,t    gcd,s,t=a,s2,t2    return (gcd,s,t)#Take inputprint("Input two non-negative integers a and b such that a>=b")a, b = map(int, input().split())x, y = a, b  # Store temporarilyresult=extended_euclidean(a,b)
#Print the resultprint(f"gcd({x},{y})={result[0]}")print(f"Linear combination gcd(a,b)=sa+tb:\n {result[0]}={result[1]}*{x}+{result[2]}*{y}")

So folks , this is all about euclidean and extended euclidean algorithms which are very important topics in number theory.

Stay tuned for more topics . Keep learning and keep inspiring.

Good bye for now. Be happy.❤😀

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store