Past exam of the mathematics course of the University of Cambridge / 2016 / ia / Paper 4 / 6E / Solution

Multiplying the desired representation by $b_1{b}_2$ turns it into the integer equationSince $b_1$ and $b_2$ are coprime integers, the necessary modular multiplicative inverses exist. Choose the unique representativesThen $a-a_1{b}_2-a_2{b}_1$ is divisible by both $b_1$ and $b_2$, hence by their product, because they are coprime. Definingtherefore gives an integer and proves existence. Any other representation, reduced modulo $b_1$ and $b_2$, must have the same $a_1$ and $a_2$, since their allowed ranges contain exactly one representative of each residue. The integer equation then forces the same $n$. This proves uniqueness.

For the prime-power fraction decomposition, put $d_i=p_i^{n_i}$ and $B_i=b/d_i$. The distinct prime-power factors $d_i$ are pairwise coprime, and $B_i$ has a modular multiplicative inverse modulo $d_i$. DefineEvery term $q_j{B}_j$ with $j\ne i$ is divisible by $d_i$, while $q_i{B}_i\equiv a(\mathrm{mod}{d}_i)$. Thus $a-{\sum }_i{q}_i{B}_i$ is divisible by all the pairwise coprime $d_i$ and therefore by $b$. With $n=(a-{\sum }_i{q}_i{B}_i)/b$, division by $b$ yields the required representation. Reducing any such representation modulo each $d_i$ proves uniqueness exactly as above. This is the residue-solving mechanism of the Chinese remainder theorem.

For $315=9\cdot 5\cdot 7$, the complementary factors are $35,63,45$. The required modular inverses givebecause $35\cdot 8\equiv 1(\mathrm{mod}9)$, $63\cdot 2\equiv 1(\mathrm{mod}5)$, and $45\cdot 5\equiv 1(\mathrm{mod}7)$. Their numerator sum is $280+126+225=631=1+2\cdot 315$. Thus the unique decomposition is