2002 IMO Shortlist Problems/N3
Let be distinct primes greater than 3. Show that has at least divisors.
Lemma 1. If , then has at least twice as many divisors as .
Proof. For every divisor of , is clearly a divisor of , but not .
Proof. Clearly, 3 divides both and . Now, suppose that there is some which divides both and . Then . But this means that both and are divisible by half the order of 2 in mod , contradicting our assumption that and are relatively prime.
We now note that since
we know that is divisible by , and, by symmetry, also, and therefore also by .
We now prove the result by induction on . Our base case, , is easy, since we know that is divisible by 3, and is greater than 27. Now, set and . By Lemma 2, we know that and are relatively prime; hence has at least factors, by the inductive hypothesis.
We know that divides . We also know that , whence . Then by Lemma 1,
We proceed by induction. For our base case, , we note that is divisible by 3. Since , is clearly greater than 3 and cannot be a larger power of three, since this would require . Therefore has some other prime factor and therefore at least 4 factors overall.
Now, suppose the proposition holds for . Without loss of generality, let be the minimum of . We shall abbreviate . We note the relation
Since has at least factors, it will suffice to show that is relatively prime to , and has at least four factors.
We note that in general, has remainder when divided by . But cannot divide , as this would require when is relatively prime to . Hence and are relatively prime.
We now claim that has at least four factors. We start by noting that in general, divides , since the roots of the former are the nonreal th roots of unity and .
Since clearly , it is sufficient to show that the former is not the square of the latter (i.e., that the former is either a higher power of the latter, or some other prime divides the latter, either of which implies that the former has at least four factors). But this follows from
Thus has at least four factors and is relatively prime to , completing the induction.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.