Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)!)$ ?

share|cite|improve this question
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
up vote 6 down vote accepted

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$).

share|cite|improve this answer
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 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.