# Hints for solving this Number Theory problem on divisibility

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.

• Hint: $d$ divides their difference as well ! – r9m Dec 27 '14 at 10:14
• 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 '14 at 13:08

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$

• That is more than the hint asked for – Mark Bennet Dec 27 '14 at 10:17
• @DevarshRuparelia, Was it more than hint? – lab bhattacharjee Dec 27 '14 at 10:20
• (+1) .. also I think the downvote is a bit harsh in this context ! – r9m Dec 27 '14 at 10:21
• You basically showed how to solve the problem, that is more than a hint. – Henrik supports the community Dec 27 '14 at 10:22
• @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. – Devarsh Ruparelia Dec 27 '14 at 10:22