Past exam of the mathematics course of the University of Cambridge / 2022 / ia / Paper 4 / 5E / Solution

The Bezout identity states that for integers $a,b$, not both zero, there are integers $r,s$ such thatIf the prime number $p$ divides $ab$ but does not divide $a$, then $\gcd (p,a)=1$. Thus $rp+sa=1$ for some integers $r,s$, and multiplication by $b$ givesBoth terms on the right are divisible by $p$, so $p\mid b$. Hence

If $\gcd (m,n)=1$, choose $r,s$ with $rm+sn=1$. Thensatisfies $x\equiv a(\mathrm{mod}m)$ and $x\equiv b(\mathrm{mod}n)$. If $x,x^{\prime }$ are two simultaneous solutions, both $m$ and $n$ divide $x-x^{\prime }$. Coprimality implies $mn\mid x-x^{\prime }$, so the solution is unique modulo $mn$. This proves the two-modulus Chinese remainder theorem.

Let $p$ be odd and supposeThen $p^d\mid (x-1)(x+1)$. Since $\gcd (x-1,x+1)$ divides $2$, the odd prime $p$ cannot divide both factors. The full power $p^d$ must therefore divide one of them, givingThese are distinct, so there are exactly two solutions.

For an odd integerthe Chinese remainder theorem identifies a solution modulo $n$ with independent solutions modulo the $k$ prime powers. Each component has two choices, hence

For $n=2^d$, there is one solution when $d=1$ and two when $d=2$. If $d\ge 3$, a solution $x$ is odd, and of the consecutive even integers $x-1,x+1$, exactly one is divisible by $4$. The 2-adic valuations therefore have minimum one; for their sum to be at least $d$, the other must be at least $d-1$. Thus $x\equiv \pm 1(\mathrm{mod}{2}^{d-1})$, giving the four distinct classesConsequently the answer is

Solved by gpt-5.6-sol high.