Try our Free Online Math Solver!

Proofs
Example 2. Prove the following results:
(a) If c is a nonzero rational number , then c π is
irrational.
(b) If m^{3} is even, then m is even.
(c) For all real numbers x and y , if x + y > 0, then x > 0 or y > 0.
(d) Let n be an integer. If n^{2} is divisible by 3, then n is divisible by 3.
(e) Let x be a real number . If
for all
,
then x = 0 .
(a) Proof. (By contradiction) Let c be a non zero rational
number, and suppose that c π
is rational. Then c π = m / n , where m , n are integers and n ≠ 0. Moreover, c
= j / k ,
where j , k are integers and k ≠ 0, but also j ≠ 0 because c is nonzero. We
then have
The products of integers k m and jn are still integers,
and jn cannot be 0 because
neither n nor j is 0. Thus, π is in the form of a rational number, which is a
contradiction because π is irrational. Ergo, c π must be irrational. QED
                                       
                          
(b) Claim: If m^{3} is even, then m is even. We shall prove
the contrapositive instead; we
shall assume that m is not even and show that m^{3} is not even. That is, we shall
assume
that m is odd and show that m^{3} is odd.
Proof. Assume that m is odd. Then m = 2 k +1 for some integer k . Then,
m^{3}
= (2 k + 1)^{3}
= 8k^{3} +12k^{2} + 6k + 1
= 2(4k^{3} + 6k ^{2} + 3k) + 1
= 2l + 1,
where l is the integer 4k^{3} + 6k^{2} + 3k . Thus, m^{3} is odd
because it is written in the form
of an odd integer. By contrapositive, if m^{3} is even, then m is even. QED
                                       
                          
(c) Proof. Let x and y be real numbers . Assume that x ≤ 0
and y ≤ 0. Then by adding ,
we have x + y ≤ 0 + 0 = 0. That is, x + y ≤ 0. Hence, x ≤ 0 and y ≤ 0 implies
that
x + y ≤ 0. By contrapositive, if x + y > 0, then x > 0 or y > 0. QED
(d) Claim: For an integer n , if n^{2} is divisible by 3, then n is divisible by 3.
Proof. Assume n is not divisible by 3. We then can apply
the Fundamental Theorem of
Arithmetic to write n uniquely as a product of powers of primes as follows:
where r_{i} are natural numbers and the p_{i} are distinct
primes. Because n is not divisible
by 3, then p_{i} ≠ 3 for 1 ≤ i ≤ k . By squaring we obtain
which is a prime factorization of n ^{2}. By uniqueness of
prime factorization, the above p_{i}
for 1 ≤ i ≤ k are the only prime factors of n ^{2}. Because none of the p_{i} equals
3, then n^{2} is
not divisible by 3. By contrapositive, if n^{2} is divisible by 3, then n must
also be divisible
by 3. QED
                                       
                          
Note: The preceding result can be generalized as follows:
Let p be prime and suppose k ≥ 2 . If n^{k }is divisible by p , then n is
divisible by p .
(In the proof of (d), simply replace 3 with p and replace the exponent 2 with k
.)
                                       
                          
(e) Claim: If all , then x = 0 .
Proof. Suppose
all
We must show that x = 0 . So suppose that x
≠ 0
.
Then x < 0 or x > 0. In either case, we have
. Now let
. For
this
, we then have
, which contradicts the assumption. Thus we must
have that x = 0 . QED
Note: We also could have argued by contrapositive: Assume x
≠ 0 . Then we showed
that there exists an
for which
fails. So if x
≠ 0 , then it is not true
that
for all. By contrapositve, if it is true that
for all
, then x =
0 .
Double Implication
A double implication is of the form p ↔ q, which is read “ p if and only if q ”.
This
statement means p → q and q → p and both implications must be proven.
Example 3. Let n be an integer. Then n is even if and only if n^{2} is even.
Proof. Suppose first that n is even. Then n = 2k , for some integer k . So then
n^{2} = (2 k )^{2} = 4k^{2} = 2(2k^{2} ).
Because 2k^{2} is also an integer, we see that n^{2} must be even.
Next we must prove that if n^{2} is even, then n is even. But we shall prove the
contrapositive instead. So assume that n is not even, i.e., that n is odd. Then
n = 2k +1
for some integer k . We then have
n^{2} = (2k +1)^{2} = 4k ^{2} + 4k + 1 = 2(2k^{2} + 2k) +1 = 2 j +1,
where j = 2k^{2} + 2k is an integer. Hence, n^{2} is odd; that is, n^{2} is not even. We
have
proven that if n is not even, then n^{2} is not even. By contrapositive, if n^{2} is
even, then n
is even. From both directions, we now have that n is even if and only if n^{2} is
even.
QED
Note: The second direction also follows from the generalization of Part (d)
using the
prime p = 2 . In other words, if 2 divides n^{2} then 2 divides n .
                                       
                          
Theorem. is irrational.
Proof. Assume
is rational. Then we can write
= m / n , where m and n are
integers with n ≠ 0. Furthermore, we can assume that the fraction is reduced so
that m
and n have no common divisors . Then by squaring the fraction , we have
or 2n^{2} = m^{2} .
Thus, m^{2} is even because it is divisible by 2. It follows that the integer m
must be
even (by Example 3). So we may write m = 2k for some integer k . Then
2n^{2} = m^{2} = (2 k)^{2} = 4k ^{2} = 2(2 k^{2} ), which gives n^{2} = 2k ^{2}.
Thus, n^{2} is even because it is divisible by 2. It follows that the integer n
also must
be even. So both m and n are even and therefore both are divisible by 2. But
this fact
contradicts the assumption that we have chosen m and n to have no common
divisors.
This contradiction leads us to conclude that
cannot be written as a fraction.
Thus,
is irrational. QED
Corollary. For any prime p , is irrational.
Exercises
Prove the following results in a formal, elegantly written, mathematical style :
(a) For all integers m and n , if m is even and n is odd, then m + n is odd.
(b) Let a be an integer. If a divides b , then b is an integer and a divides b^{2}.
(c) If x and y are rational numbers, then x + y is a rational number.
(d) Let m and n be integers. If m n is even, then m is even or n is even.
(e) Let m and n be integers. If m + n is odd, then m is odd or n is odd but not both.
(f) Let x and y be real numbers. Then x = y if and only if for every .
(g) For any prime p , is irrational.
Prev  Next 