# Why is the product of two consecutive integers $n \cdot( n+1) \forall n > 2$ guaranteed to have at least two prime factors?

I was reading this paper: http://fermatslibrary.com/s/a-new-proof-of-euclids-theorem and became confused when reading this line:

Since $n$ and $n + 1$ are consecutive integers, they must be coprime. Hence the number $N_2 = n(n + 1)$ must have at least two diﬀerent prime factors

I see that this is true in practice when writing out several examples, but was hoping for an explanation of why? (which the paper left out). I understand why $n$ and $n+1$ are co-prime, but not why that implies that $n\cdot(n+1)$ has at least two different prime factors. What does being co-prime have to do with this?

Any insight would be really helpful.

EDIT:

I believe I understand now:

1) $n$, $n+1$ have no factors in common except $1$

2) If $n$, $n+1 \ge 2$ they have at least one prime factor

3) From (1) these factors must be different, so there must be at least two different prime factors

• Can you spot one prime factor they all have in common? – πr8 Jan 12 '16 at 21:25
• If $n \ge 2$, then $n$ has at least one prime factor, and so does $n + 1$. They can't be the same. – Qiaochu Yuan Jan 12 '16 at 21:26
• Coprime means they have no factor in common. Thus, any prime which divides $n$ cannot divide $n+1$, because if it did, it would be a common factor, contrary to coprimeness. Similarly any prime which divides $n+1$ cannot divide $n$. – ForgotALot Jan 12 '16 at 21:28
• What numbers have less than 2 different prime factors? That may also help to see this problem from a different angle. – JB King Jan 12 '16 at 21:42
• @πr8 oh I see, this sequence can only generate even numbers because you will always be multiplying an odd number by an even number. So $2$ will always be a prime factor. – Hunter McMillen Jan 12 '16 at 21:48

## 5 Answers

If $n$ is even, it has $2$ as a prime factor, and $n + 1$ is odd so it doesn't -- it must have some other prime factor. There you go. (Same deal if $n$ is odd).

• All of the other answers were extremely helpful, but this one made the concept click for me. Thank you. – Hunter McMillen Jan 12 '16 at 21:41
• @HunterMcMillen: I'm glad! :-) – Eli Rose Jan 12 '16 at 22:24

Using the Euclidean Algorithm, $\gcd(n,n+1) = \gcd(n,1) = 1$. Since they are coprime, they don't share any prime factors. Since every positive integer greater than or equal to $2$ is composed of prime factors, the product $n(n+1)$ must have at least two different prime factors for $n \geq 2$ . The same applies for negative numbers $n$ less than or equal to $-2$. For the other cases, namely $\{-1,0\}$ and $\{0,1\}$, $0$ has infinitely many prime factors.

If $p$ divides $n$ and $n+1$, then $p|n-(n+1)=1$; so $gcd(n,n+1)=1$. Let $p,q$ primes such that $p|n$ and $q|n+1$. Therefore $p,q|n(n+1)$.

If $n \geq 2$, pick a prime $p$ which divides $n$ and a prime $q$ which divides $n+1$. Such primes exists because $n, n+1 >1$.

Now if $p \neq q$, $p=q$ are two distinct primes which divide $n(n+1)$. SO the only possible issue would be if $p=q$. But this is not possible, because it would mean $p|n, p|n+1$ and hence $p| (n+1)-n$.

Assume $n>1$.

$n,n+1$ are adjacent integers, so at least one of them is even, meaning that $n(n+1)$ is even.

$n(n+1)$ will also have a factor other than $2$, as otherwise it would have to be a power of $2$. But $n(n+1)=2^k$ means that $n,n+1$ must both be powers of $2$. One of them is odd, meaning that either $n$ or $n+1$ is $1$ (the only odd power of 2). Given that $n>1$, this can't be true.

So, $n(n+1)$ has a factor of $2$, but can't be factored as $2^k$. So it must have another prime factor somewhere.