Prove gcd(f(n), f(n+1))=1

Question

Let $f: N \implies N$ be the function $f(n)=n^2+n+1$. Prove for all $n \in \mathbb{N}, gcd(f(n), f(n+1))=1$. I was able to prove that both $f(n)$ and $f(n+1)$ are odd for all $n$ but now I am stuck. Any help is appreciated!

Answer 1

Suppose $d$ divides both $f(n)$ and $f(n+1)$. Then it divides their difference $$f(n+1)-f(n)=2(n+1)$$ Because, as you said $f(n)$ is odd, we must have that $d$ divides $n+1$. But note that $$f(n)=(n+1)n +1$$ So since $d$ divides both $f(n)$ and $n+1$, it must divide $f(n)-(n+1)n=1$. So $d=1$.

Answer 2

Let $p$ be a prime dividing $\gcd(f(n+1),f(n))$

We note that $$f(n+1)-f(n)=2(n+1)$$ so $p$ must divide $2(n+1)$

Since all the $f(n)$ are odd we must have $p\,|\,n+1$.

But $(n+1)^2=f(n)+n$ so $p$ must divide $(n+1)^2-f(n)=n$.

Thus $p$ divides both $n$ and $n+1$, a contradiction.

Answer 3

Hint $\ (f_n,f_{n-1}) = (\overbrace{f_n-f_{n-1}}^{\Large 2n},\,f_n) = \overbrace{(2n,n(n\!+\!1)\!\color{#c00}{+\!1})}^{\Large 2,n\ \mid\ n(n+1)\ \ \ \ \ \ \ }=1\ $ by Euclid.

Answer 4

Just do it.

$f(n+1) = (n+1)^2 + (n+1) + 1 = n^2 +2n + 1 + n + 1 + 1 = n^2 + n + 1 + 2n + 2 = f(n) + 2n + 2$.

So $\gcd(f(n+1), f(n)) = \gcd(f(n), f(n) + 2n + 2) = \gcd(f(n), 2n + 2)$.

$f(n) = n^2 + n + 1 = n^2 + \frac {2n + 2} 2$. Hmm.....

Okay.... If $n$ is even $f(n) = n^2 + n +1$ is odd. If $n$ is odd, then $f(n) = n^2 + n + 1$ is odd. So $\gcd(f(n),2) =1$ so

$\gcd(f(n), 2n + 2) = \gcd(f(n), 2(n+1)) = \gcd(f(n), n+1)$.

$f(n) = n^2 + n+ 1$ so

$\gcd(f(n), n+1) = \gcd(n^2 + n + 1, n+1) = \gcd(n^2, n + 1)$.

Let $p$ be a prime number. If $p|n^2$ then $p|n$ and $p \not \mid n+1$. So $n^2, n+1$ have no prime factors in common.

So $\gcd(n^2, n+1)=1$.