Prove the equality gcd(m, n) = gcd(n, m mod n) for every pair of positiveintegers m and n

Sure, here is the proof for the equality gcd(m, n) = gcd(n, m mod n) for every pair of positive integers m and n.

Step 1: Let's assume that d is a common divisor of m and n. This means that there exist integers q and r such that m = dq and n = dr.

Step 2: Now, let's consider the modulo operation m mod n. This can be written as m = n*q + r, where q is the quotient and r is the remainder.

Step 3: Substituting the values of m and n from step 1, we get dq = dr*q + r. Simplifying, we get r = d(q - rq).

Step 4: This shows that r is also divisible by d. Hence, d is a common divisor of n and m mod n.

Step 5: Now, let's assume that d' is a common divisor of n and m mod n. This means that there exist integers q' and r' such that n = d'q' and m mod n = d'r'.

Step 6: From the equation m = n*q + m mod n, substituting the values of n and m mod n from step 5, we get m = d'q'q + d'r'. Simplifying, we get m = d'(q'q + r').

Step 7: This shows that m is also divisible by d'. Hence, d' is a common divisor of m and n.

Step 8: From steps 4 and 7, we can conclude that the set of common divisors of m and n is the same as the set of common divisors of n and m mod n.

Step 9: Therefore, the greatest common divisor of m and n is the same as the greatest common divisor of n and m mod n. Hence, gcd(m, n) = gcd(n, m mod n).

This completes the proof.