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.


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


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.