Mystery Procedure
Can you work out what this procedure is doing?
Problem
What does this procedure do? Prove it.
Image
Student Solutions
This procedure calculates the highest common factor of A and B.
The algorithm swaps over A and B to ensure A > B. We know hcf(A,B) $\leq$ min(A,B) = B in this case. Therefore, the first guess for N = hcf(A,B) is B. It first tests whether N is a factor of B. If that's the case, it then tests whether it's a factor of A. If either of these fail, it decreases N by 1. Eventually, it will either stop at a value of N>1 such that N divides A and B, or will terminate when N=1 (as A/1 and B/1 are both whole numbers). In the latter case, A and B are coprime.
Teachers' Resources
It is not envisaged that this problem would be used as a class problem. It is more appropriate for an enthusiastic student or small group of students looking for a challenge to work on independently.