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