Two clocks, one answer

phi(k) counts units mod k; the sieve subtracts phi[i]/p at each prime in one linear pass. CRT reuses the inverse: solving x = a (mod n), x = b (mod m) sets x = a + n*t and solves for t modulo m. Composite moduli need the general egcd inverse — same idea, one more step.