Suppose $\bar{a}\in (\mathbb{Z}/n\mathbb{Z})$*. Prove that $\gcd(\bar{ab},n)=\gcd(\bar{b},n)\forall_{b\in (\mathbb{Z}/n\mathbb{Z})}$ Suppose $\bar{a}\in (\mathbb{Z}/n\mathbb{Z})$*. We want to prove that $\gcd(\bar{ab},n)=\gcd(\bar{b},n)$, so we show that for a divisor $d\in\mathbb{Z}: d|\bar{ab} \land d|n \iff d|\bar{b} \land d|n$. 
For clarity: $\bar{a}\in (\mathbb{Z}/n\mathbb{Z})$* denotes that $\bar{a}$ is in the multiplicative group such that it is coprime to $n$. 

(Unfinished) Proof:


*

*Suppose $d|\bar{b}$ and $d|n$. Then we can write $\frac{\bar{b}}{d}=q$ for some $q\in\mathbb{Z}.$ 
Since $\bar{a}\in\mathbb{Z}: \frac{\bar{ab}}{d}=aq$ with $aq\in\mathbb{Z}$ so that $d|\bar{ab}$, and $d|n$ by assumption.
$$$$


*

*Suppose $d|\bar{ab}$ and $d|n$. We know that $\gcd(\bar{a},n)=1$ as $\bar{a}\in (\mathbb{Z}/n\mathbb{Z})$*. 
By the Euclidian algorithm, we can write this as $x\bar{a}+yn=1$, so $\bar{ab}x=\bar{b}-yn\bar{b}$. 
Since $d|\bar{ab}$ and $x\in\mathbb{Z}$, we know that $d|\bar{ab}x$ by the same argument in part 1. 
As $d|n$ we can write it as $\frac{n}{d}=p$ for some $p\in\mathbb{Z}$, so $n=dp$. 
Then $xa+dpy=1$ gives us that $abx+dpby=b$ so that $\frac{b-abx}{d}=pby$ with $p,b,y\in\mathbb{Z}$. As $d|abx$, $d|b$ because else $pby$ wouldn't be an integer.

I didn't get a lot farther than this, and I'm not even sure if I'm in the right direction with the second part of this proof. A hint in the right direction would be much appreciated!
 A: If $a$ is a unit, mod $n$, then $\gcd(a,n)=1$.

Let $d=\gcd(b,n)$, and let $e=\gcd(ab,n)$.

We want to show $d=e$.

Then $d{\,\mid\,}b$ implies $d{\,\mid\,}ab$.

Thus, $d{\,\mid\,}ab$, and $d{\,\mid\,n}$, so $d$ is a common factor of $ab$ and $n$, hence $d{\,\mid\,}e$.

Since $e{\,\mid\,}n$, any divisor of $e$ is also a divisor of $n$, hence any common factor of $a$ and $e$ would also be a common factor of $a$ and $n$. But we have $\gcd(a,n)=1$, hence $\gcd(a,e)=1$.

Since $e$ divides $ab$, and $\gcd(a,e)=1$, it follows that $e{\,\mid\,}b$.

The above is a standard result, but here's the usual justification . . .

Suppose $e{\,\mid\,}ab.\;$Since $\gcd(a,e)=1$, there are integers $x,y$ such that 
$$ax+ey=1$$
Multiplying both sides by $b$ yields
$$abx + eby = b$$
hence, since $e$ divides both terms of the $\text{LHS}$, we get $e{\,\mid\,b}$. 

The above result is highly reusable. In words, it can be stated as follows:


*

*If an integer divides a product of two integers, and is relatively prime to one of the integers, then it must divide the other one.



Thus, we have $e{\,\mid\,}b$, and $e{\,\mid\,}n$, so $e$ is a common factor of $b$ and $n$, hence $e{\,\mid\,}d$.

Therefore $d=e$.
A: Since $a$ and $n$ have no common prime factors the only common factors in $ab$ and $n$ are those which are common in $b$ and $n$.
A: Here is a different take.
If $a$ is a unit mod $n$, then the ideal $(ab)$ is the same as the ideal $(b)$.
The size of the ideal $(b)$ is given by the additive order of $b$ mod $n$, which is $n/\gcd(b,n)$.
Therefore, $(ab)=(b)$ implies $n/\gcd(ab,n)=n/\gcd(b,n)$ and so $\gcd(ab,n)=\gcd(b,n)$.
