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=cmodp?



I found that it has similar form to solving ax=cmodp, but cannot find the connection between these two.


Answer



Assume that p does not divide a or b. Let x0 be a solution of ax1(modp), and let y0 be a solution of by01(modp). Then all solutions (x,y) of ax+byc(modp) are given by
xtx0(modp),y(ct)y0(modp),

where t ranges over the integers from 0 to p1.



Note that xtx0(modp) has infinitely many (closely related) solutions, as does y(ct)y0(modp). So we could write the general solution in the more cumbersome form x=tx0+mp, y=(ct)y0+np. Here m and n range over the integers, and t ranges over the integers from 0 to p1.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...