Skip to main content

Introduction to Proofs: An Active Exploration of Mathematical Language

Jennifer Firkins Nordstrom

Section 3.2 More Direct Proof: Rational Numbers and Divisibility

In this section we introduce some new defintions and use them to practice with the technique of direct proof.

Subsection 3.2.1 Rational Numbers

The set of real numbers is the set you are likely familiar with from your previous math courses, particularly algebra and calculus. These are all the numbers found on the number line, such as \(0, 1, -3, 1/2, \pi, \sqrt{2}\text{,}\) etc. Recall, we use the notation \(\mathbb{R}\) for the set of real numbers.

Definition 3.2.1.

A real number, \(r\text{,}\) is rational if there exist \(a, b\in \mathbb{Z}\) such that \(r=\frac{a}{b}\) and \(b\neq 0\text{.}\) The set of rational numbers is represented by \(\mathbb{Q}\)

Definition 3.2.2.

A real number, \(r\text{,}\) that is not rational is irrational. There is not a nice notation for the irrational numbers. We will use \(\mathbb{R}\setminus\mathbb{Q}\), which is the set of real numbers minus the set of rationals.
To determine if a given number is rational, we need to be able to find a way to write it as a fraction of integers. To prove a number is rational is really a type of existence proof--we need to show \(a, b\in \mathbb{Z}\) exist. To prove a number is not rational, we need to show there is no possible way to write it as a fraction of integers. Also, keep in mind that rational and irrational numbers first need to be real numbers. It is possible that a number that is not rational is not a real number, and thus, not irrational either.
Is \(O\) is rational?
Answer 1.
Yes: \(0=0/1\text{.}\)
Is \(2\) rational?
Answer 2.
Yes: \(2=2/1\text{.}\)
Is \(9/5\) rational?
Answer 3.
Yes: it already has the form of an integer over an integer.
Is \(2/0\) rational?
Answer 4.
No: the demoninator cannot be 0. In fact, \(2/0\) is not a number.
You have seen some common examples of irrational numbers in previous courses: \(\sqrt{2}, \pi, e\text{.}\) It is, in fact, challenging to prove these are irrational. We will see the proof that \(\sqrt{2}\) is irrational later in Section 3.4.
In your earlier dealings with rational and irrational numbers, you may have seen the property that rational numbers are ones with terminating or repeating decimal expansions, while irrational numbers have non-terminating and non-repeating decimal expansions. The next couple of examples explore this property.
Show \(0.2345\) is a rational number.
We need to find \(a, b\in \mathbb{Z}\) such that \(0.2345=\frac{a}{b}\) and \(b\neq 0\text{.}\) We can use what we know about decimals: for example, \(0.1=1/10; 0.01=1/100\text{.}\) Thus, \(0.2345=2345/10000\text{.}\) Letting \(a=2345, b=10000\text{,}\) we can see that \(a, b\in \mathbb{Z}, b\neq 0\text{.}\)
Show the repeating decimal \(0.\overline{123}\) is a rational number.
We need to find \(a, b\in \mathbb{Z}\) such that \(0.\overline{123}=\frac{a}{b}\) and \(b\neq 0\text{.}\) This one is trickier than the last example and requires a new technique. First, let \(x=0.\overline{123}=0.123123\ldots\text{.}\) Then multiply both sides of \(x=0.123123\ldots\) by 1000, so that \(1000x=123.123123\ldots\text{.}\) We chose 1000 in order to get one set of the repeated digits in front of the decimal point. Now we subtract the two equations from each other:
\begin{align*} 123.123123\ldots &=1000x\\ -(0.123123\ldots&=x) \end{align*}
Resulting in \(123=999x\text{.}\) Now we just solve for \(x=123/999\text{.}\)
Letting \(a=123, b=999\text{,}\) we can see that \(a, b\in \mathbb{Z}, b\neq 0\text{.}\)

Activity 3.2.1. Practice with Rational Numbers.

Prove the following numbers, \(x\text{,}\) are rational by finding integers, \(a\) and \(b\) so that \(x=\frac{a}{b}\text{.}\)
(a)
\(x=12.345\)
(b)
\(x=12.\overline{3}\)
(c)
\(x=1.2\overline{34}\)
The next theorem gives us an example of how to prove more general statements with rational numbers.
Let \(r, s\) be rational. Show \(r+s\) is rational.
Since \(r\) is rational, it can be written as \(\frac{a}{b}\) for some \(a, b\in \mathbb{Z}, b\neq 0\text{.}\) Similarly, since \(s\) is rational, it can be written as \(\frac{p}{q}\) for some \(p, q\in \mathbb{Z}, q\neq 0\text{.}\) (Note, we need to use different letters since \(r\) and \(s\) are not necessarily the same.) Now,
\begin{equation*} r+s=\frac{a}{b}+\frac{p}{q}. \end{equation*}
Finding a common denominator,
\begin{equation*} r+s=\frac{aq+bp}{pq}. \end{equation*}
Then \(aq+pb, pq \in \mathbb{Z}\) and, since \(p, q\neq 0, pq\neq 0\text{.}\) Therefore, \(r+s\) is rational.
Once we have proven a theorem, we can use it to prove additional statements. Note, a corollary is just a theorem that follows almost directly from a previous theorem.
Let \(r\) be a rational number. We want to show \(2r\) is rational. But \(2r=r+r\text{.}\) By Theorem 3.2.6, \(r+r\) is rational.

Activity 3.2.2. Proofs with Rationals.

Let \(r, s\) be rational numbers.
(a)
Prove \(r/2\) is rational.
(b)
Prove \(5r-2s\) is rational.
(c)
Prove or disprove \(\frac{1}{r}\) is rational.

Subsection 3.2.2 Divisibility

We introduce the idea of divisibility for integers. It is important to understand that this concept involves only integers and is not the same thing as division. Divisibility is a property while division is an operation.

Definition 3.2.8.

Let \(n, d\in \mathbb{Z}\text{.}\) Then \(n\) is divisible by \(d\) if \(n=dk\) for some \(k\in \mathbb{Z}\text{.}\)
If \(n=dk\) for some \(k\in \mathbb{Z}\) we can also say
  • \(n\) is a multiple of \(d\text{;}\)
  • \(d\) is a factor of \(n\text{;}\)
  • \(d\) is a divisor of \(n\text{;}\)
  • \(d\) divides \(n\text{.}\)
We use the notation \(d\mid n\), read “\(d\) divides \(n\text{.}\)”
Important note: \(d\mid n\) is a relationship between two integers. It is a statement that is either true or false. It does NOT equal a number. It is NOT the same thing as a fraction. It is not an equation, but it can be translated to the equation \(n=dk\) for some integer \(k\text{.}\)
It is useful to look at the special case when \(n\) or \(d\) is 0.
  • \(0\mid n\) is always false.
  • \(d\mid 0\) is true if \(d\neq 0\text{.}\)
  • Thus, \(0\mid 0\) is false, even though, technically, one could write \(0=0\cdot k\text{.}\)
Find the divisors of 6.
Answer 1.
1, 2, 3, 6, -1, -2, -3, -6
Find the divisors of 5.
Answer 2.
1, 5, -1, -5
Find the divisors of 1.
Answer 3.
1, -1
If \(d\) does not divide \(n\text{,}\) then for every \(k\in \mathbb{Z}, n\neq dk\text{.}\) This can be difficult to show in general, but if \(n\) and \(d\) are specific integers, you could show \(\frac{n}{d}\) is not an integer. This is the ONLY time a fraction can show up in proofs about divisibility.
Notation: \(d\nmid n\) means \(d\) does not divide \(n\text{.}\)
True or false: \(8\mid 24\text{.}\)
Answer 1.
True, \(24=8(3)\text{.}\)
True or false: \(8\mid 4\text{.}\)
Answer 2.
False, \(4=8(k)\) has no integer solutions since \(k=1/2\text{.}\)
True or false: \(8\mid 10\text{.}\)
Answer 3.
False, \(10=8(k)\) has no integer solutions since \(k=5/4\text{.}\)
True or false: \(8\mid -8\text{.}\)
Answer 4.
True, \(-8=8(-1)\text{.}\)
True or false: \(-2\mid 8\text{.}\)
Answer 5.
True, \(8=-2(-4)\text{.}\)
True or false: \(1\mid 4\text{.}\)
Answer 6.
True, \(4=1(4)\text{.}\)
True or false: \(8\mid 0\text{.}\)
Answer 7.
True, \(0=8(0)\text{.}\)
True or false: \(4\mid 1\text{.}\)
Answer 8.
False, \(1=4(k)\) has no integer solutions since \(k=1/4\text{.}\)
True or false: \(0\mid 8\text{.}\)
Answer 9.
False, \(8=0(k)\) has no integer solutions.

Activity 3.2.3. Divisibility Practice.

Determine if the following divisibility statements are true or false, and justify your answer.
(a)
\(3\mid 10\)
(b)
\(3\mid 0\)
(c)
\(3\mid 36\)
(d)
\(12\mid 4\)
(e)
\(0\mid 4\)
Now, we use the definition of divisibility to prove a more general theorem.
Let \(a, b, c\in \mathbb{Z}\text{.}\) Assume \(a\mid b\) and \(b\mid c\text{.}\) Then by definition, \(b=ak\) for some \(k\in \mathbb{Z}\) and \(c=bj\) for some \(j\in \mathbb{Z}\text{.}\) Substituting the first equation into the second, \(c=(ak)j=a(kj)\text{.}\) Since \(kj\in\mathbb{Z}\text{,}\) \(a\mid c\text{.}\)

Activity 3.2.4. Divisibility Proof.

Prove if 15 divides \(n\text{,}\) then 5 divides \(n\text{.}\)

Activity 3.2.5. Prove or Disprove.

Prove or disprove if 6 divides \(n\text{,}\) then 12 divides \(n\text{.}\)

Activity 3.2.6. Divisibility and Addition.

Prove if \(d\mid n\) and \(d\mid m\text{,}\) then \(d\mid (n+m)\text{.}\)

Exercises 3.2.3 Exercises

1.

Prove the following numbers are rational by writing them as a ratio of two integers.
  1. \(\displaystyle \frac{3}{7}+\frac{5}{9}\)
  2. \(\displaystyle 351.549249249\ldots\)

2.

Prove every integer is a rational number.

3.

Find the mistakes in the following “proof.”
Theorem: The sum of any two rational numbers is rational.
“Proof”: Suppose \(r\) and \(s\) are rational numbers. If \(r+s\) is rational, then by definition of rational \(r+s=a/b\) for integers \(a\) and \(b\) with \(b\neq0\text{.}\) Since \(r\) and \(s\) are rational, \(r=i/j\) and \(s=m/n\) for integers \(i, j, m\) and \(n\) with \(j\neq 0\) and \(n\neq 0\text{.}\) Thus
\begin{equation*} r+s=\frac{i}{j}+\frac{m}{n}=\frac{a}{b}, \end{equation*}
which is the quotient of two integers with nonzero denominator. Thus, it is rational.

4.

Consider the statement: The square of any rational number is a rational number.
  1. Write the statement formally as a conditional statement using variables.
  2. Determine whether the statement is true or false and justify your answer.

5.

Determine if the following statements are true or false. For true statements provide a proof. For false statements provide a counter example AND determine if a small change would make the statement true. If so, correct the statement and provide a proof of the new statement.
  1. The quotient of any two rational numbers is a rational number.
  2. If \(r\) and \(s\) are rational numbers then \(\frac{r+s}{2}\) is a rational number.

6.

Suppose \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\) are integers and \(a\neq c\text{.}\) Suppose also that \(x\) is a real number that satisfies the equation
\begin{equation*} \frac{ax+b}{cx+d}=1. \end{equation*}
Must \(x\) be rational? If so, express \(x\) as a ratio of two integers. Is the condition \(a\neq c\) important?
Hint.
Solve for \(x\text{.}\)

7.

Let \(n\in \mathbb{Z}\text{.}\) Determine if the following statements are true or false. Justify your answer.
  1. 3 divides \((3n+1)(3n+2)(3n+3)\text{.}\)
  2. \(6n(2n+10)\) is divisible by 4.
  3. 100 divides \((5n)^2(8n+24).\)

8.

Show that the following statement is false.
For all integers \(a\) and \(b\text{,}\) if \(3\mid (a+b)\) then \(3\mid (a-b)\text{.}\)

9.

Prove or disprove the following statements using the method of direct proof or counterexample.
  1. For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\mid b\) and \(a\mid c\text{,}\) then \(a\mid (b+c)\text{.}\)
  2. For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\mid b\) then \(a\mid (bc)\text{.}\)
  3. For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\) is a factor of \(c\text{,}\) then \(ab\) is a factor of \(c\text{.}\)
  4. For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\mid (b+c)\text{,}\) then \(a\mid b\) and \(a\mid c\text{.}\)
  5. For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\mid (bc)\) then \(a\mid b\) or \(a\mid c\text{.}\)
  6. For all integers \(a\) and \(b\text{,}\) if \(a\mid b\) then \(a^2\mid (b^2)\text{.}\)

10.

A fast food chain has a contest in which a card with numbers on it is given to each customer who makes a purchase. If some of the numbers on the card add up to 100, then the customer wins $100. A certain customer receives a card with the numbers
\begin{equation*} 72, 21, 15, 36, 69, 81, 9, 27, 42,\ {\rm and}\ 63\text{.} \end{equation*}
Will the customer win $100? Prove or disprove your claim.
<Prev^TopNext>