Please tell me what we did wrong with this proof. The question is:Let a,b and c be integers such that c.....?

divides a*b. Then either c divides a or c divides b.


First, we tried a bunch of examples, like when c=3 and ab=27, so a =3 and b=9, and you see that c divides a and c divides b. Or another one is when c=7 and ab=56, so a=7 and b=8, and we know that 7 divides 56 and also 7 divides 7. Also, if c=12 and a=5 and b=24, then ab=120, and you see that c divides 120, and slo c divides b, which is all we need because the conjecture is an "or" statement so we only need one of the conditions to be true. So we decided that the conjecture is true. Proof: Let a,band c be integers. We will prove the conjecture by contrapositive. So we assume that c doesn't divide a and that c doesn't divide b. We will show that c doesn't divide a*b. Since c doesn't dived a, then we know that a doesn't = c*m. Also, c doesn't divide b, so we know that b doesn't = s*n. So ab doesn't = (cm)(cn)=c(cmn). Now, cmn is an integer q(since c,m and n are all integers).Thus ab doesn't = cq for any int q. So c doesn't divide ab.

Please tell me what we did wrong with this proof. The question is:Let a,b and c be integers such that c.....?
Well, the basic problem you've run into is that the conjecture isn't true. If a = 6, b = 3, and c = 9, then a*b = 18, and 18/9 = 2, but neither 6 nor 3 is divisible by 9.





To prove that something is true you must prove it is true for all possible values of the variables, in this case a, b, and c. However, to prove something is false, you need only supply a single counter-example. Thus the above example disproves the conjecture that for all integers a, b, and c if a*b is divisible by c then a or b is also divisible by c.





Note that a ≠ cm and b ≠ cn does not imply that ab ≠ c(cmn). For example, if a = 6, b = 8, c = 2, m = 4, and n = 3, then cm = 2*3 = 8 ≠6 so cm ≠ a, and cn = 2 * 3 = 6 ≠ 8 so cn ≠ b. However, (cm)(cn) = 2 * 4 * 2 * 3 = 48, and a * b = 6 * 8 = 48, so ab = (cm)(cn). This proves that you cannot multiply not-equalities (i.e. statements with "doesn't equal).





Also, concluding that if c does not divide a or b implies that c does not divide ab is not the same as concluding that if c does divide ab it must also divide a or b. This logical fallacy is equivalent to the statement that for all plants, not a tree implies not a rock, so being a rock implies being a tree. The first statement is true: all plants that are not trees are also not rocks. However, the second statement is clearly false, as no rocks are also trees.
Reply:The thing you are trying to prove is not true. As an example, let a=2, b=3, and c=6. Now 6 divides 2*3=6, but 6 does not divide 2 or 3.





If you keep that example in mind as you go through the "proof" you see the logical error. Because a does not equal an integer times c, and b does not equal an integer times c, it does not follow that a*b does not equal an integer times c. We know what each is not, but that does not tell us what the product is not.