Linear congruences: solve x ? 1 (mod 2), x ? 1 (mod 3)

[sigma]

How would you solve a liner congruence system like this?
x ? 1 (mod 2), x ? 1 (mod 3)

 

[daon]

Re: Linear congruences

All k such that lcm(2,3) | (k-1), i.e. { 6n+1 | n is an integer}.

 

[sigma]

Well the answer for this question is x ? 1(mod6) but I keep getting x ? 3(mod6)???

 

[daon]

Look at my reply more closely.

6|(k-1) => k = 1 (mod 6).

....

We have:

x = 2a+1 => 3x = 6a+3
x = 3b+1 => -2x = -6b-2

Add them down: x = 6(a-b)+1

In general, x=1 (mod n), x = 1 (mod m) => x = 1 (mod lcm(m,n))

 

[sigma]

Ok I have it figured out. Just a new question. How would I solve this system of congruences involving 2 variables?

3x + 2y ? 1 (mod11), 2x +3y ? 5 (mod 11)

I think you have to do something with the Chinese remainder theorem but i'm not sure where to go with it

 

[daon]

Do you remember back in basic algebra when you solved these in the real numbers?

Z_11 is a field too.

3x+2y=1
2x+3y=5

Solve the first one for x:

3x=1+9y
x = 4+3y

Now sub into the second:

2(4+3y) + 3y = 5
8+9y=5
9y = 8
y = 7

Now go get your x:

3x+2(7)=1
3x = 9
x = 3

So your answer is (3,7)

You may also do this by the addition method.