Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section3.2Proofs by contradiction

In this section we study an important tool to prove mathematical theorems. This tool is called proof by contradiction or indirect proof. There is a simple logic behind, instead of proving that something must be true, we prove it indirectly by showing that it cannot be false. We assume that the opposite of our theorem is true. From this assumption we try to obtain such a conclusion which is known to be false. This contradiction then shows that our theorem must be true.

Let us consider a basic example. We try to prove that \(\sqrt{2}\) is irrational. We provide an indirect proof. We assume the opposite of our statement, that is, that \(\sqrt{2}\) is rational. Rational numbers can be written as \(\frac{a}{b}\) for some \(a\in\mathbb{Z}\) and \(b\in\mathbb{N}\) such that the greatest common divisor of \(a\) and \(b\) is 1. So we have

\begin{equation*} \sqrt{2}=\frac{a}{b}\text{.} \end{equation*}

Hence \(a^2=2b^2\text{.}\) It follows that 2 divides \(a\text{,}\) so \(a=2a_1\) for some \(a_1\in\mathbb{Z}\text{.}\) We substitute this into the equation \(a^2=2b^2\) and we get \(4a_1^2=2b^2\text{.}\) After dividing by 2 we get \(2a_1^2=b^2\text{.}\) So we have that 2 divides \(b\text{.}\) We have a contradiction since the greatest common divisor of \(a\) and \(b\) should be 1, but we obtained that 2 divides \(a\) and also divides \(b\text{.}\) Hence 2 divides the greatest common divisor. This contradiction shows that our statement must be true, that is, \(\sqrt{2}\) is irrational.

In Section 1.3 there is a statement about the Division algorithm which says that given two integers \(a\) and \(b\) such that \(b>0\text{,}\) there exist unique integers \(q\) and \(r\) for which

\begin{equation*} a=qb+r, 0\leq r\lt b\text{.} \end{equation*}

Now we prove that \(q\) and \(r\) are unique. We give a proof by contradiction. Assume that there exist integers \(q,q'\) and \(r,r'\) such that \(q\neq q'\) or \(r\neq r'\) and

\begin{align*} a\amp =qb+r, 0\leq r\lt b,\\ a\amp =q'b+r', 0\leq r'\lt b\text{.} \end{align*}

The above equations imply that

\begin{equation*} b(q-q')=r'-r\text{.} \end{equation*}

It follows that \(b\) divides \(r'-r\text{.}\) We also have the inequalities

\begin{align*} 0\leq \amp r\lt b,\\ 0\leq \amp r'\lt b\text{.} \end{align*}

So we have that

\begin{equation*} -b\lt r'-r\lt b\text{.} \end{equation*}

There is only one integer in this interval which is a multiple of \(b\text{,}\) namely 0. We obtained that \(r'-r=0\text{,}\) that is, \(r'=r\text{.}\) Also we have that \(b(q-q')=r'-r=0\text{.}\) Since \(b>0\text{,}\) it is clear that \(q-q'=0\) must hold, hence \(q=q'\text{.}\) A contradiction, since we assumed that \(q\neq q'\) or \(r\neq r'\text{.}\)

Let us consider a proposition about prime numbers (a positive integer is prime if it is greater than 1 and has no positive divisors other than 1 and the number itself.) If \(p,q\) and \(r\) are prime numbers, then

\begin{equation*} p^2+q^2\neq r^2\text{.} \end{equation*}

Assume the opposite, that is, there exist prime numbers \(p,q\) and \(r\) such that \(p^2+q^2=r^2\text{.}\) There are three possibilities

  1. \(p\) and \(q\) are odd primes,

  2. \(p\) and \(q\) are even primes,

  3. one of the primes \(p,q\) is even the other is odd.

(1) We have that \(p\) and \(q\) are odd primes, hence \(p^2+q^2=r^2\) is even. If \(r^2\) is even, then \(r\) is even. The only even prime number is 2, so we have \(r=2\text{.}\) That is, \(p^2+q^2=4\text{.}\) Since \(p\) and \(q\) are odd primes we have \(p,q\geq 3\text{.}\) Therefore \(p^2+q^2\geq 18\text{,}\) a contradiction. We proved that if \(p\) and \(q\) are odd primes, then the statement must be true.

(2) We have that \(p\) and \(q\) are even primes, that is, \(p=q=2\text{.}\) We obtain that \(8=r^2\text{.}\) It implies that \(r\) is even, so \(r=2\text{.}\) A contradiction since \(r^2=4\) while we concluded that \(r^2\) must be 8. In this case our statement turns out to be true.

(3) We may suppose that \(p\) is even and \(q\) is odd. That is, \(p=2\) and \(q=2q_1+1\) for some \(q_1\text{.}\) It is clear that \(r\) is also odd, since its square is a sum of an even number and an odd number, that is, \(r=2r_1+1\text{.}\) Our equation implies that \(4+(2q_1+1)^2=(2r_1+1)^2\text{,}\) which can be written as

\begin{equation*} 4+4q_1^2+4q_1+1=4r_1^2+4r_1+1\text{.} \end{equation*}

One gets that

\begin{equation*} q_1(q_1+1)+1=r_1(r_1+1)\text{.} \end{equation*}

The product of two consecutive integers is even, so \(q_1(q_1+1)\) and \(r_1(r_1+1)\) are even. Then we have that \(r_1(r_1+1)-q_1(q_1+1)\) is an even integer, but the above equation implies that

\begin{equation*} r_1(r_1+1)-q_1(q_1+1)=1\text{,} \end{equation*}

a contradiction since 1 is not an even integer.

Now we prove a result related to prime numbers. The proof we provide is a nice indirect proof due to Euclid.

Suppose that there are only finitely many primes, let say \(p_1\lt p_2\lt p_3\lt \ldots\lt p_n\text{.}\) Let us consider the integer

\begin{equation*} N=p_1p_2\cdots p_n+1\text{.} \end{equation*}

Since \(N\) is not on the list of prime numbers it must have a prime divisor. It means that for some \(1\leq i\leq n\) the prime \(p_i\) divides \(N\text{.}\) Applying the Division algorithm we obtain

\begin{equation*} N=\left(\prod_{1\leq k\leq n, k\neq i}p_k\right)\cdot p_i+1\text{,} \end{equation*}

that is, the remainder is equal to 1. Thus \(N\) is not divisible by \(p_i\text{,}\) a contradiction. Thus we have proved that there are infinitely many primes.

Prove that if \(x+y>10\) for some \(x,y\in\mathbb{Z}\text{,}\) then \(x>5\) or \(y>5\text{.}\)

Prove that there exists no integer \(n\) such that \(n^2-2\) is a multiple of 4.

Prove that \(\sqrt{2}+\sqrt{3}\) is irrational.

Prove that if \(a,b\) and \(c\) are odd integers, then the equation

\begin{equation*} ax^2+bx+c=0 \end{equation*}

has no solution with \(x\in\mathbb{Q}\text{.}\)

Given \(n\) integers \(a_1,a_2,\ldots,a_n\text{,}\) prove that there exists \(1\leq i\leq n\) such that

\begin{equation*} a_i\geq \frac{a_1+a_2+\ldots+a_n}{n}\text{.} \end{equation*}

Let \(F_n\) be a sequence defined by \(F_1=F_2=1\) and \(F_n=F_{n-1}+F_{n-2}, n\geq 3\text{,}\) that is, the Fibonacci sequence. Prove that \(\gcd(F_n,F_{n+1})=1\) for all positive integer \(n\text{.}\)