# Prime number divisibility

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?

-
By Euclid's algorithm, the equation $ax+by=c$ has solutions in $x,y$ integers if and only if $\gcd(a,b)$ is a divisor of $c$. –  Álvaro Lozano-Robledo Mar 11 '13 at 4:18
The first quoted sentence does not make sense (and is not used later). It would help if you provided precise quotes, and further context, e.g. where is the fraction used? –  Math Gems Mar 11 '13 at 5:02

For all prime numbers $p$, the ring $\mathbb{Z}_p$ of integers modulo $p$ is a field, meaning that every element of $\mathbb{Z}_p$ other than $0$ has a multiplicative inverse. Let $[b]$ be the element of $\mathbb{Z}_p$ corresponding to $b$. Since $p$ doesn't divide $b$, we know that $[b] \neq 0$ in $\mathbb{Z}_p$, and so $[b]$ has a multiplicative inverse $[b]^{-1}$ in $\mathbb{Z}_p$.

Let $c$ be some integer whose corresponding element in $\mathbb{Z}_p$ is $[b]^{-1}$. Since $[b] \cdot [b]^{-1} = 1$ in $\mathbb{Z}_p$, $b c \equiv 1 \pmod p$. Let $x = c a$; then $b x = b c a$, and so $b x \equiv a \pmod p$.

-
I'm very close to understanding (upvote!), but I'm not totally following. I get that if we're in $\mathbb{Z}_p$, b has an inverse, but we're not in $\mathbb{Z}_p$? Or basically, b inverse is the inverse that it WOULD be in $\mathbb{Z}_p$, and therefore works in this context? –  Casey Patton Mar 11 '13 at 4:22
Essentially, yes: the inverse from $\mathbb{Z}_p$ also works in this context. I just edited my answer to make the distinction between $\mathbb{Z}$ and $\mathbb{Z}_p$ clearer. I feel like the phrase "corresponding element" isn't the best term for me to use here, but hopefully it's clear what I mean. –  Tanner Swett Mar 11 '13 at 4:31
Awesome, I get it now. I wonder if there's a simpler way to show this though. The proof states this line as though this should just be intuitive, while it clearly requires a bit of logic. This leads me to believe maybe there's some easier, intuitive way to understand it. –  Casey Patton Mar 11 '13 at 4:42
Casey, what it requires is not intuition or logic but experience. The author expected readers to be familiar with the theorem that says that if $\gcd(b,n)=1$ then $bx\equiv a\pmod n$ has a solution, together with some other simple facts about prime numbers. These are things one will know, if one has studied elementary number theory. The author assumes one has done so. –  Gerry Myerson Mar 11 '13 at 4:57
If further clarity is needed, as $p$ does not divide $b$, we have $gcd(b, p) = 1$. This implies existence of integers $m, n$ s.t. $mb + np = 1$. So $b(am) + anp = a$ after multiplying with $a$. Now look at this equation $\mod p$. –  Macavity Mar 11 '13 at 5:24

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

-

Recall the following equivalent translations between equalities in quotient rings, congruences, and linear Diophantine equations:

$$\begin{eqnarray}\rm (b\!+\!n\Bbb Z)(x\!+\!n\Bbb Z) &=\,&\rm\: a\!+\!n\Bbb Z \,\in\, \Bbb Z/n\Bbb Z\\ \rm [b]\,[x] &=\,&\rm [a]\,\in\,\Bbb Z/n\Bbb Z\\ \rm b\,x\, &\equiv\,&\rm\: a\ \ \,(mod\ n)\\ \rm b\,x\, &=&\rm\: a + n\,y,\ \ for\ \ some\ \ y \in \Bbb Z\end{eqnarray}$$

The prior equation has a solution $\rm\ (x,y)\in\Bbb Z^2\!\iff gcd(b,n) \mid a,\$ by Euclid/Bezout.  The solution is unique $\rm\,mod\ n\,$ iff $\rm\,gcd(b,n)= 1;\:$ if so the fraction $\rm\, x \equiv a/b\,$ is well-defined $\rm\,mod\ n.$

Generally normal fractional arithmetic makes sense $\rm\:mod\ n\:$ as long as one restricts to fractions with denominator coprime to $\rm\,n\:$ (else the fraction may not uniquely exist,  i.e. the equation $\rm\: ax\equiv b\,\ (mod\ n)\:$ might have no solutions, or more than one solution). The reason why such fraction arithmetic works here (and in analogous contexts) will become clearer when one learns about the universal properties of fraction rings (localizations).

-