Proof About Division of Integers

Question

Here is a problem I just finished working on:

Prove that if $n$ is composite then there are integers $a$ and $b$ such that $n$ divides $ab$ but not $n$ does not divide either $a$ or $b$.

One thing I noticed while proving this is, that we are showing that there exist a pair of integers such that the conditional relationship is true; is it possible to find a pair such that it is not true, that $n$ divides both $a$ and $b$ individually?

Yes there is! The simplest example is that for any $n$, $n\mid n\times n$. — Mathmo123, Jul 13 '14 at 18:43

score 0 · Answer 1 · answered Jul 13 '14 at 19:01

The words "there are" tell you that the problem is asking about existence.

Words that mean existence ($\exists$) include "there is", "there exists", "one can find", etc.

Words that mean the statement is true for all ($\forall$) members of the specified set include "all", "every", etc.

"Any" is a tricky word that is best avoided.

EDIT: For a specific answer to your specific question, the statement is not true for all integers. Let $n = a = b = 4$. Then $n$ is composite and it divides $a$ and $b$ and $ab$.

That is what I figured, that the problem was concerned with existence, but I was not exactly certain. — Mack, Jul 13 '14 at 20:38

score -1 · Answer 2 · answered Jul 13 '14 at 18:56

-1

$60 = 15\times 4$. So $60$ divides $15\times4$ but $60$ does not divide $15$ and $60$ does not divide $4$.

You can do the same with any composite number.

answered Jul 13 '14 at 18:56

Michael Hardy

1

Proof About Division of Integers

2 Answers2