3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Why was this answer downvoted? $\endgroup$ – James Feb 14 at 6:54
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.