Maths Olympiad Prep

Library / /2 of 4

Number theory Difficulty 6.0 AIME, harder Prove it Romania

Given a prime p5p \ge 5, show that there exist at least two distinct primes qq and rr in the range 2,3,,p22, 3, \dots, p-2 such that qp1≢1(modp2)q^{p-1} \not\equiv 1 \pmod{p^2} and rp1≢1(modp2)r^{p-1} \not\equiv 1 \pmod{p^2}.

Solution

(1) An improper integer greater than 1 has at least one improper prime divisor; and
(2) If kk is an integer coprime to pp and nn is a proper integer, then kpnkp - n is improper.
The first claim follows from the fact that the product of two proper integers is again proper. For the second, notice that pp does not divide knp2k n^{p-2} to deduce that
(kpn)p1np1(p1)kpnp21+kpnp2≢1, (kp - n)^{p-1} \equiv n^{p-1} - (p-1)k p n^{p-2} \equiv 1 + k p n^{p-2} \not\equiv 1,
so kpnkp - n is indeed improper (since nn is coprime to pp, so is kpnkp - n).
Since ±1\pm 1 are both proper, letting k{1,2}k \in \{1, 2\} and n=±1n = \pm 1 in (2) shows that p±1p \pm 1 and 2p±12p \pm 1 are all improper, so each has an improper prime divisor by (1).

Since p5p \ge 5, the prime factors of p±1p \pm 1 are all less than p1p-1; and since 2 is the highest common factor of p1p-1 and p+1p+1, the conclusion follows, provided that 2 is proper.
Otherwise, look for an improper odd prime in the required range. To this end, notice that one of the numbers 2p±12p \pm 1 is divisible by 3, so its prime factors are all less than p1p-1, for p5p \ge 5; clearly, they are all odd, and the conclusion follows.

Alternative Solution.
If p=5p=5, the primes q=2q=2 and r=3r=3 satisfy the required conditions, so let p7p \ge 7. In the setting of the previous solution, distinguish the following two cases:
If p2p-2 is improper, it has an improper prime divisor qq by (1). On the other hand, since 1 is proper, setting k=n=1k=n=1 in (2) shows that p1p-1 is improper, so it has an improper prime divisor rr by (1). Clearly, qq and rr both lie in the required range, and they are distinct since p2p-2 and p1p-1 are coprime.
If p2p-2 is proper, set k=1k=1 and n=p2n = p-2 in (2) to deduce that 2 is improper. On the other hand, since (p2)2(p-2)^2 is proper, so is 4p+4-4p+4. Setting k=3k=-3 and n=4p+4n = -4p+4 in (2) shows p4p-4 improper, so it has an improper prime divisor ss by (1). Finally, since p4p-4 is odd, so is ss, and it should now be clear that the primes 2 and ss satisfy the required conditions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.