We say that an integer a is divisible by b if a=kb for some integer k. In other words ba​=k is an integer.

We write "a is divisible by b"

To write "a is not divisible by b" we write

Example

Prove by contradiction that if a positive integer d divides both n and n+1, then d=1.

Suppose that there exists an integers d=1 and n such that d∣n and d∣n+1. By the definition of divisibility:

where k,m∈Z.

Thus

and since m−k is an integer, this means

eg that d1​ is an integer. But the only positive integer that divides 1 is d=1, contradicting our supposition that d=1.

Thus, by contradiction, d must equal 1, Q.E.D.