Showing that a homomorphism between groups of units is surjective. [duplicate]

Solution 1:

Let $u$ be a unit modulo $d$ and confuse it with the integer $0 < u < d$. Clearly if $(u, n) = 1$ then $u$ is in the image of the map. So suppose $(u,n) \neq 1$. Then it suffices to find $x \in \mathbb{Z}$ such that $(u + xd, n) = 1$. Indeed, if this can be done, then the map sends $u+xd \rightarrow u$ with $u+xd$ a unit in $\mathbb{Z}/n\mathbb{Z}$.

Claim: Taking $x$ to be a product of all primes dividing $n$ which do not divide $u$ suffices.

Proof: Let $p$ be a prime dividing $n$. If $p \mid u$, then $p$ does not divide $x$ and $p$ does not divide $d$ by definition. Hence $p \nmid u+dx$. Now suppose $p \nmid u$. Then $p \mid x$ by definition, so $p \nmid u + dx$.

Therefore every prime which divides $n$ does not divide $u+dx$, giving $(u+dx,n) = 1$.