Solution Exercise 70: Bezout identity for coprime numbers

 

 Exercise 70

Write an Python algorithm which asks the user to type a coprime intgeger n and m and returns a tuple (u, v) verifying: um + vn = 1 (Bezout identity) 

Solution

# Enter the values of the integers m and n
m = int (input ("Enter the value of the enier m:"))
n = int (input ("Enter the value of the integer n:"))

# Initialize the value of v to 1
v = 1
# We look for the integer v such that 1-vn is a multiple of n
# while  1-vn is not a multiple of m, we increment the integer v
while (( v*n - 1 )%m != 0):
    v = v + 1
# Now the equality um + vn = 1 means that 
u = int ((1- v*n)/m)
print ("The tuple that verifies um + vn = 1 is:", (u, v))