# Discrete Factorial + Composite numbers.

• Jan 24th 2010, 04:52 PM
Discrete Factorial + Composite numbers.
Ok, my question is: prove that all of the following numbers are composite: 1000! +2, 1000! +3, 1000+4, ....., 1000! + 1002

Now, I assume I have to start with proving that 1000! is composite or not and then prove the other numbers being added to the factorial?

Also, our class definition of composite is: A positive integer a is called composite provided there is an integer b such that 1< b < a and b|a.

Help is much appreciated!
• Jan 24th 2010, 11:28 PM
tonio
Quote:

Ok, my question is: prove that all of the following numbers are composite: 1000! +2, 1000! +3, 1000+4, ....., 1000! + 1002

Now, I assume I have to start with proving that 1000! is composite or not and then prove the other numbers being added to the factorial?

Also, our class definition of composite is: A positive integer a is called composite provided there is an integer b such that 1< b < a and b|a.

Help is much appreciated!

We know that if a number divides x and y then it divides x + y and x - y.
Well, for $\displaystyle 2\le k \le 1002$ , check that $\displaystyle k\,\,\,and\,\,\,1000!$ have at least one non-trivial divisor.

Tonio
• Jan 25th 2010, 12:11 AM
craig
Quote:

Ok, my question is: prove that all of the following numbers are composite: 1000! +2, 1000! +3, 1000+4, ....., 1000! + 1002

Now, I assume I have to start with proving that 1000! is composite or not and then prove the other numbers being added to the factorial?

Also, our class definition of composite is: A positive integer a is called composite provided there is an integer b such that 1< b < a and b|a.

Help is much appreciated!

Not sure of a formal way to prove this, but I'll try and get my point across in a clear(ish) way.

The number $\displaystyle n!$ can be written as $\displaystyle 1 \times 2 \times 3 \times ... \times (n-1) \times n$.

So your $\displaystyle 1000! = 1 \times 2 \times ... \times 999 \times 1000$, let's call this equation *.

Now first we'll deal with $\displaystyle 1000! +2, 1000! +3, 1000+4, ....., 1000! + 1000$.

For $\displaystyle 1000! + 2$, from our definition * we know that 2 is a factor, therefore $\displaystyle 1000! + 2$ is a composite number. Use the same logic for 3-1000.

$\displaystyle 1000! + 1001$, this is the same as $\displaystyle 1000! + (7 \times 11 \times 13)$. We know from * that 7, 11 and 13 are factors of $\displaystyle 1000!$, therefore $\displaystyle 1000! + 1001$ is a composite number.

Repeat this technique for $\displaystyle 1000! + 1002$

Not the most well written proof but hope it makes sense.
• Jan 25th 2010, 06:52 AM
HallsofIvy
Quote:

Ok, my question is: prove that all of the following numbers are composite: 1000! +2, 1000! +3, 1000+4, ....., 1000! + 1002

It should be obvious that n!, for n> 2, is composite, just from the definition. In fact, n! is divisible by every integer from n down.
And 1000!+ 2 is divisible by 2, 1000!+ 3 is divisible by 3, 1000!+ 4 is divisible by 4, etc. Once we get to 10001 we have to be a bit more careful: 1001 is 11*91 so 1000!+ 1001 is divisible by 11, and 1002 is divisible by 2 so 1000!+ 1002 is divisible by 2.

Quote:

Now, I assume I have to start with proving that 1000! is composite or not and then prove the other numbers being added to the factorial?

Also, our class definition of composite is: A positive integer a is called composite provided there is an integer b such that 1< b < a and b|a.

Help is much appreciated!
• Jan 25th 2010, 07:29 AM
Dinkydoe
For all $\displaystyle k$ with $\displaystyle 1 \leq k \leq 1000$ we have $\displaystyle k|1000!$

And we can write: $\displaystyle n(k) := (1000!+k) = k (\frac{1000!}{k}+ 1)$.
Hence $\displaystyle n(k)$ is composite.

case: $\displaystyle n(0)$ is trivial.

We're left with $\displaystyle n(1001), n(1002)$.

Just like HallsofIvy said: Look at prime-factorisation of 1001, 1002. For all nontrivial divisors $\displaystyle d_1|1001, d_2|1002$ we can write: $\displaystyle n(1001) = d_1(\frac{1000!}{d_1}+ \frac{1001}{d_1})$ and $\displaystyle n(1002) = d_2(\frac{1000!}{d_2}+ \frac{1002}{d_2})$.

This is because $\displaystyle d_1,d_2 < 1000$ hence $\displaystyle d_1,d_2|1000!$.