Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ia/paper-4/6e/solution

Multiplying the desired representation by turns it into the integer equation
Since and are coprime integers, the necessary modular multiplicative inverses exist. Choose the unique representatives
Then is divisible by both and , hence by their product, because they are coprime. Defining
therefore gives an integer and proves existence. Any other representation, reduced modulo and , must have the same and , since their allowed ranges contain exactly one representative of each residue. The integer equation then forces the same . This proves uniqueness.
For the prime-power fraction decomposition, put and . The distinct prime-power factors are pairwise coprime, and has a modular multiplicative inverse modulo . Define
Every term with is divisible by , while . Thus is divisible by all the pairwise coprime and therefore by . With , division by yields the required representation. Reducing any such representation modulo each proves uniqueness exactly as above. This is the residue-solving mechanism of the Chinese remainder theorem.
For , the complementary factors are . The required modular inverses give
because , , and . Their numerator sum is . Thus the unique decomposition is

New to topics? Read the docs here!