Try our Free Online Math Solver!

Lecture Outline: Numbers
Example 1. Prove that the product of two odd numbers is an odd number.
Solution . Let x and y be particular but arbitrarily chosen odd
numbers. Then, x = 2k+1
and y = 2l + 1, for some integers k and l. We have
Let p = 2kl + k + l. Since k and l are integers, p is an integer and x · y = 2p + 1 is odd.
Example 2. Prove that √2 is irrational.
Solution. For the purpose of contradiction, assume that √2 be a
rational number. Then
there are numbers a and b with no common factors such that
Squaring both sides of the above equation gives
From (1) we conclude that a^2 is even. This fact combined with the result of
Example 1
implies that a is even. Then, for some integer k, let
a = 2k
Combining (1) and (2) we get
The above equation implies that b^2 is even and hence b is even. Since we
know a is even
this means that a and b have 2 as a common factor which contradicts the
assumption that
a and b have no common factors .
We will now give a very elegant proof for the fact that “√2 is irrational”
using the unique
factorization theorem which is also called the fundamental theorem of
arithmetic .
The unique factorization theorem states that every positive number can be uniquely represented as a product of primes . More formally, it can be stated as follows.
Given any integer n > 1, there exist a positive integer k, distinct prime
numbers
p_{1}, p_{2}, . . . , p_{k}, and positive integers e_{1}, e_{2}, . . . , e_{k} such that
and any other expression of n as a product of primes is identical to this
except,
perhaps, for the order in which the factors are written.
Example 3. Prove that √2 is irrational using the unique factorization theorem.
Solution. Assume for the purpose of contradiction that √2 is rational.
Then there are
numbers a and b (b ≠ 0) such that
Squaring both sides of the above equation gives
Let S(m) be the sum of the number of times each prime factor occurs in the
unique
factorization of m. Note that S(a^2) and S(b^2) is even. Why? Because the number
of times
that each prime factor appears in the prime factorization of a^2 and b^2 is
exactly twice the
number of times that it appears in the prime factorization of a and b. Then,
S(2b^2) must
be odd. This is a contradiction as S(a^2) is even and the prime factorization of
a positive
integer is unique.
Example 4. Prove or disprove that the sum of two irrational numbers is irrational.
Solution. The above statement is false. Consider the two irrational
numbers, √2 and
−√2. Their sum is 0 = 0/1, a rational number .
Example 5. Show that there exist irrational numbers x and y such that x^{y} is rational.
Solution. We know that √2 is an irrational number. Consider
Case I: is
rational .
In this case we are done by setting x = y = √2.
Case II: is
irrational.
In this case, let and let y = √2. Then,
which is an integer and hence rational.
Example 6. Prove that for all positive integers n,
n is even ↔ 7n + 4 is even
Solution. Let n be a particular but arbitrarily
chosen integer.
Proof for n is even → 7n + 4 is even. Since n is even, n = 2k for some integer
k. Then,
Hence, 7n + 4 is even.
Proof for 7n + 4 is even → n is even. Since 7n + 4 is
even, 7n + 4 = 2l for some integer l.
Then,
7n = 2l − 4 = 2(l − 2)
Clearly, 7n is even. Combining the fact that 7 is odd with
the result of the Example 1, we
conclude that n is even.
We can also prove the latter by proving its contrapositive, i.e., we can prove
if n is odd then 7n + 4 is odd.
Since n is odd we have n = 2k + 1, for some integerk. Thus we have
Prev  Next 