How can I prove that if a is not divisible by c and b is not divisible by c then ab is not divisible by c?

Answer 1

Divisibility is another means to say no remainder (i.e quotient only).

Modulus is a way to extract only the remainder part.

For example 10/5 = 2 without remainder --> 10 mod 5 = 0 whereas 9/5 = 1.8 or 9 mod 5 = 4

So if a is not divisible by c then a mod c > 0 --> call this reminder A

Also if b is not divisible by c then b mod c > 0 --> call this reminder B

Now we come to the question at hand and we are interested in a*b which neither has a fully integer representation of c embedded within it...

ab mod c = ( a mod c * b mod c ) mod c --> ( A*B ) mod c > 0 for any A ≠ 0 or B ≠ 0 as per the initial conditions provided by a's divisibility and b's divisibility with c.

Answer 2

Suggest that you start with a statement of the contrapositive:

If ab is divisible by c, then a or b are divisible by c.

Then prove the contrapositive.

Answer 3

A is not divisible by c ----> a = cn + r , where r is a non zero remainder

B is not divisible by c ----> B = cM + s, where s is a non zero remainder

AB = (cn+r)(cM + s)

= c^2nM + csn + crM + rs

= c( cnM + sn + rM) + rs

so AB is the product of c and some number cnM + sn + rM),

with remainder rs.

Most importantly, the remainder rs is NOT zero since neither r nor s is zero.

therefore c does not divide AB evenly.

end of proof