Problem:
Suppose that a,b, and c are positive integers such that
14a+15b=210c
Which of the following statements are necessarily true?
I. If gcd(a,14)=1 or gcd(b,15)=1 or both, then gcd(c,210)=1.
II. If gcd(c,210)=1, then gcd(a,14)=1 or gcd(b,15)=1 or both.
III. gcd(c,210)=1 if and only if gcd(a,14)=1 and \operatorname{gcd (b, 15)=1.
Answer Choices:
A. I,II, and III
B. I only
C. I and II only
D. III only
E. II and III only
Solution:
Note that 14 and 15 are relatively prime and 210=14⋅15. Let q and r be two relatively prime positive integers (such as 14 and 15). The equation qa+rb=qrc is equivalent to ar+bq=c. Hence
gcd(c,q)=gcd(ar+bq,q)=gcd(ar,q)=gcd(a,q)
Similarly, gcd(c,r)=gcd(b,r). Also, gcd(c,qr)=1 if and only if gcd(c,q)=1 and gcd(c,r)=1. Therefore Statement III is true, and that statement logically implies Statement II. To see that Statement I might be false, let a=1,b=3, and c=57; then the hypothesis is true but the conclusion is false. Thus Statements (E)IIandIII are the only ones that are necessarily true.
The problems on this page are the property of the MAA's American Mathematics Competitions