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₁, p₂, . . . , p_k, and positive integers e₁, e₂, . . . , 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