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