Page 91 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

1= 3 − 2= (−5)103 +(14)37 − [(9)103 +(−25)37] =(−14)103 +(39)37.

So, r = −14 and s =39. Let’s check our work:

(−14)103 = 1442, and(39)37 = 1443,

so indeed

(−14)103 +(39)37 =1.

Do you know what? You can solve every problem in this book without a calculator, just as I
have. Well, not every problem, because as you’ll see, there are a few * problems which no one

has ever solved. But, it’s possible that you will be the first to solve them!

• Hint for # 5: Use the IUT. Yes, it is incredibly useful. It is possible to do #5 using only the

IUT and the definition of divide.
• Hint for #6: One way to show that two positive integers are equal is to show that they divide
each other. The greatest common divisor is always at least one. It is always positive. First,
prove that if two positive numbers divide each other, then they must be equal. Then, prove
using the definition of greatest common divisor and the IUT (yep, incredibly useful) that
(a, bc) divides (a, b)(a, c) and also prove that (a, b)(a, c) divides (a, bc).
• Hint for #7: This is similar to #5 and # 6. The IUT may be incredibly useful here too.
• Hint for # 8: You can make the equation look more neat and tidy by putting 1 in disguise

k
1= ,
k

and so

1 k k +1
1+ = + .
k k k

Then, the product looks like

1+ 1 2+ 1 3+ 1 n +1
∗ ∗ ∗ ... ∗ .
1 2 3 n
Now, you might notice a pattern and be able to prove the equation straight away. Otherwise,
you can do a proof by induction. The base case is n =1, and in this case, the product just
has one term,

1+ 1
=2 = n +1.
1

91