A number gives remainders 4, 8, and 12 when successively divided by 5, 9, and 13 (short division for 585 = 5 × 9 × 13). What remainder would occur if divided directly by 585?

Given data

• 585 = 5 × 9 × 13 with pairwise coprime factors.
• Short-division remainders: 4 (mod 5), 8 (mod 9), 12 (mod 13).

Concept / Approach

• Chinese Remainder Theorem (CRT): find r such that

r ≡ 4 (mod 5), r ≡ 8 (mod 9), r ≡ 12 (mod 13)

Step-by-step solutionStart with r ≡ 8 (mod 9) ⇒ r = 8 + 9aImpose r ≡ 12 (mod 13): 8 + 9a ≡ 12 (mod 13)9a ≡ 4 (mod 13)Inverse of 9 mod 13 is 3 (since 9 × 3 = 27 ≡ 1)a ≡ 3 × 4 = 12 (mod 13) ⇒ a = 12 + 13tThus r = 8 + 9(12 + 13t) = 116 + 117tNow impose r ≡ 4 (mod 5): 116 + 117t ≡ 4 (mod 5)116 ≡ 1, 117 ≡ 2 (mod 5) ⇒ 1 + 2t ≡ 42t ≡ 3 (mod 5) ⇒ multiply by inverse of 2 (which is 3): t ≡ 9 ≡ 4 (mod 5)Take t = 4 ⇒ r = 116 + 117 × 4 = 584

Verification584 mod 5 = 4, 584 mod 9 = 8, 584 mod 13 = 12.

Common pitfalls

• Confusing successive short-division remainders with non-coprime moduli or forgetting CRT conditions.

Final Answer584