1
$\begingroup$

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 different 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

$\endgroup$
  • 3
    $\begingroup$ Can you spot one prime factor they all have in common? $\endgroup$ – πr8 Jan 12 '16 at 21:25
  • 1
    $\begingroup$ If $n \ge 2$, then $n$ has at least one prime factor, and so does $n + 1$. They can't be the same. $\endgroup$ – Qiaochu Yuan Jan 12 '16 at 21:26
  • 2
    $\begingroup$ 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$. $\endgroup$ – ForgotALot Jan 12 '16 at 21:28
  • 1
    $\begingroup$ What numbers have less than 2 different prime factors? That may also help to see this problem from a different angle. $\endgroup$ – JB King Jan 12 '16 at 21:42
  • 1
    $\begingroup$ @π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. $\endgroup$ – Hunter McMillen Jan 12 '16 at 21:48
2
$\begingroup$

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).

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

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.