The problem says that if $c$ divides $ab$ and $\gcd(b,c)=1$, then prove that $c$ divides $a$. $\gcd(a,c)?$
If $c$ divides $ab$, then $\gcd(ab,c)=d$ (say).
Given that, $\gcd(b,c)=1$, then there exist integers $x$, $y$ such that, $$bx+cy=1\\ \Rightarrow b=\frac{1-cy}{x}$$
$$\therefore abx+cy=d\\ \Rightarrow a.(\frac{1-cy}{x}).x+cy=d\\ \Rightarrow a+ac(-y)+cy=d\\ \Rightarrow a(1-cy)+cy=d\\ \Rightarrow ax'+cy=d,$$ where $x'=(1-cy)$.
Therefore, $\gcd(a,c)=d$. Hence, $c$ divides $a$. Does it imply $\gcd(a,c)=1$?
I think $\gcd(a,c)=1$ but cannot prove. I'm stuck here.
Any help is greatly appreciated.
Best Answer
Given $c \mid ab$ and $\gcd(b,c)=1$, prove $c \mid a$
$gcd(b,c)=1 \implies \exists m,n \in \mathbb Z, bm+cn=1 \implies abm+acn=a$.
Since $c \mid ab$, then $c \mid abm+acn$. Hence $c \mid a$