Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Salahuddin Oct 23 '12 at 7:56
    
@Salahuddin: Even if $41$ were never a GCD (as it is for $n=32$), the statement would be true. –  robjohn Oct 23 '12 at 8:57
    
@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 ? –  Ryan Oct 23 '12 at 9:34
    
@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}$. –  robjohn Oct 23 '12 at 12:24
    
@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. –  robjohn Oct 23 '12 at 16:53
show 1 more comment

4 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
Thanks Marvis. Would you mind to elaborate though, as my number theory is very weak. –  Ryan Oct 22 '12 at 19:35
    
@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$ –  Ross Millikan Oct 22 '12 at 19:39
    
@Ross Thanks both! I've understood everything except the final bit: how was 123 eliminated? :D –  Ryan Oct 22 '12 at 19:52
    
@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. –  user17762 Oct 22 '12 at 19:56
    
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. –  Ryan Oct 23 '12 at 7:25
add comment

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

share|improve this answer
    
This is a neat and elegant solution! Now I'm trying to figure out how to apply this intuition to future such problems... –  Ryan Oct 23 '12 at 7:27
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.