Consider the following code which determines whether x and y are relatively prime (that is, there are no integers ≥ 2 that divide evenly into both x and y):

bool IsRelativelyPrime(int x, int y) {
for (int i = 2; i <= x && i <= y; i++) {
if ((x % i == 0) && (y % i == 0)) return false;
}
return true;
}

You may assume that x and y are both at least 2.

Identify the loop invariant for the above code, prove the correctness of your invariant using induction, and then use the loop invariant to prove the correctness of the algorithm.