1
$\begingroup$

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

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

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$.
$\endgroup$
  • $\begingroup$ I got to that result doing polynomial long division on $n^2+1$. Thanks!! $\endgroup$ – YoTengoUnLCD Apr 16 '15 at 20:00
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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.