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 and , then
Keeping in this in mind, I'm going to simplify the congruences first:
So we're left with the system:
And by the Chinese Remainder theorem, since , there is a unique solution modulo . Should be pretty simply to solve this one.
Divide the formula of o_O into 2 formulae:
1) If and then .
2) If then .
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.
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:
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:
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!