Thread: Need to check my answer

Thanks for showing me how to work out some of the previous post.

I would like to check my answer for this problem

Find all incongruent solutions modulo 35 of the following system

7x + 5y = 13 (mod 35)
11x + 13y = 4 (mod35)


91x + 65y = 169 (mod 35)
-605x - 65y = -20 (mod 35)
=
514 = 149 (mod 35)

Euclidean Algorithm
514 = 14*35 + 24

35 = 1*24 + 11

24 = 2*11 + 2

11 = 5*2 + 1

Extended Euclidean Algorithm
1 = (1 * 11) + (-5 * 2)
= (-5 * 24) + (11 * 11)
= (11 * 35) + (-16 * 24)
= (-16 * 514) + (235 * 35)
= (235 * 35) + (-16 * 514)

35-4 = 31
Solution
x = 31 (mod 35)

77x +44y = 143(mod 35)
-77x -91y = -28 (mod 35)
=
36y = 115 (mod 35)

Euclidean Algorithm
35 = 0*36 + 35

36 = 1*35 + 1

35 = 35*1 + 0

Extended Euclidean Algorithm
1 = (1 * 36) + (-1 * 35)
= (-1 * 35) + (1 * 36)


115*36 = 4140
4140 / 35 = 118.28
118 * 35 = 4130
4140-4130 = 10

Solution
Y = 10 (mod 35)

I think im correct but not sure

Originally Posted by math_cali

7x + 5y = 13 (mod 35)
11x + 13y = 4 (mod35)

Because mathematicians are lazy I will not write "mod 35" rather I will write, and you will know it is modulo 35.

Now, we have.

Multiply the first equation by 13, second by -5,

Note I reduced everything to its smallest positive integer.
Add them, (note )

Put that into any equation, say the first.



Since,

And divides 20.
We will have 5 incongruent solutions.
You should be able to solve those.