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

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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