Let a and b be two positive integers such that a + b is a prime number. Prove that the greatest common divisor of a and b is 1.
I'm betting I need to somehow end up with ax + by = 1, but I can't figure out how to get there...?
I'm betting I need to somehow end up with ax + by = 1, but I can't figure out how to get there...?
-
How about proof by contrapositive? If the gcd(a, b) > 1, then a + b is not prime.
Suppose gcd(a, b) = p > 1. Then there are integers m and n such that a = mp and b = np.
a + b = mp + np = (m + n)p. Both (m + n) and p are > 1, so a + b is not prime.
Suppose gcd(a, b) = p > 1. Then there are integers m and n such that a = mp and b = np.
a + b = mp + np = (m + n)p. Both (m + n) and p are > 1, so a + b is not prime.