# What are the conditions for $n^2 \nmid(n-1)!$

Q: What are the conditions for $n^2 \nmid (n-1)!$, given that $2\le n \le 100$ and $n\in \mathbb{N}$?

According to me the two conditions must be:
1. $n$ is a prime number (since the factorization of $(n-1)!$ will not have a $n$ when n is prime).
2. $n = 2\times$(prime number). (Because if $p$ is the prime number such that $n=2p$, then $(2p-1)!$ will have only one $p$ in the prime factorization, but we need two.)

Is there any other condition for $n^2\text{does not divide} ((n-1)!)$ ?

-
Just a tip: use \nmid ($\nmid$) for "does not divide" rather than \not | ($\not |$), which looks unclear and confusing. –  6005 Jan 6 '14 at 8:01
Is there a typos in the post? You wrote $2\in\mathbb{N}$ –  Test123 Jan 6 '14 at 8:04
Just a question, why the restrictions? And why $2\in \mathbb{N}$? –  Umberto Jan 6 '14 at 8:04
$n=8$ doesn't fit into either 1 or 2 –  Jyrki Lahtonen Jan 6 '14 at 8:05
You can easily find some condition if $n=p^k$ for some prime $p$, or if $n=pq$ for distinct primes $p,q$. The first condition will add $8$ and $9$ to your previous list. –  zozoens Jan 6 '14 at 8:54

If $n$ has (at least) two distinct prime factors -- say $p$ and $q$ -- then notice that the factors $\frac{n}{p}$, $\frac{n}{q}$, $p$, and $q$ multiply to get $n^2$. So we would like to write $$n^2 = \frac{n}{p} \cdot \frac{n}{q} \cdot p \cdot q \; \mid \; (n-1)!$$ (since $p,q, \frac{n}{p}, \frac{n}{q} < n$ are contained in the expansion of $(n-1)!$.) But a few things could go wrong:

1. $n$ does not have at least two distinct prime factors. Then either $n$ is a power of a prime, or $n = 1$. If $n = 1$, in fact $n^2$ does divide $(n-1)! = 1$. Otherwise, let $n = p^k$, $k > 0$.

1a. If $k = 1$, then this is one exception (which you list): $\boxed{n \text{ is prime}}$.

1b. If $p^{k-1} > 2k$, then we can write $$n^2 = p^{2k} \; \mid \; p^{p^{k-1} - 1} \; \mid \; (p)(2p)(3p)\cdots ((p^{k-1} - 1)p) \; \mid \; (n-1)!$$ 1c. Either (1a) or (1b) applies unless $(p,k) = (2,2), (2,3), (2,4), (3,2)$. These correspond to $n = 4, 8, 16, 9$, of which $\boxed{n = 4, 8, 9}$ are genuine exceptions.

2. $\frac{n}{p}$ could equal $p$ (or $\frac{n}{q}$ could equal $q$). In this case, $n = p^2$, which is not divisible by $q$ (so this case never happens).

3. $\frac{n}{p}$ could equal $q$ (or $\frac{n}{q}$ could equal $p$). In this case, $n = pq$. If $p,q > 2$, then we write $$n^2 = p^2q^2 \; \mid \; p \cdot q \cdot 2p \cdot 2q \; \mid \; (n-1)!$$ because $p,q, 2p, 2q < pq = n$. Otherwise, we have the exception $\boxed{n \text{ is 2 times a prime}}$. (This exception also encompasses $n = 4$ from case 1.)

So: besides $n = 8,9$, your two conditions are correct (and you don't need the restriction $2 \le n \le 100$).

-
You don't need $n=4$ as an exception. It is 2 times a prime! –  shaurya gupta Jan 6 '14 at 8:49
@shauryagupta Good point. –  6005 Jan 6 '14 at 8:51
What if we were to count the number of values of n that satisfy the restriction $2\le n \le 100$? –  shaurya gupta Jan 6 '14 at 8:51
ideone.com/zfsd3o says you are right :) (I just coded this in an old Xperia, I am feeling extremely badass for getting it right the first time) –  chubakueno Jan 6 '14 at 8:53
@chubakueno So are there 42 such values of $n$?? –  shaurya gupta Jan 6 '14 at 8:56