0
$\begingroup$

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!

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Hint:

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

$\endgroup$
1
$\begingroup$

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

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