Assume $d\mid n$. Show $g\colon (\mathbb Z/n\mathbb Z)^*\to(\mathbb Z/d\mathbb Z)^*$ given by $g(a\mod n)= a\mod d$ is surjective.

Question

Let $d,n\in\mathbb Z_{>0}$ with $d\mid n$. Show $g\colon (\mathbb Z/n\mathbb Z)^*\to(\mathbb Z/d\mathbb Z)^*$ given by $g(a\mod n)= a\mod d$ is surjective.

In a previous exercise, I’ve shown the following:

Let $d,n\in\mathbb Z_{>0}$ with $d\mid n$. Let $a\in\mathbb Z$ such that $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$.

Consider $\overline a\in(\mathbb Z/d\mathbb Z)^*$. This means that $\gcd(a,d)=1$. We want to show that $\gcd(a,n)=1$. We know that $\gcd(a+td,n)=1$. Therefore there exists $u,v\in\mathbb Z:ua+utd+vn=1$. I need to show there exists $u',v'\in\mathbb Z:u'a+v'n=1$. How can I continue from here on?

Answer 1

Given that no answer is posted, I will provide it myself:

Consider $a\mod d\in(\mathbb Z/d\mathbb Z)^*$ for some $a\in\mathbb Z$. This means that $\gcd(a,d)=1$. From the previous exercise mentioned in the question, we know that $\gcd(a+td,n)=1$. Assume $\gcd(a,n)\neq 1$. This means that there exists a prime number $p$ such that $p\mid a$ and $p\mid n$. However, this means that $p\mid a+td$ and $p\mid n$. This is a contradiction. We conclude $\gcd(a,n)=1$. Therefore $a\mod n\in(\mathbb Z/n\mathbb Z)^*$, so $f$ reaches $a\mod d$.