# Find $GCD(n^2+1,n+1)$

$GCD(n^2+1,n+1)$, $n\in \mathbb{N}$

What I did: $n^2+1=(n-1)(n+1) + 0$

So I thought $(n^2+1:n+1)=n+1$

But that doesn't seem to be the case: $n=2$

$n^2+1=5$

$n+1=3$

$GCD(5,3)=1$

Why is the GCD here $n-1$?

E: I just realized (thanks to a comment) I made a mistake, as $n^2+1\neq(n+1)(n-1)$.

Edit2: I'm sorry guys, I don't understand most of your answers. We haven't yet studied things like the floor function in my class. I know a bit of mod arithmetic and euclid's algorithm.

• Sorry, but $n^2+1$ is not equal to $(n+1)(n-1)+0$ – imranfat Apr 15 '15 at 23:43
• @imranfat Oh damn, I kept reading $n^2+1$ as $n^2-1$ in my head. – YoTengoUnLCD Apr 15 '15 at 23:44
• It happens to all of us ...:) – imranfat Apr 15 '15 at 23:45

We have $$(n^2+1) - (n-1)(n+1) = 2$$ Hence, if $d = \gcd(n^2+1,n+1)$, then $d$ divides $2$. Hence, $d$ has to be $1$ or $2$.

• If $n$ is even, $n^2+1$ and $n+1$ are both odd, hence $\gcd(n^2+1,n+1) = 1$.
• If $n$ is odd, $n^2+1$ and $n+1$ are both even, hence $\gcd(n^2+1,n+1) = 2$.
• I got to that result doing polynomial long division on $n^2+1$. Thanks!! – YoTengoUnLCD Apr 16 '15 at 20:00

Hint $\ \gcd(f(n),n\!-\!a) = \gcd(f(a),n\!-\!a)\,$ by the Euclidean algorithm, since,

${\rm mod}\ n\!-\!a\!:\,\ n\equiv a\,$ so $\,f(n)\equiv f(a)\,$ by the Polynomial Congruence Rule, for $\,f(x)\,$ any polynomial with integer coefficients.  Yours is $\,f(x) = x^2+1,\,$ and $\,a = -1.$

If you picture doing the Euclid algorithm, it terminates within two steps:

$$n^2+1 = (n-1) \cdot (n+1) + 2 \\ n+1 = \left\lfloor \frac{n+1}{2} \right\rfloor \cdot 2 + [n \text{ even}]$$ So $$\text{gcd} (n^2+1,n+1) = \left\{ \begin{array}{cl} 1 & \text{if } n \text{ even} \\ 2 & \text{if } n \text{ odd} \end{array} \right.$$

• I'm sorry I don't understand how you got to that second step. – YoTengoUnLCD Apr 16 '15 at 0:03