2
$\begingroup$

if $a|bc$ and $gcd(a,b) = 1$, then $a|c$

We know that $b|bc$

also $a|bc$

and $(a,b)= 1 \rightarrow \big(ab=lcm(a,b\big)\big| bc$

so $a | c$.

Is this proof correct?

Edit: I think assuming $lcm(a,b)=ab$ is too much so here is another elementary proof:

$(a,b)=1\rightarrow \exists p,q \in Z \ni pa +qb = 1 \rightarrow pac + qbc = c $

now $a|ac$ and $a|bc$ so $a|c$

$\endgroup$
  • $\begingroup$ That looks fine to me. $\endgroup$ – Don Thousand Nov 19 '19 at 7:41
  • $\begingroup$ How do you prove that the lcm of $a$ and $b$ is $ab$? $\endgroup$ – Lord Shark the Unknown Nov 19 '19 at 7:42
  • 1
    $\begingroup$ @Martund He/she didn't mention that, but is she or he had, I'd ask him/her how that was proved. $\endgroup$ – Lord Shark the Unknown Nov 19 '19 at 7:46
  • 1
    $\begingroup$ Your new argument is very much a standard proof. $\endgroup$ – Lord Shark the Unknown Nov 19 '19 at 7:47
  • 1
    $\begingroup$ I worry about these proofs. Assuming that if $\gcd(a,b)=1$ then $lcm(a,b)=ab$ and that if $a|m$ and $b|m$ then $lcm(a,b)|m$ seem to me to not be any more fundamental then the result you are proving. I'd worry about checking the proofs of those assumptions and verify you didn't use something equiv to what your are proving. (One should always be prepared to prove use statements anyway.) Which is not to say your proof isn't valid. It might very well be. $\endgroup$ – fleablood Nov 19 '19 at 7:58
3
$\begingroup$

This proof is correct, another one could be using bezout's identity. $$gcd(a,b)=1$$ $$\Longrightarrow \exists x,y\in \mathbb Z : ax+by=1$$ $$\Longrightarrow acx+bcy=c$$ LHS is divisible by $a$, so is RHS.

$\endgroup$

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