0
$\begingroup$

Looking at sequences a=u+n^2, that there is a common divisor of 4u+1 between a2u and a2u+1, and now i need to prove that this is the greatest common divisor between terms au and au+1. This is a part where i'm stuck, i know that au+1 - au is equal to 2n+1, but dont know where to go next?

$\endgroup$
  • $\begingroup$ Please use the dollar sign markups to put your expression into Latex. I take it you mean sequences of the form $a_{n} = u + n^{2}$ for some (non-negative?) integer $u$. What does au and au+1 mean? Is the first one $a_{n}u$ or $a_{u}$? Is a2u+1 $a_{2}u + 1$ or $a_{2u+1}$. In this case it can be guessed from the question but it is still a good habit to get into $\endgroup$ – AlphaNumeric Sep 16 '16 at 10:34
4
$\begingroup$

Fix $n$ and let $d$ be the common divisor of $a_{n} = 100 + n^{2}$ and $a_{n+1}=100 + (n+1)^{2}$. Then $d$ divides their difference $$ a_{n+1} - a_{n} = 2n+1. $$ Furthermore, it divides the following linear combination: $$ 2a_{n} - n(2n+1) = 200 + 2n^{2} - 2n^{2} - n = 200 - n. $$ Again, $d$ divides the linear combination $$ 2(200 - n) + (2n + 1) = 400 + 1 = 401. $$ Since $401$ is prime, the only posibilities for $d$ are $1$ and $401$.

One can show that $401$ divides $100+n^{2}$ if and only if $n$ has residue $200$ or $201$ when divided by $401$. Then, the answer is: $$ d = \begin{cases} 401 \text{ if $n$ has residue $200$ or $201$ when divided by $401$,}\\ ~~1~~ \text{ in any other case}. \end{cases} $$

$\endgroup$

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.