## Chapter 32Solutions for ninth week’s assignments

Also available as PDF.

### 32.1 Linear Diophantine equations

Find two integer solutions to each of the following, or state why no solutions exist:

• 64x + 336y = 32
• 33x - 27y = 11
• 31x - 27y = 11
• 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}} & & }