`r_hops = u_hops - q (v_hops)` and `r_skips = u_skips - q (v_skips)`.
\n", "\n", "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.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def hop_and_skip(a,b):\n", " '''\n", " Takes two integer arguments a,b, and prints a sentence of the form\n", " GCD(a,b) = x(a) + y(b). The method is the Euclidean algorithm,\n", " tallying hops (units of a) and skips (units of b) along the way.\n", " '''\n", " u = a # We use u instead of dividend.\n", " v = b # We use v instead of divisor.\n", " u_hops, u_skips = 1,0 # u is built from one hop (a) and no skips, for now.\n", " v_hops, v_skips = 0,1 # v is built from no hops and one skip (b), for now.\n", " while v != 0: # We could just write \"while v:\"\n", " q = u // v # q stands for quotient.\n", " r = u % v # r stands for remainder. So u = q(v) + r.\n", " \n", " r_hops = u_hops - q * v_hops # Tally hops\n", " r_skips = u_skips - q * v_skips # Tally skips\n", " \n", " u,v = v,r # The new dividend,divisor is the old divisor,remainder.\n", " u_hops, v_hops = v_hops, r_hops # The new u_hops, v_hops is the old v_hops, r_hops\n", " u_skips, v_skips = v_skips, r_skips # The new u_skips, v_skips is the old v_skips, r_skips\n", " \n", " print(\"{} = {}({}) + {}({})\".format(u,u_hops,a,u_skips,b))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "hop_and_skip(102,45)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Experimentation space here.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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. \n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def solve_LDE(a,b,c):\n", " '''\n", " Describes all of the solutions to the linear Diophantine equation\n", " ax + by = c. There are either no solutions or infinitely many solutions.\n", " Prints a description of the solution set, and returns None if there are no solutions\n", " or returns a single solution if one exists.\n", " ''' \n", " u = a # We use u instead of dividend.\n", " v = b # We use v instead of divisor.\n", " u_hops, u_skips = 1,0 # u is built from one hop (a) and no skips.\n", " v_hops, v_skips = 0,1 # v is built from no hops and one skip (b).\n", " while v != 0: # We could just write while v:\n", " q = u // v # q stands for quotient.\n", " r = u % v # r stands for remainder. So u = q(v) + r.\n", " \n", " r_hops = u_hops - q * v_hops # Tally hops\n", " r_skips = u_skips - q * v_skips # Tally skips\n", " \n", " u,v = v,r # The new dividend,divisor is the old divisor,remainder.\n", " u_hops, v_hops = v_hops, r_hops # The new u_hops, v_hops is the old v_hops, r_hops\n", " u_skips, v_skips = v_skips, r_skips # The new u_skips, v_skips is the old v_skips, r_skips\n", " \n", " g = u # The variable g now describes the GCD of a and b.\n", " \n", " if c%g == 0: # When GCD(a,b) divides c...\n", " d = c//g\n", " x = d * u_hops\n", " y = d * u_skips # Now ax + by = c is a specific solution!\n", " print(\"{} x + {} y = {} if and only if \".format(a, b, c))\n", " print(\"x = {} + {} n and y = {} - {} n, for some integer n.\".format(x,b//g,y,-a//g))\n", " return x,y\n", " else: # When GCD(a,b) does not divide c...\n", " print(\"There are no solutions to {} x + {} y = {},\".format(a,b,c))\n", " print(\"because GCD({}, {}) = {}, which does not divide {}.\".format(a,b,g,c))\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solve_LDE(102,45,3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solve_LDE(72,100,17)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercises\n", "\n", "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.\n", "\n", "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).\n", "\n", "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)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Use this space to work on the exercises.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" } }, "nbformat": 4, "nbformat_minor": 1 }