Strayer Elementary Number Theory 2. 3. 40.

Yeah so this one is a nightmare. I found no proofs to use for help, so I will not link to any. Only hints that there is a solution using prime factorization.

Good news is, if this proof is too much for you, I have seen a possibly easier induction proof floating around out there. I didn't learn the details of it, as I saw it well after I was already committed to this version of the proof.

Some might find it a challenge to accept the part of the proof saying it is OK to rewrite the moduli as powers of a single prime; i.e., that it is indeed equivalent to solving for any other moduli. I realize this, and I'm sorry if I could not make it more clear in just a line or two.

The main reason making this ok is Lemma 1. That is, solving the congruence x=b(mod m) is equivalent to solving the congruences x=b(mod p1^(k1)), x=b(mod p2^(k2)), ..., x=b(mod pn^(kn)), where the p^(k)'s represent the prime factorization of m. So, we can translate Problem 40 as it is worded in the book to a problem solely about solving congruences only for prime power moduli, just by this important Lemma. So at this point, it is not just easier in terms of notation, but also easier in the amount of steps and wording in the proof to just use moduli that are powers of a single prime. You can do it the other way, but you will quickly have so many indices and variables and p's and q's you will probably lose yourself. There is nothing to gain from using more complicated moduli, just A LOT of extra work (and variables/ symbols).

A secondary reason is the 'meat' of the solution where we investigate the consequences of assuming (mi,mj)|bi-bj for all i!=j. So, what if we were using moduli more complicated than powers of a single prime, and we also assume said moduli are not coprime? Then we break them down into their respective prime factorizations and study those congruences. As for the prime power (or powers) that are held in common, we learn (as per the proof) that we can simply ignore accounting for these congruences (when their prime powers are less than others) in determining the solution. We just forget them for the time being, and are eventually left with a system of congruences of coprime moduli that are just powers of a single prime.

Hope this helps. God-speed.