0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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...." $\endgroup$ – Bill Dubuque Feb 9 at 21:57
  • $\begingroup$ Thanks, fixed (I really was thinking of $d$ being a prime number). $\endgroup$ – Stefan Lafon Feb 15 at 21:49
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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