2

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.

user4478
  • 329
  • The connection is probably the Chinese Remainder Theorem. – Peter Taylor Jul 03 '13 at 17:09
  • In general, once you've solved $ax+by=c$ with one solution $(x_0,y_0)$ all solutions will be of the form $(x,y)=(x_0+bk,y_0-ak)$. This assumes $a,b$ are not divisible by $p$. So if you've solved $ax=c\pmod p$, then you've got a soluton with $y_0=0$. – Thomas Andrews Jul 03 '13 at 17:13
  • The msolve command of Maple produces it. – user64494 Jul 03 '13 at 17:15
  • from http://mathworld.wolfram.com/DiophantineEquation.html I know ax+by=c has a general solution, but can someone tell me how can to write down the general solution form of ax+by=c mod p? – user4478 Jul 03 '13 at 17:21
  • My guess: if I get a solution (x0,y0), all of the other solutions are (x0+kp, y0+kp)? – user4478 Jul 03 '13 at 17:23

1 Answers1

1

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$.

André Nicolas
  • 507,029
  • My guess: if I get a solution (x0,y0), then all of the other solutions are (x0+kp, y0+kp). Is my guessed solution form equivalent to your solution form? – user4478 Jul 03 '13 at 17:27
  • @user4478: Your guess is off in a couple of ways. First the "$k$" for the first coordinate and the one for the second coordinate can be different integers. Secondly, there is a third free parameter that I have called $t$ in my solution, – André Nicolas Jul 03 '13 at 17:33