4
$\begingroup$

Prove that for any integer $n$, $\gcd (3n^2+5n+7, n^2+1)=1$ or $41$.

The following answer is convoluted because I've intentionally created excess solutions. However, I can't figure out how to eliminate them! Anyone?

Let $$d=\gcd (3n^2+5n+7, n^2+1).$$ Then $$d|[(3n^2+5n+7)-3(n^2+1)]$$ $$d |(5n+4)$$ And $$d | [5(3n^2+5n+7)-3n(5n+4)]$$ $$d |(13n+35)$$ And $$d |[5(13n+35)-13(5n+4)]$$ $$d |123$$ Therefore, $d= 1$ or $3$ or $41$ or $123$.

  • 0
    I guess people stopped somewhere. You still have to prove that 41 is indeed, the GCD for some such expressions, without which the solution is incomplete.2012-10-23
  • 0
    @Salahuddin: Even if $41$ were never a GCD (as it is for $n=32$), the statement would be true.2012-10-23
  • 0
    @robjohn Logically, yes, but isn't that like saying that the statement would be true if d had been shown to be 1 or 2 or ... or 100000 ? Do you think it might be a good idea to end such a proof by giving a possible n for each value of d found, to prove that that d is indeed a possible gcd ?2012-10-23
  • 0
    @Ryan: point taken. The aim here is to remove all the impossibilities. I retract my statement, except that the GCD is $41$ when $n\equiv32\pmod{41}$.2012-10-23
  • 0
    @Ryan: I have a complete proof using Gaussian factorization (which is used in Bill Dubuque's answer) that $(3n^2+5n+7,n^2+1)=41$ iff $n\equiv32\pmod{41}$. I can post if after the homework is due, if you wish.2012-10-23
  • 0
    @robjohn My question isn't actually homework, and if you don't mind to add your proof, I'm sure it would be beneficial. Cheers.2012-10-23

4 Answers 4

6

From your last step, we get that $d = 1,3,41,123$.

Recall that $$n^2 \equiv 0,1 \pmod{3} \text{ (Why?)}$$ Hence, $3$ (or) $123$ does not divide $n^2+1$.

EDIT

Note that any $n$ is either $0 \pmod{3}$ or $\pm1 \pmod{3}$.

Hence, $n^2 \equiv 0,1 \pmod{3}$. (Recall that if $x \equiv y \pmod{a}$, then $x^k \equiv y^k \pmod{a}$.)

Hence, $n^2 + 1 \equiv 1,2 \pmod{3}$. This means that $3$ does not divide $n^2+1$. Hence, $3$ cannot divide any divisor of $n^2+1$. This enables us to rule out $d=3$ and $d=123$.

  • 0
    Thanks Marvis. Would you mind to elaborate though, as my number theory is very weak.2012-10-22
  • 0
    @Ryan: Working $\pmod 3, 0^2=0, 1^2=1, 2^2=1,$ so $n^2+1=1$ or $2$. Therefore $3 \nmid n^2+1$2012-10-22
  • 0
    @Ross Thanks both! I've understood everything except the final bit: how was 123 eliminated? :D2012-10-22
  • 0
    @Ryan $3$ divides $123$. So if $123$ were to divide $n^2+1$, then $3$ will divide $n^2+1$, which is what we have ruled out.2012-10-22
  • 0
    Oh thank you, now I see it: Because 3 cannot divide $n^2+1$, any multiple of 3 also can't divide $n^2+1$. Thanks Marvis for your response, and I'm glad I created this problem; it's been educational.2012-10-23
5

Or, you can write $$(-5n+4)(3n^2+5n+7)+(15n+13)(n^2+1)=41 \ .$$

  • 0
    This is a neat and elegant solution! Now I'm trying to figure out how to apply this intuition to future such problems...2012-10-23
1

Hint $\, $ Let $\rm\:d = gcd$, so $\rm\:d\:|\ i^2\!+1,\, 7+5\,i+3\,i^2.\:$ Then, like taking norms of Gaussian integers, $$\rm\:mod\ d\!:\,\ i^2\equiv -1\ \Rightarrow\ 0\equiv 7+5\,i+3\,i^2\equiv 4+5\,i\ \Rightarrow\ 0\equiv (4+5\,i)(4-5\,i)\equiv 4^2\!+5^2\equiv 41$$

0

Suppose that $$ (3n^2+5n+7,n^2+1)=(5n+4,n^2+1)\ne1\tag{1} $$ then either $$ (5n+4,n+i)=(4-5i,n+i)\ne1\tag{2} $$ or $$ (5n+4,n-i)=(4+5i,n-i)\ne1\tag{3} $$ Since $4-5i$ is a Gaussian prime, $(2)\Rightarrow4-5i\,|\,n+i$. That is, $$ \frac{n+i}{4-5i}=\frac{(4n-5)+(5n+4)i}{41}\in\mathbb{Z}[i]\tag{4} $$ which is true if and only if $n\equiv32\pmod{41}$.

Since $4+5i$ is a Gaussian prime, $(3)\Rightarrow4+5i\,|\,n-i$. That is, $$ \frac{n-i}{4+5i}=\frac{(4n-5)-(5n+4)i}{41}\in\mathbb{Z}[i]\tag{5} $$ which is true if and only if $n\equiv32\pmod{41}$.

Thus, $(1)$ implies either $$ (2)\Rightarrow4-5i\,|\,(5n+4,n^2+1)\text{ iff }n\equiv32\pmod{41}\tag{6} $$ or $$ (3)\Rightarrow4+5i\,|\,(5n+4,n^2+1)\text{ iff }n\equiv32\pmod{41}\tag{7} $$ Therefore, $$ (1)\Rightarrow n\equiv32\pmod{41}\tag{8} $$ It is easy to verify that $$ n\equiv32\pmod{41}\Rightarrow41\,|\,(3n^2+5n+7,n^2+1)\tag{9} $$


Again, $(1)$ implies either $$ (2)\Rightarrow4-5i\,|\,(3n^2+5n+7,n^2+1)\Rightarrow4+5i\,|\,(3n^2+5n+7,n^2+1)\tag{10} $$ or $$ (3)\Rightarrow4+5i\,|\,(3n^2+5n+7,n^2+1)\Rightarrow4-5i\,|\,(3n^2+5n+7,n^2+1)\tag{11} $$ Therefore, $$ (1)\Rightarrow41=(4-5i)(4+5i)\,|\,(3n^2+5n+7,n^2+1)\tag{12} $$ Finally, as Pambos points out, the Euclidean Algorithm yields $$ (15n+13)(n^2+1)-(5n-4)(3n^2+5n+7)=41\tag{13} $$ Therefore, $$ (3n^2+5n+7,n^2+1)\,|\,41\tag{14} $$