Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Numbers of the form share factors in a neat way. For example .
Euclidean algorithm: where . Bezout: for some integers , , and is solvable exactly when .
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Part (a). .
Step 2. The first claim of part (b). By part (a), minus a multiple of is . The subtracting rule gives .
Step 3. The formula. Use strong induction on . If , both sides are . Otherwise, say . By Step 2 the HCF equals , a pair with a smaller exponent sum. By the induction hypothesis this is . And . Proof complete.
Step 4. Part (c). , so the HCF is .
Answer: .
What if? The proof works for any base : .
Log in to join the discussion.
Loading…