Divisibility

An integer divides an integer , and we write (like ), if there exists an integer such that . If does not divide , then

For all integers , , and , if , and , then

Assume and . Since , there exists an integer such that . Since , there exists an integer such that .

Since , we conclude that .

For all integers , , and , if or , then

For all integers , , and , if and , then for all integers and ,

Let , , and be arbitrary integers, and assume that and . Since , there exists an integer such that . Since , there exists an integer such that . Let and be arbitrary integers. Then is also an integer.

Since is an integer, it follows from the definition of divisibility that

The symbolic form of DIC is:
The converse of this is: , which is true
However, the following statement is false:

Notice how in the second example, the and are outside the implication, so the hypothesis might hold true for just one pair of and for the statement to "move on".
For the first example, the hypothesis must divide EVERY and for , so the condition is much stronger.
i

For all natural numbers , if and , then

Let be arbitrary integers, and assume that and .
Since , there exists an integer such that (1).
Since , there exists an integers such that (2).

Substituting into (1), we obtain . Since we are working with only natural numbers, we conclude that , which means . Rearranging (2) for gives .
Substituting into (1) gives , so .

Finally, since we are only working with natural numbers, we have .