Given $a$, $b$, $c$ (integers), and $p$ (prime),
Is there any general solution for $ax+by=c \mod p$?
I found that it has similar form to solving $ax=c \mod p$, but cannot find the connection between these two.
Answer
Assume that $p$ does not divide $a$ or $b$. Let $x_0$ be a solution of $ax\equiv 1\pmod{p}$, and let $y_0$ be a solution of $by_0\equiv 1 \pmod p$. Then all solutions $(x,y)$ of $ax+by \equiv c\pmod{p}$ are given by
$$x\equiv tx_0 \pmod{p}, \qquad y\equiv (c-t)y_0 \pmod{p},$$
where $t$ ranges over the integers from $0$ to $p-1$.
Note that $x\equiv tx_0\pmod{p}$ has infinitely many (closely related) solutions, as does $y\equiv (c-t)y_0\pmod{p}$. So we could write the general solution in the more cumbersome form $x=tx_0+mp$, $y=(c-t)y_0 +np$. Here $m$ and $n$ range over the integers, and $t$ ranges over the integers from $0$ to $p-1$.
No comments:
Post a Comment