Arithmetic progression - terms divisible by a prime. 
If $p$ is a prime and $p \nmid b$, prove that in the arithmetic progression $a, a+b, a +2b, $ $a+3b, \ldots$, every $p^{th}$ term is divisible by $p$.

I am given the hint that because $\gcd(p,b)=1$, there exist integers $r$ and $s$ satisfying $pr+bs=1$.  Put $n_k$ = $kp-as$ for $k = 1,2,...$ and show that $p \mid a + n_k b$.
I get how to solve the problem once I apply the hint, but I am unsure how to prove the hint.  How do I know what to set $n_k$ to?

Apply the extended Euclidean algorithm to find $r$ and $s$.
Suppose $p=31$, $b=23$
$$\begin{array}{c|c|c}
pr+bs & r & s \\
\hline p=31 & 1 & 0 \\
b=23 & 0 & 1 \\ \hline
8 & 1 & -1 \\
7 & -2 & 3 \\
1 & 3 & -4 \\
\end{array}$$
$31\cdot 3 + 23 \cdot -4 = 93-92 = 1 \quad \checkmark$
The process works by, at each step, subtracting a multiple of the last line from the line above it to get a smaller number. So $23-2\times 8 = 7$, for example, and the same operations are applied to the $r$ and $s$ values.

Then looking at $n_k=kp-as$, we see that
$\begin{align}a+n_kb &= a+bkp-bas \\
&= a+bkp-a(1-rp) \\
&= a+bkp-a+arp \\
&= p(bk+ar)\\
\end{align}$
and so $p\mid a{+}n_kb$ as required. Note that successive values of $n_k$ are different by exactly $p$ to complete the proof.
