Jim Belk University of Glasgow

Homework 3

Due Date: Friday, February 19

    1. Write a program that, given two integers \(a\) and \(b\) (not both zero), uses the extended Euclidean algorithm to find integers \(x\) and \(y\) such that \[ ax + by \,=\, \mathrm{gcd}(a,b). \]
    2. Demonstrate your program from part (a) by finding integers \(x\) and \(y\) so that \[ 348153868589018633619876937115107\,x \,+\, 417313194961807259870190713481689\,y \;=\; 210209. \]
    3. Write a program which takes as input the coefficients \((a,b,c)\) for a linear Diophantine equation \[ ax + by \,=\, c, \] where \(\mathrm{gcd}(a,b) \mid c\), and outputs the solution \((x,y)\) for which \(x\) is nonnegative and as small as possible. For example, the input \((57,92,17)\) should yield the solution \((81,-50)\), and the input \((56,119,28)\) should yield the solution \((9,-4)\).
    4. Demonstrate your program from part (c) by finding the solution to the equation \[ 127330249286126071218855\,x \,+\, 141478053616390052813269\,y \;=\; 1984929 \] for which \(x\) is nonnegative and as small as possible.
  2. Given a pair \(a_1,a_2\) of positive integers with \(a_1>a_2\), the corresponding Euclidean sequence \(a_1,\ldots,a_n\) is the decreasing sequence defined recursively by the equation \[ a_k \,=\, R(a_{k-2},a_{k-1}) \] where \(R(a,b)\) denotes the remainder upon dividing \(a\) by \(b\). The sequence ends when it reaches zero. For example, the Euclidean sequence starting with \(a_1=194\) and \(a_2= 57\) is \[ 194,\;\;57,\;\;23,\;\; 11,\;\; 1,\;\; 0. \] Prove that the length of any Euclidean sequence is less than or equal to \(1+ 2\bigl\lceil\log_2(a_1)\bigr\rceil\). (Hint: Show that \(a_k < a_{k-2}/2\) for each \(k > 2\).)
  3. If \(a\) is a positive integer and \(p\) is a prime, the multiplicity of \(\boldsymbol{p}\) in \(\boldsymbol{a}\) is defined by the formula \[ n_p(a) \,=\, \max\{k \mid p^k\text{ divides }a\}. \] Use this notation to prove the following statements. You should feel free to use any of the facts about \(n_p\) listed on the “Facts About \(n_p\)” page.
    1. Prove that \[ \mathrm{lcm}(a,b,c) \,=\, \frac{abc\,\mathrm{gcd}(a,b,c)}{\mathrm{gcd}(a,b)\,\mathrm{gcd}(a,c)\,\mathrm{gcd}(b,c)} \] for all positive integers \(a\), \(b\), and \(c\).
    2. Prove that \[ \mathrm{lcm}\bigl(a,\mathrm{gcd}(b,c)\bigr) \,=\, \mathrm{gcd}\bigl(\mathrm{lcm}(a,b),\mathrm{lcm}(a,c)\bigr) \] for all positive integers \(a\), \(b\), and \(c\).