# 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$ – AgentS 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)$ – JMP 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