(11C) Think of a Number

[Albert Chan]

Amazingly, solution for { x≡a (mod 5), x≡b (mod 7), x≡c (mod 9) }, there is *NO* inverse to calculate

Let x' = a + 5m, a solution to 2 congruences.

mod 7: x' = a + 5m ≡ a - 2m ≡ b → m = (1/2)(a-b)

Note: fraction 1/2 really meant inverse of 2 (mod 7), not yet calculated
Note: since x' is a solution, we use "m = ...", not "m ≡ ..."

Let x'' = x' + 35n, a solution to 3 congruences.

mod 9: x'' = x' + 35n ≡ x' - n ≡ c → n = x' - c

x'' = x' + 35(x' - c) = 36(a + (5/2)(a-b)) - 35c = 126a - 90b - 35c

x'' (mod 315) ≡ 126a + 225b + 280c