Chinese Remainder Theorem

[morrowcosom]

Homework Statement

Find a satisfying a 1 (mod 2), a 2 (mod 3), with 0 < a < 6

Begin with the Mod 2 calculation

Homework Equations

The Attempt at a Solution

I found that U1=3 and U2=4, but then it says "Now take the appropriate linear combination of {U1, U2} to find a which matches the required congruences: a 1 (mod 2), a 2 (mod 3)".

How do take the appropriate linear combination of 3 and 4 to find a? (I know the answer is 5 just by looking at it, but have no idea how to get there via the method mentioned above)

Thanks for the help

 

[nate808]

!

your goal is to find a solution that satisfies the given congruences. In this case, the given congruences are a 1 (mod 2) and a 2 (mod 3). This means that a is congruent to 1 (mod 2) and a is congruent to 2 (mod 3).

To find the solution, we can use the Chinese Remainder Theorem, which states that if we have a system of congruences with relatively prime moduli, we can find a unique solution modulo the product of the moduli. In this case, the moduli are 2 and 3, which are relatively prime. Therefore, we can use the Chinese Remainder Theorem to find a unique solution modulo 2*3=6.

To apply the Chinese Remainder Theorem, we can use the formula a ≡ a1M1y1 + a2M2y2 (mod M), where a1, a2 are the remainders when a is divided by M1 and M2 respectively, and y1, y2 are the solutions to the corresponding congruences.

In this case, a is congruent to 1 (mod 2) and 2 (mod 3). This means that a1 = 1, a2 = 2, M1 = 2, and M2 = 3. To find y1 and y2, we can use the Extended Euclidean Algorithm.

y1 is the inverse of 2 modulo 2, which is 1.

y2 is the inverse of 3 modulo 3, which is 1.

Therefore, the solution is a ≡ 1*2*1 + 2*3*1 (mod 6) ≡ 2 + 6 ≡ 8 ≡ 2 (mod 6).

Since we want a to be between 0 and 6, we can reduce the solution further to a ≡ 2 (mod 6).

Thus, the satisfying solution is a = 2.