Skip to main content
OlympiadHQ

Browse · harp

Print

smc

number theory senior

Problem

Suppose , , and are positive integers such thatWhich of the following statements are necessarily true? I. If or or both, then . II. If , then or or both. III. if and only if .
(A)
(B)
(C)
(D)
(E)
Solution
We examine each of the conditions. The first condition is false. A simple counterexample is and . The corresponding value of is . Clearly, and , so condition would imply that However, is clearly not (they share a common factor of ). Obviously, condition is false, so we can rule out choices and . We are now deciding between the two answer choices and . What differs between them is the validity of condition , so it suffices to simply check . We look at statement 's contrapositive to prove it. The contrapositive states that if and , then In other words, if shares some common factor that is not with and shares some common factor that is not with , then also shares a common factor with . Let's say that , where is a factor of not equal to . (So is the common factor.) We can rewrite the given equation as We can express as , for some positive integer (this can be ). We can factor out to get We know that all values in this equation are integers, so must be divisible by . Since is a factor of , must also be a factor of , a multiple of . Therefore, we know that shares a common factor with (which is ), so . This is what states, so therefore is true. Thus, our answer is
Final answer
E