# Question In Elementary Number Thoery

In the book, "Elementary Number Theory 6th Edition(David M. Burton)", I don't know how to solve this problem.

P.58 number 18 (a)

If p is a prime and b is not divisible by p, prove that in the arithmetic progression a, a+b, a+2b, .... every pth term is divisible by p (Hint : Because gcd(p, b)=1, there exist integers r and s satisfying pr+bs=1. Put n(k)=kp-as for k = 1,2,3... and show that a+n(k) is divisible by p)

By the above hint, I can result in pl(a+n(k)), but after that, I don't know how to continue this problem. Thank you very much if you give me some help.

## 1 Answer

There is a typo in post as written at this time. We will use $n_k$ instead of $n(k)$.

We want to prove that $p$ divides $a+n_k b$. The divisibility follows from the definition of $n_k$. For $$a+n_k b=a+(kp-as)b=a+kpb-asb=a+kpb-a(1-pr)=kpb+apr.$$ Since $a+n_kb=p(kb+ar)$, we have shown that $p$ divides $a+n_k b$.

There is an integer $k$ such that $kp-as\ge 0$. For that $k$, the number $a+n_{k}b$ is in our arithmetic sequence.

When we add $1$ to $k$, then we are looking at the term $a+n_{k+1}b$, which is $a+((k+1)p-as)b$. This is $a+(kp-as)b+pb$, so we have advanced in the sequence by $p$ terms.

When we add $1$ to $k+1$, we are looking at $a+((k+2)p-as)b$, which is $a+(kp-as)b+2pb$, so we have advanced in the sequence by another $p$ terms.

The same pattern continues. Every time we increment $k$ by $1$, we advance in the sequence by $p$ terms.

There is a simpler way of seeing what's happening. Once we have found a single $n_0$ such that $a+n_0b$ is divisible by $p$, it is clear that $a+ (n_0+mp)b$ is divisible by $p$ for every integer $m$. For $a+(n_0+mp)b=a+n_0b+mp$.