Games
Problems
Go Pro!

Reference > Mathematics > Introduction to Proofs

Proof by contradiction is a very interesting form of proof, in which we make an assumption (usually we're not allowed to make assumptions when doing proofs) and use the assumption to arrive at a contradiction. Once we have a contradiction, we know that the assumption can't be true. Let's take a look at an example.

Prove: No proper divisors of an integer are more than half of that integer.

Proper divisors are numbers that are less than the number itself. For example, the proper divisors of 12 are 1, 2, 3, 4, and 6. There are no proper divisors of 12 that are bigger than 6.  It makes sense, doesn't it? But how do we prove it?

We assume the opposite, and create a contradiction.

```STATEMENT                                                    REASON
1. Let k be a divisor of n such that n2 < k < n               Assumption
2. n < 2k < 2n                                               Multiplicative property of inequality (x2)
3. There exists a positive integer j such that kj = n        Definition of a divisor
4. kj < 2k and 2k < 2kj                                      Substitution property of inequality
5. j < 2 and 2 < 2j                                          Division property of inequality (/k)
6. j < 2  and 1 < j                                          Division property of inequality (/2)
```

Line 6 states that j is between 1 and 2, but there are no integers between 1 and 2, which violates statement 3, leading to a contradiction.

Since we've generated a contradiction, we can conclude that our assumption in statement 1 is invalid. Thus, no proper divisors of an integer are more than half of that integer.

## Questions

1.
Prove by contradiction: If x is even, x2 is a multiple of 4
2.
Prove by contradiction: If x and y are both even, their sum is even. Assign this reference page Transitive Property in Proofs Lemmas, If and Only If Theorems   Like us on Facebook to get updates about new resources