Maths Olympiad Prep

Library / /37 of 121

Number theory Difficulty 5.6 AIME, harder Prove it India

Problem:
Find all natural numbers n>1n > 1 such that n2n^{2} does not divide (n2)!(n-2)!.

Solution

Solution:
Suppose n=pqrn = p q r, where p<qp < q are primes and r>1r > 1. Then p2p \geq 2, q3q \geq 3 and r2r \geq 2, not necessarily a prime. Thus we have
n2np=pqrp5p>pn2nq=q(pr1)3q>qn2npr=pr(q1)2pr>prn2nqr=qr(p1)qr \begin{aligned} & n-2 \geq n-p = p q r - p \geq 5p > p \\ & n-2 \geq n-q = q(p r - 1) \geq 3q > q \\ & n-2 \geq n-p r = p r(q-1) \geq 2 p r > p r \\ & n-2 \geq n-q r = q r(p-1) \geq q r \end{aligned}
Observe that p,q,pr,qrp, q, p r, q r are all distinct. Hence their product divides (n2)!(n-2)!. Thus n2=p2q2r2n^{2} = p^{2} q^{2} r^{2} divides (n2)!(n-2)! in this case. We conclude that either n=pqn = p q where p,qp, q are distinct primes or n=pkn = p^{k} for some prime pp.

Case 1. Suppose n=pqn = p q for some primes p,qp, q, where 2<p<q2 < p < q. Then p3p \geq 3 and q5q \geq 5. In this case
n2>np=p(q1)4pn2>nq=q(p1)2q \begin{aligned} & n-2 > n-p = p(q-1) \geq 4p \\ & n-2 > n-q = q(p-1) \geq 2q \end{aligned}
Thus p,q,2p,2qp, q, 2p, 2q are all distinct numbers in the set {1,2,3,,n2}\{1, 2, 3, \ldots, n-2\}. We see that n2=p2q2n^{2} = p^{2} q^{2} divides (n2)!(n-2)!. We conclude that n=2qn = 2q for some prime q3q \geq 3. Note that n2=2q2<2qn-2 = 2q-2 < 2q in this case so that n2n^{2} does not divide (n2)!(n-2)!.

Case 2. Suppose n=pkn = p^{k} for some prime pp. We observe that p,2p,3p,,(pk11)pp, 2p, 3p, \ldots, (p^{k-1}-1)p all lie in the set {1,2,3,,n2}\{1, 2, 3, \ldots, n-2\}. If pk112kp^{k-1}-1 \geq 2k, then there are at least 2k2k multiples of pp in the set {1,2,3,,n2}\{1, 2, 3, \ldots, n-2\}. Hence n2=p2kn^{2} = p^{2k} divides (n2)!(n-2)!. Thus pk11<2kp^{k-1}-1 < 2k.

If k5k \geq 5, then pk112k112kp^{k-1}-1 \geq 2^{k-1}-1 \geq 2k, which may be proved by an easy induction. Hence k4k \leq 4. If k=1k=1, we get n=pn=p, a prime. If k=2k=2, then p1<4p-1<4 so that p=2p=2 or 33; we get n=22=4n=2^{2}=4 or n=32=9n=3^{2}=9. For k=3k=3, we have p21<6p^{2}-1<6 giving p=2p=2; n=23=8n=2^{3}=8 in this case. Finally, k=4k=4 gives p31<8p^{3}-1<8. Again p=2p=2 and n=24=16n=2^{4}=16. However n2=28n^{2}=2^{8} divides 14!14! and hence is not a solution.

Thus n=p,2pn = p, 2p for some prime pp or n=8,9n = 8, 9. It is easy to verify that these satisfy the conditions of the problem.

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.