Mystery Procedure
Can you work out what this procedure is doing?
Age
14 to 16
Challenge level
What does this procedure do? Prove it.
Image
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.
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.