For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer

[Math100]

Homework Statement

For $n>1$, show that every prime divisor of $n!+1$ is an odd integer that is greater than $n$.

Relevant Equations

None.

Proof:

Suppose for the sake of contradiction that there exists a prime divisor of $n!+1$,
which is an odd integer that is not greater than $n$.
Let $n>1$ be an integer.
Since $n!$ is even,
it follows that $n!+1$ is odd.
Thus $2\nmid (n!+1)$.
This means every prime factor of $n!+1$ is an odd integer.
Let $p$ be a prime factor of $n!+1$ such that $p\leq n$.
Then we have $p\mid n!$ and $p\mid (n!+1)$.
Thus $p\mid 1$, which implies that $p=\pm 1$.
This is a contradiction because $p$ must be a prime number where $p\neq \pm 1$, so $p\nleq n$.
Therefore, for $n>1$, every prime divisor of $n!+1$ is an odd integer that is greater than $n$.

 

[PeroK]

Looks right, but a bit laboured.

 

[Math100]

Looks right, but a bit laboured.

What do you mean by 'laboured'? I do not understand this.

 

[PeroK]

What do you mean by 'laboured'? I do not understand this.

This, for example:

Since $n!$ is even,
it follows that $n!+1$ is odd.
Thus $2\nmid (n!+1)$.
This means every prime factor of $n!+1$ is an odd integer.

Could simply be replaced by this:

Since $n!$ is even, every prime factor of $n!+1$ is odd.

 

[Math100]

I guess I wrote too many words.

 

[PeroK]

I guess I wrote too many words.

The problem will come when you get more difficult proofs. Too much detail will make such proofs unreadable.
You have some good ideas that are not easy to see, but then you take 3-4 lines to convince us that an odd number is not even!

 

[pbuk]

I guess I wrote too many words.

In some places, but you have not written any words to justify the key statement of the proof:

Let $p$ be a prime factor of $n!+1$ such that $p\leq n$.
Then we have $p\mid n!$

Why?

 

[mathwonk]

SPOILER ALERT!if 1<p ≤ n, then p divides n!, so the remainder after dividing (n!+1) by p is 1. Hence p does not divide n!+1.

This is the key observation in Euclid's original proof that there is no limit to the number of primes. I admit I myself found it mysterious when I first saw it. I just didn't realize that if p divided both n! and n!+1 then p would divide 1. This is the famous and useful (and trivial) "3 term principle".

 

[pbuk]

This is the famous and useful (and trivial) "3 term principle".

Yes but the exercise is to prove it. I don't see how you can do that without something like "from the definition of the factorial, every p not greater than n divides n!".

 

[mathwonk]

the 3 term principle says that if p divides both a and b, and a+b = c, then p divides c. or also if p divides any 2 of the 3 terms, a,b,c, then it divides the third. this is a pretty easy exercise.

"from the definition of the factorial, every p not greater than n divides n!".

forgive me, this is so obvious as to not seem to be needed to be mentioned. but you are right, this is a key step. i just assumed someone using the notation n! knows what it means. or rather, when outlining a short "proof" i tend to omit steps which i think have been rendered so obvious as to suggest themselves to the reader.

In this example of course, if the reader is someone who does not notice that n! is divisible by every integer between 1 and n, then your explanation is more appropriate than mine. of course you are right, the clearest explanation is always one that gives all the steps.
cheers!