# Is this proof that $100!$ is not divisible by $101$ correct?

Is it enough to say that because $101$ is a prime number and $100!$ consists of numbers, and each of these numbers is composed of prime numbers which are less than $101$, and every number can't be decomposed in two different ways such that product of different primes is equal to another product of second group of a different primes, therefore $100!$ is not divisible by $101$?

Is this enough as a proof?

• It is phrased poorly, but you have the right idea. As per the definition of a prime, if $p$ is prime and $p\mid (a_1\times a_2\times \dots \times a_n)$ where each $a_i$ is an integer, then that implies that $p\mid a_1$ or $p\mid a_2$ or ... or $p\mid a_n$, but clearly $101\nmid 1, 101\nmid 2,\dots 101 \nmid 100$ and since $101$ is prime this implies that $101\nmid 100!$ Jul 4 '18 at 16:39
• @JMoravitz I am in your debt Jul 4 '18 at 16:45
• In a word. Yes. That is enough of a proof. I'm not going to even condemn your awkward wording. A huge part of mathmatics is expressing simple ideas that lack elegant vocabular and which then lead to convoluted eyes-glaze-over sentences such as yours. But the key component is that $101$ is a prime and thus not represented in any of the terms that "make up" $100!$. Recognizing and stating that, no matter how, awkward the phrasing is worth full credit as far as I'm concerned. Jul 4 '18 at 17:50

I think the argument relies hazily on the uniqueness of prime factorisation. It would be much more irrefutable to use

Euclid's lemma : If a prime number divides a product of numbers, it divides at least one factor in the product.

• The op stated "and every number can't be decomposed in 2 different ways" which is not in the least bit hazy. Admittedly it is poorly and awkwardly naively expressed as novice student not adept in formal and elegant language would make. But I actually find that reflects well on the student truly "getting" it. Jul 4 '18 at 17:55
• You're right, this asserttion is not hazy. What I find hazy is to which number exactly this is applied. Jul 4 '18 at 18:29

You have the right idea. Here is a simpler argument based on your idea:

If $n \le 100$ and $p$ is a prime factor of $n$, then $p \le n \le 100$. Therefore, the primes in the factorization of $100!$ are precisely the primes less than $100$ and so $101$ is not one of them.

By Wilson's theorem , $100!=(101-1)!\equiv -1\pmod{101}$, since $101$ is prime.

• This is incredibly overkill for the question at hand. Jul 4 '18 at 16:48
• Can you extend that to $101|97!$? Of that $102$ does divide $97!$. Way overkill and way underflexible. Jul 4 '18 at 17:46
• @Fimpellizieri What is or isn't overkill depends much on the situation. I don't find it impossible to imagine a situation where Wilson's theorem is one of the expected ways to answer the question. Jul 4 '18 at 19:19
• This doesn't answer the question. The question is whether the given proof is correct, not a request for a more elegant proof. Jul 4 '18 at 20:14
• @EricLippert: I think once the OP is assured in other Answers that the proposed proof verification is okay, posts like the above that connect up alternative points of view are helpful, esp. for future Readers. Jul 4 '18 at 22:02