# 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 |