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

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!

## 4 Answers

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

• The reasoning appears wrong. It is not true that $\,d\neq 2,\ d\mid 2m\,\Rightarrow\, d\mid m.\,$ But that is true if $\,d\,$ is odd. You can fix it by deleting the sentence "Can $d$ be equal to $2$?" and replacing it by "since $f(n)$ is odd and $\,d\mid f(n)$ we know $d$ is odd so we conclude...." – Bill Dubuque Feb 9 at 21:57
• Thanks, fixed (I really was thinking of $d$ being a prime number). – Stefan Lafon Feb 15 at 21:49

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.

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

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.