0
$\begingroup$

I'm trying to prove a theorem out of my text:

Theorem: Let $a$ and $b$ be natural numbers. Then $GCD(a,b)=1$ if and only if for all natural numbers $c$, if $a|bc$ then $a|c$.

I did come across this proof, which is slightly similar, but not exactly the same.

$\endgroup$
  • $\begingroup$ I take it you don't want to use unique prime factorization either? $\endgroup$ – pjs36 Oct 6 '15 at 1:37
  • $\begingroup$ Yeah, this isn't something we have normally used in our text with these kinds of problems, but if you can use it to show another way to do the proof that would be great to see. $\endgroup$ – metausar Oct 6 '15 at 2:10
0
$\begingroup$

If $(a,b)=1$ then there are $s, t$ so $1=sa+tb$ iff $c=sac+tbc$. If $a$ divides $bc$ then $a$ divides the entire right-hand side. So $a$ divides $c$.

In the other direction (via contrapositive), if $(a,b)=d\neq 1$ then for some $n, m$ we have $a=nd$, $b=md$. Take $c=n$. So $a\mid mdn=bc$ but $a\not\mid n=c$ (or else $a$ is a proper divisor of itself).

| cite | improve this answer | |
$\endgroup$

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.