Maths Olympiad Prep

Library / HMMT February /812 of 1302

HMMT February, 2019

Number theory Difficulty 5.4 AIME, harder Prove it United States

Problem:

Call a positive integer nn weird if nn does not divide (n−2)!(n-2)!. Determine the number of weird numbers between 2 and 100 inclusive.

Solution

Solution:

We claim that all the weird numbers are all the prime numbers and 44.

Since no numbers between 11 and p−2p-2 divide prime pp, (p−2)!(p-2)! will not be divisible by pp. We also have 2!=22! = 2 not being a multiple of 44.

Now we show that all other numbers are not weird. If n=pqn = pq where p≠qp \neq q and p,q≥2p, q \geq 2, then since pp and qq both appear in 1,2,…,n−21, 2, \ldots, n-2 and are distinct, we have pq∣(n−2)!pq \mid (n-2)!. This leaves the only case of n=p2n = p^2 for prime p≥3p \geq 3. In this case, we can note that pp and 2p2p are both less than p2−2p^2 - 2, so 2p2∣(n−2)!2p^2 \mid (n-2)! and we are similarly done.

Since there are 2525 prime numbers not exceeding 100100, there are 25+1=2625 + 1 = 26 weird numbers.

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

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