Find all positive integers $n$ such that $n^2 \not\mid (n - 2)!$

Question

Find all positive integers $n$ such that $n^2 \not\mid (n - 2)!$

We have that $\gcd(n - 1, n) = 1$, then $n^2 \not\mid (n - 1)!$

Of course, primes and Carmichael numbers are solutions to this question, but are there any other ones?

For the case where $v_n((n - 1)!) = 1$, I don't know what to do.

(I apologise for not showing my attempts, I haven't thought of anything which could potentially lead to an actual answer.)

Answer 1

Claim: The only solutions are $n=8, 9, p, 2p$ (for any $p$ prime)

Prove: It is clear that $n=8,9$ satisfy the requirement, as $64 \not\mid 720$ and $81 \not\mid 5040$.

Now I shall first prove $n = p, 2p$ satisfy, then prove these are the only solutions.

By definition,

$$(p-2)! = (p-2)\times(p-3)\times(p-4)\times\cdots\times2\times1$$

Looking at each of the factors $p-2,p-3,p-4,\cdots,2,1$, it is clear that none of them (with exception, of course, of $1$) is divisible by $p$, let alone $p^2$. Remember that since $p$ is a prime, $p \mid ab \implies (p\mid a) \lor (p \mid b)$ ($\lor$ means "or")

Similarly,

$$(2p-2)!=(2p-2)\times(2p-1)\times(2p-2)\times\cdots\times(p)\times\cdots\times2\times 1$$

This time while multiplying from $2p-2$ to $1$, you "pass through" $p$, as $p\geq 2$. Therefore, there is one factor of $p$ in the product of $(2p-2)!$. However, this is the only one, as no other terms in the product divide $p$, and again, this proves that $p^2 \not\mid (p-2)!$.

To show that these are the only numbers, consider $n=xy$ with both of $x, y > 2$. This is always possible for a number not in above form. (Note below)

$$(xy-2)!=(xy-2)\times(xy-3)\times\cdots\times(x(y-1))\times\cdots\times(x(y-2))\times\cdots\times2\times1$$

It is clear that the terms $x(y-1)$ and $x(y-2)$ (as well as many more others) are divisible by $x$. However, we also need to show they're actually in the product, and not like $5\times4\times\cdots\times23\times\cdots\times1$ (haha that's extreme). This can easily be proven since

$$xy-2\leq x(y-1)\leq x(y-2) \iff -2\leq -x \iff x\geq 2$$

This can also be done with $(x-1)y$ and $(x-2)y$ instead, as the proof is similar.

This shows that $x^2 \mid (xy-2)!$ and $y^2 \mid (xy-2)!$. As mentioned in the comments, to ensure that $x^2y^2 \mid (xy-2)!$, you must also ensure that $\gcd(x^2,y^2)=1$ i.e. $\gcd(x,y)=1$. This can be forced unless $n=k^2$. The case that $n=k^2$ (perfect square) is left to be an exercise for you, the reader :) (Sorry!)

Finally, this concludes the proof, and we've shown that:

$$n=8, 9, p, 2p$$

Cheers :)

To prove every integer that cannot be written as 8, 9, p, 2p

must be in the form of xy with x,y > 2, we can see that

The number `n` can be written as product of two primes p,q and an integer k
i.e. n=pqk (Factorisation and since it's not a prime).
Note that k can be 1, when n is a semi-prime.

If p=2, qk must not be a prime.
Therefore k>1 and k >= 2.
Therefore, (pk) >= 4. q is a prime,
so it must either be 2 or (at least 3).
However when q=2, either k=2 and pqk = 8, or k>=3 and pq=4>=3.
Therefore, if p=2, pqk must either be 8 or xy.

Therefore, p>=3.
Now q can either be 2, or at least 3.
When q is 2, k >= 2 since pqk=2pk is not 2p.
Now we have p>=3, q=2, k>=2. So (qk) >= 3 again and (p)(qk)=(x)(y). 

If p>=3 and q>=3, k doesn't even matter and we have (p)(qk)=(x)(y) again.

This completes the proof