Question

Solve these linear equations over Z₅

2x+3y =4

3x+y=2

The answer is (1,4) as unique solution, please kindly explain the reasons and show your work, much appreciated!

Answer 1

Given linear equations are, 2x+3y=4......................(i)

3x+y=2........................(ii)

We know that, in Z₅ system we represent numbers by the rule a*b = remainder part of a*b/5.

Therefore the given equations can be written as, 2x+3y4(mod 5)......................(iii)

3x+y2(mod 5)........................(iv)

Now, multipling 2 on both sides of (iv), we get, 6x+2y4(mod 5)

From 2x+3y4(mod 5) and 6x+2y4(mod 5) we can say that 6x+2y2x+3y(mod 5) , i.e., 4xy(mod 5) ,i.e., y4x(mod 5), i.e., y=4x+5m, where m is an integer.

Putting this in (iii) and (iv) we get, 2x+3y=4+5n and 3x+y=2+5p

i.e., 2x+3(4x+5m)=4+5n and 3x+(4x+5m)=2+5p

i.e., 14x=4+5(n-3m) and 7x=2+5(p-m) [where n,p are integres]

i.e., 14x=4(mod 5) and 7x=2(mod 5)

Now, gcd(14,5)=1 and gcd(7,5)=1.

Hence the congruences has an unique solution.

Since, gcd(14,5)=1, there exist integers a,b such that 14a+5b=1.

Here a=-1, b=3. Therefore 14(-1)+5.3=1 and this implies 14(-1)1(mod 5), i.e., 14(-4)4(mod 5).

All solutions are , i.e.,

All solutions are congruent to 1(mod 5) and therefore the given congruence has a unique solution.

Now, y4x(mod 5), i.e., y4.1(mod 5), i.e., y4(mod 5).

Also, by similar reasons, all the solutions are congruent to 4(mod 5) and therefore the given congruence has an unique solution.

Therefore, (1,4) is the unique solution of the given system of linear equations.