4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Since $c$ divides $ab$, you have $\gcd(ab, c) = c$ $\endgroup$ – rsadhvika Mar 16 '18 at 13:18
  • 1
    $\begingroup$ 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$? $\endgroup$ – vrugtehagel Mar 16 '18 at 13:20
  • $\begingroup$ actually i am trying to determine (if possible) $g.c.d(a,c)$ from the equation $bx+cy=1$ by some algebra. $\endgroup$ – vbm Mar 16 '18 at 13:26
  • $\begingroup$ $c|a \implies c|a.\gcd(a,c)$ $\endgroup$ – JonMark Perry Mar 16 '18 at 13:35
  • $\begingroup$ @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$. $\endgroup$ – vbm Mar 16 '18 at 13:42
7
$\begingroup$

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$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Mar 16 '18 at 14:35
  • $\begingroup$ good point. thanks. $\endgroup$ – miniparser Mar 16 '18 at 14:40
  • $\begingroup$ edited/corrected. $\endgroup$ – miniparser Mar 16 '18 at 19:38
  • $\begingroup$ There’s another issue in there. You have $ab=cd$, and then later, $a=cd$. Does that mean $b$ is necessarily equal to $1$? $\endgroup$ – G Tony Jacobs Mar 16 '18 at 19:41
  • $\begingroup$ corrected. thanks. $\endgroup$ – miniparser Mar 16 '18 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.