Hints for solving this Number Theory problem on divisibility

Question

Find all positive integers $d$ such that $d$ divides both $n^{2}+1$ and $(n + 1)^{2}+1$ for some integer $n$.

Currently what I am thinking of is like manipulating $n^{2}+1$ and finding out the answer. Please guide me on how to move forward with this problem.

HINTS ONLY

Thanks for helping.

Please, try to make the title of your question more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. — Martin Sleziak, Dec 27, 2014 at 13:08

lab bhattacharjee · Accepted Answer · 2014-12-27 10:25:49Z

3

The idea is to reach at a constant divisible by $d$

If $d$ divides $a,b;d$ must divide $ax+by$ for integers $a,b,x,y$

So, $d$ must divide $1\cdot(n+1)^2+1(-1)\cdot(n^2+1)=2n+1$

So, $d$ must divide $n\cdot(2n+1)+(-2)\cdot(n^2+1)=n-2$

Follow the pattern to find $d$ must divide $5$

answered Dec 27, 2014 at 10:15

lab bhattacharjee

273k18 gold badges203 silver badges321 bronze badges

$\begingroup$ That is more than the hint asked for $\endgroup$
– Mark Bennet
Dec 27, 2014 at 10:17
$\begingroup$ @DevarshRuparelia, Was it more than hint? $\endgroup$
– lab bhattacharjee
Dec 27, 2014 at 10:20
1

$\begingroup$ (+1) .. also I think the downvote is a bit harsh in this context ! $\endgroup$
– r9m
Dec 27, 2014 at 10:21
$\begingroup$ You basically showed how to solve the problem, that is more than a hint. $\endgroup$
– Henrik supports the community
Dec 27, 2014 at 10:22
$\begingroup$ @labbhattacharjee I think so but not too much that it can be downvoted.I would say remove the last step and it would be fine. $\endgroup$
– Devarsh Ruparelia
Dec 27, 2014 at 10:22

| Show 3 more comments

1 Answer 1