How many values of $n<50$ exist that satisfy$ (n-1)! \ne kn$ where n,k are natural numbers?

Question

How many natural numbers less than 50 exist that satisfy $ (n-1)! \ne kn$ where n,k are natural numbers and $n \lt 50$ ?

when n=1

$0!=1*1$

when n=2

$1!\ne2*1$

...

...

...

when n=49

$48!=\frac{48!}{49}*49$

Here $k = \frac{48!}{49}$ and $n =49$

Answer 1

Let $n$ be a prime number. However, there is one more case. let $n=4$. $$(4-1)!=3!=6\neq4\cdot{k}$$ since $k\in{\mathbb{N}}$

Answer 2

If you're only interested in the case of up to n = 49 then the answer isn't very enlightening... the answer is 16.

As the hints above suggest, you need to look at what happens when n is a prime, although you also need to take care in this case with n = 4 (can you see why?).

Answer 3

Others have already given the answers (16, the primes plus 4). This is why.

For any number $n$, either $n$ is prime or $n$ is composite. If n is prime, then n cannot divide $(n-1)!$, as n is not in the prime decomposition of any of the numbers up to $n-1$ and therefore not in the decomposition of the factorial.

If $n$ is composite, then by decompose $n$ to its primes, $n = p_1^{\alpha_1}\times\ldots\times p_r^{\alpha_r}$, where $\alpha_i \in \mathbb{N}$ and $p_i$ is prime. For a given $p_i$, we have that $p_i, 2p_i, \ldots, (\frac{n}{p_i}-1)p_i$ will be part of the factorial product, so we have enough of $p_i$ in the factorial to as long as $\frac{n}{p_i} - 1 \geq \alpha_i$.

It's easy to see that for any $\alpha_i > 2$, this is true (we see that $p_i^{\alpha_i - 1} \geq 2^{\alpha_i - 1} \geq \alpha_i$ for all $\alpha_i > 2$). For $\alpha_i = 2$, it is still true if any of the other $\alpha_j \neq 0$. And lastly, for $n = p_i^2$, we have $p_i - 1 \geq 2$ for all $p_i$ other than $p_i = 2$. So the only situation where this will fail is if $n = 2^2 = 4$.

Answer 4

For natural numbers $z$ and prime $p$ denote the largest $k$ such that $p^k$ divides $z$ by $[z]_p$. It is well known that $$\bigl[m!\bigr]_p=\left\lfloor{m\over p}\right\rfloor+\left\lfloor{m\over p^2}\right\rfloor+\left\lfloor{m\over p^3}\right\rfloor+\ldots\quad.$$ It follows that $n$ does not divide $(n-1)!$ iff there exists a prime $p$ such that $$[n]_p\ >\ \left\lfloor{n-1\over p}\right\rfloor+\left\lfloor{n-1\over p^2}\right\rfloor+\left\lfloor{n-1\over p^3}\right\rfloor+\ldots\quad.\tag{1}$$ When $p>n$ then both sides of $(1)$ are zero. When $p=n$ then the left side of $(1)$ is $1$, and the right side of $(1)$ is zero. In this case $n$ does not divide $(n-1)!\ $.

Assume now that $p<n$ and that $[n]_p=\rho\geq0$.

When $\rho\leq1$ then the left side of $(1)$ is $\leq1$, and the right side is $\geq1$. In this case $p$ cannot serve as witness for $n\not|\>(n-1)!\ $.

When $\rho\geq2$ we can argue as follows: We have $n\geq p^\rho$ and therefore $$\left\lfloor{n-1\over p}\right\rfloor\geq\left\lfloor p^{\rho-1}-{1\over p}\right\rfloor=p^{\rho-1}-1=:Q\ .$$ Now $$Q\geq p2^{\rho-2}-1\geq p(\rho-1)-1=\rho+\bigl((p-1)(\rho-1)-2\bigr)\geq\rho\ ,$$ unless $p=\rho=2$. It follows that $n=2^2$ (forget about multiples of $2^2$) is the only case where a nonprime $n$ could satisfy $(1)$ for a certain $p$. The number $4$ is indeed such an exception.