Problem on divisibility.

Find all natural numbers $n\geq1$ such that $n^2$ does not divide $(n-2)!$. I tried to do it by supposing prime factorization of n in terms of variable, but I cannot buzz it, please help!

• I didn't find all of them and I'm far from proofing this but maybe it helps to list those I found to see a pattern. First of all if n is prime it can't devide (n-2)! Oct 2, 2015 at 15:55
• If n has a prime-factorisation where every prime has the exponent 1 then n must be less then 2 times the biggest prime + 2 because if you assume it was bigger (n-2)! would have all the prim factors twice in them and you could devide them Oct 2, 2015 at 16:06
• Well, let's see. If n is composite and greater than four then all the non-trivial factors of n divide (n-2)! so unless n = prime^2, n divides (n-2)!. So for n^2 not to the must be some factors of n that only appear once in {1,...., n-2}. We need to find some way of expressing and calculating that. Oct 2, 2015 at 16:25
• @SubhadeepDey Agawa was referring to a comment that was flagged and removed afterwards. Oct 2, 2015 at 16:25
• @RobertSoupe,Oh, I see. I am sorry.
– user249332
Oct 2, 2015 at 16:27

Well the key really lies in prime factorization. Suppose $n = pqr,$ where $p < q$ are primes and $r > 1$. Then $p ≥ 2, q ≥ 3$ and $r ≥2$ ,not necessarily a prime. Thus we have $n−2 ≥ n−p=pqr−p≥5p>p$, $n−2 ≥ n−q=q(pr−1)≥3q>q$, $n−2 ≥ n−pr=pr(q−1)≥2pr>pr$, $n−2 ≥ n−qr=qr(p−1)≥qr$.

Observe that $p,q,pr,qr$ are all distinct. Hence their product divides $(n − 2)!$. Thus $n^2 = p^2q^2r^2$divides $(n −2)!$ in this case. We conclude that either $n = pq$ where $p,q$ are distinct primes or $n = pk$ for some prime $p$.

Case 1. Suppose $n = pq$ for some primes $p,q,$ where $2 < p < q$. Then $p ≥ 3$ and $q ≥ 5$. In this case $n−2 > n−p=p(q−1)≥4p$, $n−2 > n−q=q(p−1)≥2q$. Thus $p,q,2p,2q$ are all distinct numbers in the set ${1,2,3,... ,n − 2}.$ We see that $n^2 = p^2q^2$ divides $(n − 2)!$.

We conclude that $n = 2q$ for some prime $q ≥ 3$. Note that $n−2=2q−2<2q$ in this case so that $n^2$ does not divide $(n−2)!$.

Case 2. Suppose $n = pk$ for some prime $p$. We observe that $p,2p,3p,...(pk−1 −1)p$ all lie in the set ${1,2,3,... ,n −2}$. If $pk−1 −1 ≥ 2k,$ then there are at least $2k$ multiples of $p$ in the set ${1,2,3,... ,n − 2}.$ Hence $n^2 = p^2k$ divides $(n−2)!.$ Thus $pk−1 −1 < 2k.$ If $k ≥ 5$, then $pk−1 −1 ≥ 2k−1 −1 ≥ 2k$, which may be proved by an easy induction. Hence $k ≤ 4.$ If $k = 1$, we get $n = p,$ a prime. If $k = 2,$ then $p−1 < 4$ so that $p = 2 \ or \ 3$; we get $n = 22 ,4 \ or$ $n = 32 , 9$ . For $k = 3$, we have $p^2 −1 < 6$ giving $p = 2$; $n =23,8$ in this case. Finally, $k = 4$ gives $p^3 −1 < 8$. Again $p = 2$ and $n = 24 , 16$. However $n^2 = 28$ divides $14!$ and hence is not a solution. Thus $n = p,2p$ for some prime $p$ or $n = 8,9$.

The answer would have been more interesting and less lengthy had op given some extra conditions. But nevertheless, question was beautiful.

• I think in your first case line 1 you want: "where $2 \leq p < q$. Otherwise, you have $n = pq$ for $2 < p < q$ followed in the next paragraph by, "We conclude that $n = 2q$..." Oct 2, 2015 at 20:44
• nope, i have written exactly what i wanna write Oct 3, 2015 at 2:55
• If $n = pq$ for $2 < p < q$ and $n = 2q$ then $p = 2$; an immediate contradiction. Oct 3, 2015 at 2:58
• Yeah, contradiction is what we want, n=pq for some prime p,q, where 2<p<q, but we showed that here n^2 divides (n-2)!, hence we conclude that n is not equal to pq for some 2<p<q, hence p is not greater than 2, so it is equal to two! Oct 3, 2015 at 3:05

What you need to focus on is the prime factorization of $(n - 2)!$. Let's say $p_1 = 2$, $p_2 = 3$, $p_3 = 5$ and so on and so forth to $p_{\pi(n - 2)}$ (where $\pi(n - 2)$ tells you how many primes there are up to $n - 2$. Then the factorization of $(n - 2)!$ goes something like this: $$(n - 2)! = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \ldots {p_{\pi(n - 2)}}^{\alpha_{\pi(n - 2)}}.$$

Clearly $\alpha_{\pi(n - 2)} = 1$. The previous exponents might be greater than 1, and certainly $\alpha_1 > 1$ for $n > 5$. Figuring out $\alpha_2$, $\alpha_3$ gets a little tricky. But definitely $\alpha_j = 0$ for all $j > \pi(n - 2)$.

What this means is that no square or cube other higher power of a prime greater than $n$ can divide $(n - 2)!$. For that matter, neither can $(n - 1)^2$ if $n - 1$ is prime. As for numbers that have all their prime factors in common with $(n - 2)!$, if any of the exponents in their factorization exceeds a certain threshold, then its square will not divide $(n - 2)!$.

Well, I think you can take it from here to the destination: if $n$ is a prime, or twice a prime, or equal to 8 or 9, then $n^2 \nmid (n - 1)!$ (see A178156 in Sloane's OEIS).

• 12 isnt twice a prime but 12^2 divide 10! Oct 2, 2015 at 16:28
• You're absolutely right, @Agawa001. Something in the back of my mind told me that there's a difference between $n \nmid (n - 2)!$ and $n \nmid (n - 1)!$. But when I saw the comment that was flagged and removed, I found myself losing interest in the question. Oct 2, 2015 at 16:50
• the question is nice but if the op asks for a specific conditions for any squared number to divide the factorial of its minus 2, the question can drag more interests (including me), but nice attempt though :) Oct 2, 2015 at 16:54

OK, let's try this:

I think a number $n$ with the prime factors $\alpha_n$ and the exponent $\beta_n$ a solution if and only if it is less then $\max\{\alpha_n 2 \beta_n\} + 2$

Proof-Concept: $n^2$ has the same prime factors with doubled exponent. $(n - 2)!$ contains the prime factor $x$ exactly $\lfloor \frac{n - 2}{x} \rfloor$ times. Therefore $(n - 2)!$ is divisible by $\alpha_n^{2 \beta_n}$ if $n \geq \alpha_n 2 \beta_n + 2$.