Exercise 848Number theory › CongruencesL1Added 3 Nov 2026

Halving in modular arithmetic

#halving#modular arithmetic#odd modulus

Statement

In $\mathbb{Z}/n\mathbb{Z}$ with $n$ odd, show that the congruence $2x\equiv a\pmod n$ has a unique solution for every $a$ .

Hint

$2$ is invertible mod $n$ iff $n$ is odd.

Show solutionHide solution

Inverse of 2. $n$ odd means $\gcd(2,n)=1$ , so $2$ is invertible mod $n$ . The inverse is $(n+1)/2$ (since $2\cdot(n+1)/2=n+1\equiv1$ ).

Solution. $x\equiv a\cdot(n+1)/2\pmod n$ .

Conclusion. Halving is well defined mod $n$ when $n$ is odd; it is not when $n$ is even.