PDA

View Full Version : diophantine equations


ascheras
Dec20-04, 05:36 PM
ok, so i've never done a problem like this one before:

find all solutions:

24x + 11y == 4 (mod 35)
5x + 7y == -13 (mod 35).

This reduces to:
24x + 11y == 4 (mod 5)
5x + 7y == -13 (mod 5).

and
24x + 11y == 4 (mod 7)
5x + 7y == -13 (mod 7).

Solving the two, i get (2,1) and (3,4) respectively.
Do I now apply the CRT to get all the solutions?

Popey
Dec21-04, 03:45 PM
I'm not quite sure about it, but I think that you should now solve these systems

x == 2 (mod5)
x == 3 (mod7)

which gives x == 17 (mod35)

and

y == 1 (mod5)
y == 4 (mod7)

which gives y == 11 (mod35)

Gokul43201
Dec21-04, 04:03 PM
Yes, from the above, using CRT gives you :

x \equiv 17~(mod~35)~~y \equiv 11~(mod~35)