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.
From (1) we conclude that a^2 is even. This fact combined with the result of
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.
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
p1, p2, . . . , pk, and positive integers e1, e2, . . . , ek such that
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
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.
Example 5. Show that there exist irrational numbers x and y such that xy is rational.
Solution. We know that √2 is an irrational number. Consider
Case I: is
In this case we are done by setting x = y = √2.
Case II: is
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
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.
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