A problem on divisibility: If $c$ divides $ab$ and $\gcd(b,c)=1$, then prove that $c$ divides $a$.

Question

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.

Answer 1

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$

Answer 2

If $c|ab$, then $ab=nc$, where $n$ is some integer. If $\gcd{(b,c)}=1$, we have $cx+by=1$. Multiplying through by $a$, we have, $acx+aby=a$. We can substitue $ab=nc$ to get $acx+cny=a$, such that $a=c(ax+ny)=a$, or in other words, that $c|a$ as desired. The second part of your question was already addressed in the comments.

Answer 3

Proofs involving strictly multiplication, division and $\gcd$ of the integers are often very naturally thought of by using the fundamental theorem of arithmetic, leading to an alternate representation of the numbers: ordered tuples of their prime exponents.

For example, $21 = 3 \times 7$. If we look at the infinite ordered list of primes, we can also see that $21 = 2^0 \times 3^1 \times 5^0 \times 7^1 \times \dots$. So it's ordered tuple representation of its prime exponents would be $(0, 1, 0, 1, 0, \dots)$.

Now the operations are very simple:

1. $a\times b$: simply add the exponents pairwise. We have $3 \times 5 = (0, 1, 0, \dots) + (0, 0, 1,\dots) = (0, 1, 1, \dots).$

2. $a \div b$: simply subtract the exponents pairwise. If for some pair you'd get a negative number, it means that $a$ is not divisible by $b$.

3. $\gcd(a, b)$: take the minimum of the exponents pairwise. For example for $12$ and $18$ we'd get:

   $\min((2, 1, 0, \dots), (1, 2, 0, \dots)) = (1, 1, 0, \dots) = 6$

In this context the problem is really easy to prove:

The problem says that if $c$ divides $ab$ and $\gcd(b,c)=1$, then prove that $c$ divides $a$. $gcd(a,c)=?$

Let $a_i, b_i, c_i$ respectively be the $i$th prime exponent of $a, b, c$. Then $c \mid ab$ tells us $c_i \leq a_i + b_i$ and $\gcd(b, c) = 1$ tells us $\min(b_i, c_i) = 0$. This allows us to substitute $c_i$ for $b_i + c_i$ in our first equation, giving $b_i + c_i \leq a_i + b_i \Rightarrow c_i \leq a_i$. That tells us $c \mid a$. It also tells us $\min(c_i, a_i) = c_i$, thus $\gcd(a, c) = c$.

Answer 4

$c|ab$

$gcd(b,c)=1\Longrightarrow c\nmid b\space(c|b\Longleftrightarrow gcd(b,c)=c)$

$c|ab\wedge c\nmid b\Longrightarrow c|a$