2
$\begingroup$

I need to prove that there are infinitely many natural numbers $n$ for which $2n^2+3$ and $n^2+n+1$ are relatively prime.

This is not true for every $n$ (for example, $n=4$), I tried to check for odd $n$ but can't find way to prove it (I tried induction). Any ideas?

$\endgroup$
4
$\begingroup$

Any common divisor of $2n^2+3$ and $n^2+n+1$ divides $2(n^2+n+1)-(2n^2+3)$, which is $2n-1$.

Any common divisor of $2n^2+3$ and $2n-1$ divides $2n^2+3-n(2n-1)$, which is $n+3$.

And any common divisor of $2n-1$ and $n+3$ divides $7$.

Now produce infinitely many numbers $2n^2+3$ that are not divisible by $7$.

Remark: We have in essence used the Euclidean Algorithm for polynomials. If we chase down details, we find that the gcd is $1$ except when $n\equiv 4\pmod{7}$.

$\endgroup$
  • $\begingroup$ Wonderful!Can you explain me how you used Euclidean Algorithm in this steps? $\endgroup$ – Meow Oct 3 '14 at 16:50
  • 1
    $\begingroup$ When we try to find the gcd of two numbers, we divide and find the remainder. I was actually using the Euclidean Algorithm for polynomials. $\endgroup$ – André Nicolas Oct 3 '14 at 16:58

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.