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.
We proceed by induction. Base case . Observe that , and since , so has at least 4 divisors.
Now suppose the proposition holds for .
lemma 1: if with and both being odd, then .
Proof: let p be a prime that divides both and . Then p divides both and . Since (mod ) and (mod ), divides and . But, , so . Hence proven.
lemma 2: , with being a prime greater than .
Proof; It suffices to show that . for , the only solution to (mod ) is . is the smallest natural such that (mod ). This means that if (mod ), (mod ), but is a prime greater than , so this is not possible.
Note that . Let . Note that . So . Note that .
I will now prove . Note that . We wish to prove . Rearrange the inequality to get . Note that , which implies the inequality. Since , .
Also, note that . This means has at least four factors. Note that if , would be relatively prime to , which would mean has at least factors.
Assume and are not relatively prime. Then there exists some prime such that . Let , and , with being the prime in question. Note that . ( is relatively prime to ). Then . Let be the number of divisors of . Then . Note that , so . From the inductive step , so . This implies , which completes the induction. QED