TITLE: Prime number divisibility
QUESTION [2 upvotes]: The following line is in a proof I'm reading, and I don't understand the logic:

Let $\frac{a}{b}$ be an arbitrary element ($a$ and $b$ both integers).  Since $p$ is a
  prime, and $p$ doesn't divide $b$, the congruence $bx ≡ a$ $(mod$ $p)$ has  a solution.

So, we know $b$ is not divisible by prime $p$, $a$ is just some integer (possibly divisible by $p$).  Therefore $bx - a = py$ for some integer $x$ and $y$?  Why is this the case?

REPLY [0 votes]: Since $p\nmid b$ it follows that if $$R=\{r:r \text{ is the remainder of $s$ over $p$ for } s\in\{0,b,2b,3b,\ldots,(p-1)b\}\}$$
then $R=\{0,1,2,\ldots,p-1\}$ (if $xb$ and $yb$ leave the same remainder when divided by $p$ then $|x-y|b$ is divisible by $p\Rightarrow x=y$. Therefore $R$ has $p$ elements.)
We conclude that there is an $x\in\{0,1,\ldots,p-1\}$ such that $xb$ and $a$ leave the same remainder when divided by $p$. Hence $p\mid xb-a.$
{"set_name": "stack_exchange", "score": 2, "question_id": 327154}