Suppose a and b are congruent mod m, then we can write a = b + km for some integer k. Now, let d1 = gcd(a,m), and let d2 = gcd(b,m). Since d2 | b and d2 | m, we have d2 | (b + km), so d2 | a. So d2 divides both a and m, so d2 ≤ d1. A similar argument shows d1 ≤ d2 (since b = a + Km, where K =...