1

Claim: $a,b,c \in \mathbb{Z}, $ with $c$ prime. If $c \mid ab$ then $c \mid a$ or $c \mid b.$

My Proposed Proof (Contrapositive): Suppose $c\nmid a, c\nmid b$. So, $a = cd + r$ and $b = ce + q$, with $d,e,q, r \in \mathbb{Z}$. Note $q, r \ne 0 \ne c.$ Next, $ab = c^2ed + cdq + cer + qr = c(ced + dq + er) + qr.$ Since $c$ is prime $qr \ne c$. Therefore $c\nmid ab$.

I am in an intro to proofs class, I just want to know if this proof is valid.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
cbankr22
  • 33
  • 2
  • 1
    Note that you need to argue that $c$ doesn't divide $qr$, not just that $c\neq qr$. – lulu Mar 01 '23 at 01:06
  • @ColinAcker FYI, see [Euclid's lemma](https://en.wikipedia.org/wiki/Euclid%27s_lemma). – John Omielan Mar 01 '23 at 01:10
  • 1
    It may be interesting to compare with the proof in Euclid (book VII proposition 30). https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII30.html – GEdgar Mar 01 '23 at 01:15
  • To stress, this is incomplete as it stands. All you conclude is that $c\,|\,ab\implies c\,|\,qr$ but why is that impossible? Of course, if we knew the result, we'd know this was impossible...$c$ is a prime and $c$ can't divide either of $q,r$. But that's ciruclar reasoning. – lulu Mar 01 '23 at 01:18
  • Hint: Equivalently transform the statement into: $$p\mid ab\ \mbox{and}\ p\nmid a\ \mbox{then}\ p\mid b.$$ Because then you have $ab=pm$ for some integer $m$ and $p,a$ would be coprime which implies that $p\lambda+a\mu=1$ for another integers $\lambda,\mu$. – janmarqz Mar 01 '23 at 01:36
  • 1
    What you proved is $\bmod c\!:\ a\equiv r,\ b\equiv q\Rightarrow ab\equiv rq,\,$ i.e. the [Congruence Product Rule](https://math.stackexchange.com/a/879262/242). You can use this to reduce this Euclid's Lemma to the case $\,0\le a,b < c,\,$ but you have not proved this reduced version. We already have most all known proofs of Euclid's Lemma in prior answers (so please don't duplicate them further in answers below). – Bill Dubuque Mar 01 '23 at 02:23
  • 1
    For a `solution-verification` question to be on topic you must specify *precisely* which step in the proof you question, and *why so*. This site is not meant to be an open-ended proof checking machine. – Bill Dubuque Mar 01 '23 at 02:26

0 Answers0