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 ax≡1(modp), and let y0 be a solution of by0≡1(modp). Then all solutions (x,y) of ax+by≡c(modp) are given by
x≡tx0(modp),y≡(c−t)y0(modp),
where t ranges over the integers from 0 to p−1.
Note that x≡tx0(modp) has infinitely many (closely related) solutions, as does y≡(c−t)y0(modp). So we could write the general solution in the more cumbersome form x=tx0+mp, y=(c−t)y0+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