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!

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)$.
