# If $d|n-1$ and $d|n^2+2$ show $d|3$

If $$d \mid n-1$$ and $$d \mid n^2+2$$, show that $$d\mid3$$

Attempt:

$$n-1=\alpha d \tag 1$$

$$n^2+2=\beta d \tag 2$$

for some $$\alpha,\beta$$.

Now we must show $$3=\gamma d$$ for some $$\gamma$$.

Adding (1) and (2), we get $$n^2+n+1=(\alpha+\beta)d = \gamma d$$

I'm having some trouble from here onwards. Have I done the steps correctly thus far? Thanks!

• Hint: $d \mid (n-1)(n+1)$. – Robert Israel Mar 25 at 1:55
• How do we know this? – Programmer Mar 25 at 1:58
• If $n-1 = \alpha d$, what do you suppose $(n-1)(n+1)$ is? – Robert Israel Mar 25 at 2:18

$$d$$ divides $$n^2+2-(n-1)=n^2-n+3=n(n-1)+3$$ this implies that $$d$$ divides $$3$$ since it divides $$n(n-1)$$.

$$(n-1)=ad, n^2+2=bd$$ implies that $$n^2+2-(n-1)=bd-ad=n(n-1)+3=and+3$$ implies that $$and+3=(b-a)d$$ and $$3=(b-a-an)d$$.

If $$d|n-1$$ and $$d|n^2+2,$$ then $$d|(n^2+2)-(n-1)(n+1)=3.$$

Let $$n-1=m$$. Then $$n^2+2=(m+1)^2+2=m^2+2m+3$$. If $$d\mid m$$ and $$d\mid m^2+2m+3$$, then....

$$\bmod d\!:\ n\!-\!1\equiv 0\,\Rightarrow\,\color{#c00}{n\equiv 1}\,$$ so $$\, 0\equiv \color{#c00}n^2+2\equiv 3$$

If congruences are unfamiliar then we can divide with remainder.

Recall $$\ f(n) = (n-1)q(n)+ f(1)\ \$$ [Polynomial Remainder Theorem]

thus $$\, d\mid f(n),(n-1)\,\Rightarrow\, d\mid f(1)\ [= 3\ \ {\rm for}\ \ f(n) = n^2+2]$$

Hint:

If $$d|a$$ and $$d|b$$, then $$d|ka+lb$$

Another shortcut: $$n^2 + 2 = ((n-1)+1)^2 + 2 = k(n-1) +3 \stackrel{d|(n^2+2), d|(n-1)}{\Longrightarrow}d|3$$