Divisibility Proof Help

Question

Show that for all integers $j$, if $d$ is an integer such that $j \mid k+8$ and $d \mid k^2+1$ then $j \mid 65$.

I'm having a lot of trouble, with solving this proof. I first rewrote the equations as,

$$\begin{align*} aj &= k + 8, \\ bj &= k^2 + 1. \end{align*} $$

Then by adding them together,

$$\begin{align*} aj + bj &= k^2 + k + 9, \\ (a+b)j &= k^2 + k + 9. \end{align*}$$

But I am not sure how to proceed from here. Any help would be greatly appreciated.

Answer 1

$d \mid (n+8) \Rightarrow d \mid (n+8)^2$

So: $d \mid (n^2 + 16n + 64) \tag{1}$

Also: $d \mid (n^2 + 1) \tag{2}$

So $d$ divides this difference:

$d \mid (n^2 + 16n + 64) - (n^2 + 1) \Rightarrow d\mid (16n + 63) \tag{3}$

Now since $d \mid (n+8)$ we get:

$d \mid 16(n+8) \tag{4}$

$d \mid (16n+128) \tag{5}$

Finally from $(5)$ and $(3)$ we get that $d$ divides this difference:

$(16n+128) - (16n + 63) = 65$

Answer 2

From $d \mid n + 8$, you have

$$\begin{equation}\begin{aligned} & n + 8 \equiv 0 \pmod d \\ & n \equiv -8 \pmod d \\ & n^2 \equiv 64 \pmod d \\ & n^2 + 1 \equiv 65 \pmod d \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Since $d \mid n^2 + 1$, from \eqref{eq1A}, you get $n^2 + 1 \equiv 65 \equiv 0 \pmod d \implies d \mid 65$.