# Salvage of a divisibility proposition.

• Feb 17th 2011, 10:32 AM
Dinghy
Salvage of a divisibility proposition.
Problem:
"Determine the sufficient (and if possible necessary) conditions on an integer n for the following statement to be true: "For integers a and b, if n doesn't divide ab, then n doesn't divide a and n doesn't divide b." Then state the condition on n and the resulting implication as a proposition and prove it"

I was able to work out something that makes sense to me, but considering I didn't put a specific condition on n, I was wondering if I might have made a mistake.

Attempted proof:
"Assume that n, a, and b are integers such that n doesn't divide ab. Since n doesn't divide ab, by definition ab does not equal kn, where k is some integer. Because ab does not equal kn, neither a nor b can be multiples of n, otherwise ab would produce another multiple of n, which n would divide. Because a does not equal kn and b does not equal kn, n doesn't divide a and n doesn't divide b respectively."
• Feb 17th 2011, 11:15 PM
emakarov
Quote:

Originally Posted by Dinghy
Problem:
"Determine the sufficient (and if possible necessary) conditions on an integer n for the following statement to be true: "For integers a and b, if n doesn't divide ab, then n doesn't divide a and n doesn't divide b."

Since this is supposed to be a property of n only (not of a, b), I assume the property is, "For all integers a and b, if n doesn't divide ab...". Let's denote it by P(n). Its contrapositive, which is equivalent to the original statement, is, "For all a and b, if n divides a or n divides b, then n divides ab". I agree that it is true for all n. To be formal, one can say that the necessary and sufficient condition Q(n) on n is True. I.e., we have for all n, Q(n) <-> P(n).