# If $p$ is a prime and $(a,b)=1$ then there is a $k \in \{ 0, \dots, p-1 \}$ s.t. $p | (a-kb)$?

I'm working on a problem regarding $$p$$-adic numbers. I boiled down the problem to an elementary problem in number theory. I'm wondering if the following statement is true:

If $$p$$ is a prime and $$a,b \in \mathbb{Z}$$ with $$(a,b)=1$$ then there is a $$k \in \{ 0, \dots, p-1 \}$$ s.t. $$p$$ devides $$a-kb$$.

• What do you mean with $(a,b)=1$?? gcd maybe? – Ahlfkushevich Feb 13 at 10:27
• Yes, the greatest common divisor – Muzi Feb 13 at 10:28
• what about $a=p+1, b=k=1$? – Chris Feb 13 at 10:29
• @Chris I think $a,b$ are given and cannot be chosen freely. – James Feb 13 at 10:30

$$p\mid a-kb$$ means that $$a-kb=0\mod p$$. In other words, $$a=kb\mod p$$. $$a\mod p$$ is a residue class and one of $$\{0,\dots, p-1\}$$. The same is true for $$k$$ and $$b$$ and $$kb$$. So your question reduces to asking whether given any $$a,b\in \{0,\dots, p-1\}$$ there is some $$k\in\{0,\dots,p-1\}$$ such that $$a=bk$$. But this is true and the $$k$$ is even uniquely determined. Why? Because $$\mathbb Z_p$$ forms a group!

$$\mathbb Z_p$$ being a group means that there exists an inverse $$b^{-1}\in\mathbb Z_p$$ and you can define $$k=ab^{-1}\in\mathbb Z_p$$.

Note that you need $$(a,b)=1$$ only to assure that $$b\neq 0$$.

Since you want to solve $$a \equiv kb \;(mod \; p)$$ and because $$p$$ is prime, then $$\frac{\mathbb{Z}}{p\mathbb{Z}}$$ is a field, and so any element has and inverse except the $$0$$. So then there always exist that $$k$$ unless $$b \equiv 0 \; (mod \; p)$$
Case $$1$$: $$a\equiv b \mod p$$
$$a\equiv b \mod p\iff a-b\equiv 0 \mod p\iff k=1$$ and we're done!
Case $$2$$: $$a\not\equiv b \mod p$$
This implies that $$a, b$$ have different residue classes $$\mod p$$. Since the set $$\{0,..., p-1\}$$ includes all possible residues $$\mod p$$, you can always choose one such that $$a-kb\equiv 0 \mod p \iff p\mid a-kb$$