Because if you can divide it to couple of moduli which are pairwise coprime, then you can use CRT to recover the original congruence
Hi all,
I have a congruence 224x +225y = 226 (mod 228)
I've been told it can be reduced to:
0x + 1y = 2 (mod 4)
2x + 0y = 1 (mod 3)
15x + 16y = 17 (mod 19)
I don't think I fully understand how to divide (reduce?) a congruence because I can't figure out how to get from the first congruence to the other three.
I recognize that 3, 4, and 19 are the prime factors of 228, and also that if you use these values as modulo on the original values (224, 225, 226) you get the new values in the last three congruences. i.e. 224 mod 3 = 2, which fits into 2x + 0y = 1 mod 3
I (think I) understand how to divide a congruence by a number if the divisor and the modulo are relatively prime. If ax + by = c (mod n) and gcd(d,n) is 1 then you can divide a, b, and c by d for the new congruence.
Example: 6x + 10y = -14 (mod 3) divided by 2 is 3x + 5y = -7 (mod 3)
If d and n are not relatively prime, then it is my understanding that you can still divide, but that the resulting modulo will change to equal (n / gcd(n,d)) and the c value equals (c/gcd(n,d)) and not c/d.
Example: 28x - 14y = 14 (mod 35) divided by 14 is 2x - 1y = 2 (mod 5)
I tried this second method to divide 224x + 225y = 226 (mod 228) by 57 (in order to get a new modulo of 4), but 224 and 225 are not evenly divisible by 57.
Is there a special rule on dividing a congruence by a prime factor of its modulo? Am I doing the wrong thing when trying to divide a congruence by a number that is not relatively prime to the modulus?
Thank you for your time,
m
I understand how to use the Chinese Remainder Theorem on the last three congruences to get the first congruence, but I don't know how to start with the first congruence and come up with the last three congruences. I understand how to get the prime factorization of the modulo from the first congruence, but how do I divide the original congruence to get the new equations?
What is the equation that turns: 224x + 225y = 226 (mod 228)
into: 0x + 1y = 2 (mod 4)
Thanks for the thought,
m