Chapter 32
Solutions for ninth week’s assignments

32.1 Linear Diophantine equations

• From a previous problem, we have that 336 = 64 ⋅ 5 + 16. Thus 336 ⋅ 1 + 64 ⋅-5 = 16 and 336 ⋅ 2 + 64 ⋅-10 = 32. So one solution is \mathbf{{x}_{0} = -10} and \mathbf{{y}_{0} = 2}. The general solution is x = {x}_{0} + t ⋅ 336∕(336,64) = -10 + 21t and y = {y}_{0} - t ⋅ 64∕(336,64) = 2 - 4t for any integer t. Another solution then is \mathbf{x(1) = -10 + 1 ⋅ 21 = 11} and \mathbf{y(1) = 2 - 4 ⋅ 1 = -2}.
• Here, (33,27) = (3 ⋅ 11,{3}^{3}) = 3. Now 3 ∤ 11, so there are no solutions.
• Now 31 is prime, so (31,27) = 1\mathrel{∣}11 and there are solutions. Running through the Euclidean algorithm we see that
  \eqalignno{ 31 & = 27 ⋅ 1 + 4, & & \cr 27 & = 4 ⋅ 6 + 3,\text{and} & & \cr 4 & = 3 ⋅ 1 + 1. & & }

  Starting from the bottom and substituting for the previous remainder,

  \eqalignno{ 4 + 3 ⋅ (-1) & = 1, & & \cr 4 + (27 + 4 ⋅ (-6)) ⋅-1 = 27 ⋅ (-1) + 4 ⋅ 7 & = 1, & & \cr 27 ⋅ (-1) + (31 + 27 ⋅ (-1)) ⋅ 7 = 31 ⋅ 7 + 27 ⋅ (-8) & = 1. & & \cr & & }

  We find that 31 ⋅ 7 + 27 ⋅ (-8) = 1, so 31x - 27y = 11 has an initial solution of \mathbf{{x}_{0} = 7 ⋅ 11 = 77} and \mathbf{{y}_{0} = -1 ⋅-8 ⋅ 11 = 88}.

  The general solutions have the form

  \eqalignno{ x = {x}_{0} + t {-27\over (31,27)} & = 77 - 27t,\text{ and} & & \cr y = {y}_{0} - t {31\over (31,27)} & = 88 - 31t, & & }

  Another solution is given by \mathbf{x(1) = 77 - 27 ⋅ 1 = 50} and \mathbf{y(1) = 88 - 31 ⋅ 1 = 57}.

32.2 Exercises 6.3

Problem 5

{16\over 48} = {16⋅1\over 16⋅3} = {1\over 3}

Problem 6

{21\over 28} = {7⋅3\over 7⋅4} = {3\over 4}

Problem 9

{3\over 8} = {5⋅3\over 5⋅8} = {15\over 40}, {3\over 8} = {-1⋅3\over -1⋅8} = {-3\over -8}, {3\over 8} = {2⋅3\over 2⋅8} = {6\over 16}

Problem 10

{9\over 10} = {-2⋅9\over -2⋅10} = {-18\over -20}, {9\over 10} = {2⋅9\over 2⋅10} = {18\over 20}, {9\over 10} = {11⋅9\over 11⋅10} = {99\over 110}

Problem 13

• {2\over 6} = {1\over 3}
• {1\over 4}
• {4\over 10} = {2\over 5}
• {3\over 9} = {1\over 3}

Problem 14

• {12\over 24} = {1\over 2}
• {6\over 24} = {1\over 4}
• {12\over 16} = {3\over 4}
• {2\over 16} = {1\over 8}

Problem 20

{8\over 9}

Problem 22

{41\over 90}

Problem 24

{14\over 60} = {7\over 30}

Problem 26

{41\over 60}

Problem 28

{3\over 28}

Problem 30

{-1\over 6}

Problem 32

{1\over 4}

Problem 34

{-3\over 10}

Problem 36

{-3\over 20}

Problem 39

{13\over 3}

Problem 40

{31\over 8}

Problem 57

\eqalignno{ 2 + {1\over 1 + {1\over 3+{1\over 2} } } & = 2 + {1\over 1 + {2\over 7}} & & \cr & = 2 + {7\over 9} & & \cr & = \mathbf{{25\over 9} } & & }

Problem 58

\eqalignno{ 4 + {1\over 2 + {1\over 1+{1\over 3} } } & = 4 + {1\over 2 + {3\over 4}} & & \cr & = 4 + {4\over 11} & & \cr & = \mathbf{{48\over 11}} & & }