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

Question

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!

Answer 1

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

Answer 2

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

---

If congruences are unfamiliar then we can divide with remainder.

Recall $\ \color{#0a0}{f(n) = (n-1)}q(n)+ \color{#c00}{f(1)}\ \ $ [Polynomial Remainder Theorem]

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

Answer 3

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

Answer 4

Hint:

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

Answer 5

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

Answer 6

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