Is there anything I can tell about $\gcd(x^2+1,x^2+4x+5)$ for any given integer $x$? I believe I've seen similar questions in the past, though I don't remember any details or what to search for. I did write a computer program to check the first $50$ values which seem to alternate between $1$ and $2$, but how do I prove this?
Asked
Active
Viewed 86 times
3
-
2$x^2+4x+5=(x^2+1)+4(x+1)$, $x^2+1=2+(x+1)(x-1)$. – Andrés E. Caicedo Mar 03 '14 at 08:03
-
What are the "first" $50$ values? – alex Mar 03 '14 at 08:03
-
@alex: I think he's evaluating $f(x) = \gcd(x^2+1, x^2+4x+5)$ on small positive integers, which has $f(1) = \gcd(2,10)=2$ and $f(2) = \gcd(5,17)=1$. – Eric Towers Mar 03 '14 at 08:09
-
@Eric Towers Ops... I misunderstood the question, I thought he had to find the gcd in the polynomial ring... – alex Mar 03 '14 at 08:14
1 Answers
6
If $d$ divides both
$d$ will divide $x^2+4x+4-(x^2+1)=4(x+1)$
$d$ will divide $4(x^2+1)-4(x+1)(x-1)=8$
Now if $x$ is even $x^2+1$ is odd $\implies(x^2+1,x^2+4x+5)=1$
If $x$ odd, $x^2\equiv1\pmod8\iff x^2+1\equiv2\implies(x^2+1,x^2+4x+5)=2$
lab bhattacharjee
- 274,582