Slove the system of congruences
3x = 2 mod 4
4x = 1 mod 5
6x = 3 mod 9
is it no solution since 6 and 9 do not have an inverse since the gcd of 6 and 9 is not one thus u cant write it in the form x=a mod p
If $\displaystyle ac \equiv bc \ (\text{mod } m)$ and $\displaystyle (c,m) = d$, then $\displaystyle a \equiv b \left(\text{mod } \frac{m}{d}\right)$
Keeping in this in mind, I'm going to simplify the congruences first:
$\displaystyle \begin{array}{rcll} 3x & \equiv & 2 & (\text{mod } 4) \\ 3x & \equiv & 6 & (\text{mod } 4) \\ x & \equiv & 2 & (\text{mod } 4) \end{array}$........$\displaystyle \begin{array}{rcll} 4x & \equiv & 1 & (\text{mod } 5) \\ 4x & \equiv & -4 & (\text{mod } 5) \\ x & \equiv & -1 & (\text{mod } 5) \\ x & \equiv & 4 & (\text{mod } 5) \end{array}$........$\displaystyle \begin{array}{rcll} 6x & \equiv & 3 & (\text{mod } 9) \\ 6x & \equiv & 12 & (\text{mod }9) \\ x & \equiv & 2 & (\text{mod } 3) \end{array}$
So we're left with the system:
$\displaystyle \begin{array}{rcll} x & \equiv & 2 & (\text{mod } 4) \\ x & \equiv & 4 & (\text{mod } 5) \\ x & \equiv & 2 & (\text{mod } 3) \end{array}$
And by the Chinese Remainder theorem, since $\displaystyle (4, 5, 3) = 1$, there is a unique solution modulo $\displaystyle 4\cdot 5 \cdot 3 = 60$. Should be pretty simply to solve this one.
i get the right answer after applying the CRT to the reduced congruences, but i still dont know how u reduced the congruences or simplified them. Could you maybe explain it a little bit. Could u find the inverse modulo of each congruence and and reduce it to the form x=a mod m
Hello,
Divide the formula of o_O into 2 formulae:
1) If $\displaystyle ac\equiv bc\pmod m$ and $\displaystyle (c, m)=1$ then $\displaystyle a\equiv b\pmod m$.
2) If $\displaystyle ac\equiv bc\pmod {mc}$ then $\displaystyle a\equiv b\pmod m$.
1) corresponds to the case where you can find an inverse.
2) is a technique to decrease the modulus.
You add the modulus as many times as you want so that the coefficient of x and the right-hand-side have a common divisor.
Bye.
What I did was play around with the congruences a little. Remember, they sort of act like equality signs as well. Let's take the middle one I did:
$\displaystyle
\begin{array}{rcll} 4x & \equiv & 1 & (\text{mod } 5) \\ 4x & \equiv & -4 & (\text{mod } 5) \qquad \text{1. Subtracted 5} \\ x & \equiv & -1 & (\text{mod } 5) \qquad \text{2. Divided both sides by 4} \\ x & \equiv & 4 & (\text{mod } 5) \qquad \text{3. Added 5 to get a least residue} \end{array}
$
Basically, I wanted to get rid of the coefficient in front of the x and what I wanted is to ultimately divide it out:
1. If something is congruent to 4x mod 5, then adding or subtracting multiple of 5's will still be congruent to 4x. Remember: $\displaystyle a \equiv b \ (\text{mod m}) \ \iff \ a = b + km$
2. This refers to the very first statement I had in my first post
3. Again, adding and subtracting multiples of the modulus will not change the congruence as we did in step 1. The main purpose in doing so was to get a least residue (i.e. the "remainder")
Edit: Oh beaten!