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

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.

• Since $c$ divides $ab$, you have $\gcd(ab, c) = c$ – rsadhvika Mar 16 '18 at 13:18
• If $c$ divides $ab$ but has no common factors with $b$, then clearly $c$ divides $a$, and as a result, $\gcd(a,c)=c$. Your proof seems correct yet I don't quite understand why you go from $c\mid a$ to $\gcd(a,c)=1$. How is $\gcd$ defined? Do you see why $c\mid a$ implies $\gcd(a,c)=c$? – vrugtehagel Mar 16 '18 at 13:20
• actually i am trying to determine (if possible) $g.c.d(a,c)$ from the equation $bx+cy=1$ by some algebra. – vbm Mar 16 '18 at 13:26
• $c|a \implies c|a.\gcd(a,c)$ – JonMark Perry Mar 16 '18 at 13:35
• @vrugtehagel, I have made a delay but now I've got it. yes at first I was wrong. This is correct - $g.c.d(a,c)=c$. – vbm Mar 16 '18 at 13:42

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$

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.

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

• Mindblowing and very much helpful explanation. Thank you so much. – vbm Mar 16 '18 at 13:53

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

• Two numbers being relatively prime is not equivalent to one not dividing the other. For example $4$ does not divide $6$, but four and six are not relatively prime. – G Tony Jacobs Mar 16 '18 at 14:35
• good point. thanks. – miniparser Mar 16 '18 at 14:40
• edited/corrected. – miniparser Mar 16 '18 at 19:38
• There’s another issue in there. You have $ab=cd$, and then later, $a=cd$. Does that mean $b$ is necessarily equal to $1$? – G Tony Jacobs Mar 16 '18 at 19:41
• corrected. thanks. – miniparser Mar 16 '18 at 20:13