Wednesday, 26 April 2017

modular arithmetic - how to solve ax+by=cmodp?



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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...