`r_hops = u_hops - q (v_hops)` and `r_skips = u_skips - q (v_skips)`.
# # This sort of tallying is what makes the algorithm below work. The function below does not introduce any new programming concepts, but it assembles many ideas together. # # In[ ]: def hop_and_skip(a,b): ''' Takes two integer arguments a,b, and prints a sentence of the form GCD(a,b) = x(a) + y(b). The method is the Euclidean algorithm, tallying hops (units of a) and skips (units of b) along the way. ''' u = a # We use u instead of dividend. v = b # We use v instead of divisor. u_hops, u_skips = 1,0 # u is built from one hop (a) and no skips, for now. v_hops, v_skips = 0,1 # v is built from no hops and one skip (b), for now. while v != 0: # We could just write "while v:" q = u // v # q stands for quotient. r = u % v # r stands for remainder. So u = q(v) + r. r_hops = u_hops - q * v_hops # Tally hops r_skips = u_skips - q * v_skips # Tally skips u,v = v,r # The new dividend,divisor is the old divisor,remainder. u_hops, v_hops = v_hops, r_hops # The new u_hops, v_hops is the old v_hops, r_hops u_skips, v_skips = v_skips, r_skips # The new u_skips, v_skips is the old v_skips, r_skips print("{} = {}({}) + {}({})".format(u,u_hops,a,u_skips,b)) # In[ ]: hop_and_skip(102,45) # Try out the hop_and_skip code on some integers of your choice. Does it behave correctly? Check the results, using Python as a calculator. Does it run quickly for large integers? # In[ ]: # Experimentation space here. # To conclude this lesson, we put everything together to create a long(ish) function to solve linear Diophantine equations. We want this function to be smart enough to respond when an equation has no solutions, and to describe *all* solutions when they exist. # # The first part of the function `solve_LDE` is the same as the hop and skip function above. But rather than expressing $GCD(a,b)$ as $ax + by$, the function uses the GCD to determine the existence and the general form of a solution to $ax + by = c$. The formula for the general form comes from [An Illustrated Theory of Numbers](http://bookstore.ams.org/mbk-105), Chapter 1, Corollary 1.25. # In[ ]: def solve_LDE(a,b,c): ''' Describes all of the solutions to the linear Diophantine equation ax + by = c. There are either no solutions or infinitely many solutions. Prints a description of the solution set, and returns None if there are no solutions or returns a single solution if one exists. ''' u = a # We use u instead of dividend. v = b # We use v instead of divisor. u_hops, u_skips = 1,0 # u is built from one hop (a) and no skips. v_hops, v_skips = 0,1 # v is built from no hops and one skip (b). while v != 0: # We could just write while v: q = u // v # q stands for quotient. r = u % v # r stands for remainder. So u = q(v) + r. r_hops = u_hops - q * v_hops # Tally hops r_skips = u_skips - q * v_skips # Tally skips u,v = v,r # The new dividend,divisor is the old divisor,remainder. u_hops, v_hops = v_hops, r_hops # The new u_hops, v_hops is the old v_hops, r_hops u_skips, v_skips = v_skips, r_skips # The new u_skips, v_skips is the old v_skips, r_skips g = u # The variable g now describes the GCD of a and b. if c%g == 0: # When GCD(a,b) divides c... d = c//g x = d * u_hops y = d * u_skips # Now ax + by = c is a specific solution! print("{} x + {} y = {} if and only if ".format(a, b, c)) print("x = {} + {} n and y = {} - {} n, for some integer n.".format(x,b//g,y,-a//g)) return x,y else: # When GCD(a,b) does not divide c... print("There are no solutions to {} x + {} y = {},".format(a,b,c)) print("because GCD({}, {}) = {}, which does not divide {}.".format(a,b,g,c)) return None # In[ ]: solve_LDE(102,45,3) # In[ ]: solve_LDE(72,100,17) # ### Exercises # # 1. Solve problems 4-7 of Chapter 1 of [An Illustrated Theory of Numbers](http://bookstore.ams.org/mbk-105) using the `solve_LDE` function. # # 2. Write an `LCM` function, using the previous `GCD` function and the GCD-LCM product formula, Theorem 1.23 of [An Illustrated Theory of Numbers](http://bookstore.ams.org/mbk-105). # # 3. Sometimes it is important to find not the integer solutions, but the *positive* integer solutions to a Diophantine equation. Modify the `solve_LDE` function to create a `solve_LDE_positive(a,b,c)` function. The output of the function should be all pairs of *positive* integers $x$, $y$, such that $ax + by = c$ (if any pairs exist), and a helpful message if no pairs exist (and a `return None` should be used in this case). # In[ ]: # Use this space to work on the exercises.