English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


Proofs

Example 2. Prove the following results:

(a) If c is a non-zero rational number , then c π is irrational.
(b) If m3 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 n2 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 non-zero. 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 m3 is even, then m is even. We shall prove the contrapositive instead; we
shall assume that m is not even and show that m3 is not even. That is, we shall assume
that m is odd and show that m3 is odd.

Proof. Assume that m is odd. Then m = 2 k +1 for some integer k . Then,

m3
= (2 k + 1)3
= 8k3 +12k2 + 6k + 1
= 2(4k3 + 6k 2 + 3k) + 1
= 2l + 1,

where l is the integer 4k3 + 6k2 + 3k . Thus, m3 is odd because it is written in the form
of an odd integer. By contrapositive, if m3 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 n2 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 ri are natural numbers and the pi are distinct primes. Because n is not divisible
by 3, then pi ≠ 3 for 1 ≤ i ≤ k . By squaring we obtain

which is a prime factorization of n 2. By uniqueness of prime factorization, the above pi
for 1 ≤ i ≤ k are the only prime factors of n 2. Because none of the pi equals 3, then n2 is
not divisible by 3. By contrapositive, if n2 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 nk 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 n2 is even.

Proof. Suppose first that n is even. Then n = 2k , for some integer k . So then

n2 = (2 k )2 = 4k2 = 2(2k2 ).

Because 2k2 is also an integer, we see that n2 must be even.

Next we must prove that if n2 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

n2 = (2k +1)2 = 4k 2 + 4k + 1 = 2(2k2 + 2k) +1 = 2 j +1,

where j = 2k2 + 2k is an integer. Hence, n2 is odd; that is, n2 is not even. We have
proven that if n is not even, then n2 is not even. By contrapositive, if n2 is even, then n
is even. From both directions, we now have that n is even if and only if n2 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 n2 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 2n2 = m2 .

Thus, m2 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

2n2 = m2 = (2 k)2 = 4k 2 = 2(2 k2 ), which gives n2 = 2k 2.

Thus, n2 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 b2.

(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