Proof Basics

Proofs

Author

Patrik Bak

1Introduction

The common perception of mathematics is that it is about calculation. In reality, however, it is about understanding generally valid statements. To be certain that these are indeed valid statements, and not just some measurement error, we precisely justify, or prove, these statements. It should therefore come as no surprise to us that proofs are an integral part of the Mathematical Olympiad, as well as university courses. In this material, we will provide a basic overview of what proofs look like in mathematics. We will illustrate them with several examples. The illustrative examples will mainly concern numbers, where the principles are best illustrated. However, the described theory can of course be applied in other areas – we will encounter proofs in all materials.

2Basic Types of Proofs

In general, we distinguish two basic types of proofs: direct proof and proof by contradiction. In short:

Direct proof: We derive the statement to be proved from valid statements.
Proof by contradiction: We assume that the statement to be proved does not hold and try to derive a mathematically invalid statement, to reach a contradiction.

We can imagine this as follows: Let's say that all the statements we start from are in a large pot of soup. The process of proving consists of combining statements from the soup and adding new ones from them – for example, if we have $a^3=1$ in the soup, we can add $a=1$ to the soup, thanks to which we can add $a^4-2a+1=0$ to the soup, etc. We then view our two types of proofs as follows:

A direct proof works by gradually adding new and new statements to the soup until we add the one we aim to prove.
On the other hand, in a proof by contradiction, we add the negation of the statement to be proved to the soup and proceed as if we were proving directly. We add new statements until the soup curdles and we get some nonsense, such as $0=1$ , or the opposite of one of the assumptions.

In the following two sections, we will show specific interesting examples of proofs. But first, two notes:

A very important technique is proof by mathematical induction. Strictly speaking, this is not so much a type of proof as it is a recipe for adding new valid statements to the soup.
In school, a distinction is usually made between two types of indirect proofs: indirect proof by contradiction and proof by contrapositive. We will explain that the latter is actually a special case of proof by contradiction.

2.1Direct Proof

Direct proofs are quite natural – we combine assumptions from the problem statement with existing knowledge until we reach the statement to be proved. Every proof can therefore be written as a series of chains of implications:

Example 1

Prove that the squares of odd numbers leave a remainder of 1 when divided by 8.

✓Solution

First, let's take this complete written proof:

Odd numbers can be written in the form $m=2n+1$ for an integer $n$ . We are proving that $m^2=(2n+1)^2=4n(n+1)+1$ leaves a remainder of 1 when divided by 8. One of the numbers $n$ , $n+1$ is even, so $n(n+1)$ is an even number, so $4n(n+1)$ is divisible by 8, so $m^2=4n(n+1)+1$ leaves a remainder of 1 when divided by 8, which was to be proved.

Before we go further, let's realize the structure of that proof. It consists of these statements:

$V_0$ : $m$ is an odd integer
$V_1$ : $m=2n+1$ for some integer $n$
$V_2$ : $n$ is an integer, thus $n$ is even or $n+1$ is even
$V_3$ : $n(n+1)$ is even
$V_4$ : $4n(n+1)$ is divisible by 8
$V_5$ : $4n(n+1)+1$ leaves a remainder of 1 when divided by 8
$V_6$ : $(2n+1)^2$ leaves a remainder of 1 when divided by 8
$V_7$ : $m^2$ leaves a remainder of 1 when divided by 8

The proof consists of the transitions $V_0 \Rightarrow V_1$ and $V_2 \Rightarrow V_3 \Rightarrow V_4 \Rightarrow V_5 \Rightarrow V_6$ . By combining $V_1$ and $V_6$ we get $V_7$ .

A verbal description is obviously more practical than a bulleted one. Its problem may be that more complicated problems can get lost in it: Poorly written solutions often fail because the implications are not clear from the text. Practical advice: for every statement, ask yourself the question: is it clear what the assumptions are and how something was derived from them? With such self-checking, one often realizes that their solution has a mistake.

Exercise 1

Prove that for prime numbers $p \ge 5$ , it holds that $p^2-1$ is a number divisible by 24.

✓Solution

We decompose the expression into the product $(p-1)(p+1)$ . Since $p$ is a prime number greater than 3, it is not divisible by 3, so it gives a remainder of 1 or 2. In the first case, 3 divides the factor $p-1$ , in the second $p+1$ . At the same time, $p$ is odd, so $p-1$ and $p+1$ are two consecutive even numbers. One of them is therefore divisible by 2 and the other even by 4, so their product is divisible by 8. Since the number $p^2-1$ is divisible by both 3 and 8, and these numbers are coprime, it is also divisible by 24.

As an interesting aside, let us present another solution that uses the result from the previous example: squares of odd numbers leave a remainder of 1 when divided by 8. Thanks to this, we actually have that $p^2-1$ is divisible by 8 – it remains to justify that $p^2-1$ is divisible by 3. Since $p$ is not 3, $p$ has the form either $3k+1$ or $3k-1$ for some $k$ , in short $p=3k \pm 1$ . Then

p^2-1 = (3k \pm 1)^2 - 1 = 9k^2 \pm 6k = 3(3k^2 \pm 2k),

which is clearly divisible by three.

In harder problems, it may not be immediately obvious how to use the assumptions from the problem statement and it is necessary to analyze the situation.

Example 2

Prove that if a natural number $n$ is the square of an integer, then it has an odd number of divisors.

✓Solution

How to use the fact that $n$ is the square of an integer? We can write $n=m^2$ , which was the first step in the previous illustrative example – but that won't help us for long. The key is to think about divisors, after all, we are proving something about them. The basic idea is:

Divisors of a natural number typically come in pairs, $d$ is a divisor of $n$ if and only if $n/d$ is a divisor of $n$ . If it never happened that these are the same divisors, then the number of divisors of $n$ is even.

But when does it happen that this pairing pairs a divisor with itself? Exactly when $d=n/d$ , i.e., when $d^2=n$ . And that is exactly our assumption! Consequently, all divisors except the divisor $\sqrt{n}$ will pair up with someone, so in total we will have an odd number of divisors, which was to be proved.

Note. This example actually holds as an equivalence. In fact, it would be easier if the reverse implication were given, because the fact that it is a square is used only at the end of the reasoning chain. In competition problems, however, it is common for authors to try to mask these key steps.

The previous example can also be solved using the generally useful formula for the number of divisors:

Theorem 1

Let $n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ , where $p_1,p_2,\dots,p_k$ are distinct prime numbers and $a_1,a_2,\dots,a_k$ are integers. Then the number $n$ has exactly

(a_1+1)(a_2+1)\cdots (a_k+1)

divisors.

Proof

Consider an arbitrary divisor $d$ of $n$ . Since $d$ divides $n$ and the prime factorization of $n$ contains only the primes $p_1,\dots,p_k$ , the factorization of $d$ must also contain only these primes. We can therefore write $d = p_1^{b_1} \cdot p_2^{b_2} \cdots p_k^{b_k}$ . For each $i$ , we must have $0 \leq b_i \leq a_i$ (the upper bound follows from the fact that $d$ , as a divisor of $n$ , cannot contain a higher power of $p_i$ than $n$ does). Every divisor can thus be uniquely represented as a $k$ -tuple $(b_1,\dots,b_k)$ satisfying $0 \leq b_i \leq a_i$ . The number of divisors is therefore equal to the number of such $k$ -tuples.

To determine the number of $k$ -tuples, we use the combinatorial rule of product. The choices of the individual exponents $b_1,\dots,b_k$ are independent of one another – the value of $b_i$ does not restrict the values of the other exponents in any way. For the exponent $b_i$ , we have $a_i+1$ options, namely all integers from $0$ to $a_i$ . By the rule of product, the total number of $k$ -tuples is

(a_1+1)(a_2+1)\cdots (a_k+1).

Exercise 2

Prove the previous example, i.e., the theorem about the oddness of the number of divisors of perfect squares, using the theorem on the number of divisors. Also prove the reverse implication of this theorem.

✓Solution

Let $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ . Since $n$ is the square of an integer, all exponents $a_1, \dots, a_k$ must be even. According to the theorem, the number of divisors is equal to the product $(a_1+1)(a_2+1)\cdots(a_k+1)$ . Since each $a_i$ is even, each parenthesis represents an odd number. The product of odd numbers is always odd, thus the number of divisors is odd.

Problem 1

Given a composite number $n > 1$ . Prove that it is divisible by a prime number not exceeding $\sqrt{n}$ .

1Hint

The number $n$ is composite, let's write it as $ab$ , where $1<a \leq b<n$ .

2Hint

The idea is to say that the smaller of the numbers $a,b$ , i.e., $a$ , is divisible by a sufficiently small prime. To do this, it suffices to say that it is sufficiently small in itself (in the tightest case, it is a prime itself).

✓Solution

Since $n$ is composite, we can write it as $n=ab$ , where $1 < a \le b < n$ . Multiplying the inequality $a \le b$ by the number $a$ , we get $a^2 \le ab = n$ , from which $a \le \sqrt{n}$ . The number $a>1$ has at least one prime divisor $p$ . Clearly $p \le a \le \sqrt{n}$ . Since $p$ divides $a$ and $a$ divides $n$ , then $p$ divides $n$ , which we wanted to prove.

Problem 2^*

A natural number $n$ has exactly $k$ divisors. Prove that the product of the divisors of $n$ is equal to $\sqrt{n^k}$ .

1Hint

Use the trick with the paired divisor again.

2Hint

Distinguish the cases where $n$ is and is not a square.

✓Solution

In the solution, we will consider the pairing of divisors: $d$ is a divisor of $n$ if and only if $n/d$ is a divisor of $n$ . The product of such divisors is $n$ .

Let's analyze two cases:

If $n$ is not a square, then for every divisor $d \neq n/d$ holds (otherwise $d^2=n$ ). All $k$ divisors thus form exactly $k/2$ such pairs. The total product is $n^{k/2} = \sqrt{n^k}$ .
If $n$ is a square, then $d=\sqrt{n}$ forms a pair with itself. The remaining $k-1$ divisors form $(k-1)/2$ pairs with product $n$ . The total product is therefore $n^{\frac{k-1}2} \cdot \sqrt{n} = n^{\frac{k}2 - \frac12 + \frac12} = \sqrt{n^k}.$

To conclude this section, one important note. When writing proofs, a common imprecision is omitting assumptions, for example someone may write $x^2=1$ , so necessarily $x=1$ . This can be a valid part of a solution, provided the problem statement tells us that $x$ is positive. However, if we do not include this assumption in the solution, it sounds suspicious because it is unclear whether the solver was aware of it, and therefore may lead to a loss of points. Correctly, we would write something like $x^2=1$ and $x$ is positive, so necessarily $x=1$ . Let us illustrate a very common situation where this occurs:

Example 3

When does $a \mid b$ and $b \mid a$ hold for integers $a,b$ ?

✓Solution

The intuitive answer is that necessarily $a=b$ . In solutions, we sometimes indeed see the reasoning that $a \mid b$ and $b \mid a$ , so $a=b$ . This is indeed true if we know that the numbers $a,b$ are non-negative. Let us analyze the situation in detail:

The relation $a \mid b$ gives that there exists an integer $u$ such that $b=au$ . Similarly, $b \mid a$ means that there exists an integer $v$ such that $a=bv$ . Multiplying these equalities, we have $ab=abuv$ .

If $ab=0$ , i.e., if for example $a=0$ , then the relation $b=au$ gives $b=0$ . Then both relations mean $0 \mid 0$ , which is fine† and $a=b$ holds.

If $ab\neq 0$ , then $ab=abuv$ gives $1=uv$ . The number $1$ can be written as a product of integers in exactly two ways: $1 \cdot 1$ and $(-1) \cdot (-1)$ . This gives us two solutions $(u,v)=(1,1)$ and $(u,v)=(-1,-1)$ , which correspond to $a=b$ and $a=-b$ . If, however, $a,b$ are non-negative, then either one is zero, which was resolved above, or both are positive, which cannot happen when $a=-b$ – so in that case we would indeed have $a=b$ .

The conclusion is that $a \mid b$ and $b \mid a$ if and only if $a=b$ or $a=-b$ , and for non-negative numbers even directly $a=b$ .

2.2Proof by Contradiction

This type of proof is particularly useful in cases where what is being proved is hard to grasp and it is far simpler to say something about its negation. A very common example where this is illustrated:

Example 4

Prove that the number $\sqrt{2}$ is irrational.

✓Solution

We proceed by contradiction. Assume that $\sqrt{2}$ is a rational number, i.e., it can be written as a fraction $\frac pq$ in simplest form (numbers $p, q$ are coprime). After squaring and multiplying by the denominator, we get $p^2=2q^2$ .

The right side is divisible by two, so $p^2$ and subsequently $p$ must also be even, i.e., $p=2k$ . By substituting, we have $(2k)^2=2q^2$ , which simplifies to $2k^2=q^2$ . Now we see that $q$ must also be even. The numbers $p$ and $q$ are thus both divisible by two, which is a contradiction with the assumption that they are coprime.

Exercise 3

This proof would not pass if we had $\sqrt{4}$ . Where would it fail?

✓Solution

It would fail in the step where we try to show that $q$ is also divisible. We would have the equation $p^2=4q^2$ , from which it follows that $p$ is even, i.e., $p=2k$ . However, by substituting, we get $4k^2=4q^2$ , which after canceling simplifies to $k^2=q^2$ . From this equality, it does not follow that $q$ is even (nor divisible by 4). Thus, we do not get a contradiction with the coprimality of $p, q$ .

Exercise 4

Prove the generalization of the statement about the irrationality of $\sqrt{2}$ : Let $n$ be a natural number. The number $\sqrt{n}$ is irrational if and only if there exists a prime number $p$ which appears in the prime factorization of $n$ with an odd power.

✓Solution

We proceed by contradiction. Let $\sqrt{n} = \frac ab$ for coprime $a, b$ . We rearrange the equation to $nb^2 = a^2$ . In the prime factorization of a square ( $a^2$ and $b^2$ ), every prime number has an even exponent. On the left side, the exponent of any prime number is the sum of its exponent in $n$ and in $b^2$ . For equality to hold, this sum must be even, which means that the exponent of every prime number in $n$ must be even. Thus, if $n$ contains a prime number with an odd power, we get a contradiction. Conversely, if all exponents are even, $n$ is a square and $\sqrt{n}$ is a rational number.

Problem 3

Prove that the sum of a rational and an irrational number is an irrational number.

1Hint

We proceed by contradiction. What if for rational $r_1,r_2$ and irrational $r'$ it holds that $r_1+r'=r_2$ ?

✓Solution

We proceed by contradiction. Let $r_1$ be rational and $r'$ be an irrational number. Assume that their sum $r_2 = r_1 + r'$ is rational. Then we can express $r' = r_2 - r_1$ . Since the difference of two rational numbers is always a rational number, $r'$ must also be rational. However, this is a contradiction with the assumption that $r'$ is irrational.

Problem 4

Prove that the number $\sqrt{2}+\sqrt{3}$ is irrational.

1Hint

We proceed by contradiction. Let $\sqrt{2}+\sqrt{3}=r$ . We need to get rid of the roots.

2Hint

The key to getting rid of the roots is squaring. By squaring the equality from the previous hint, we will have one root instead of two.

✓Solution

We proceed by contradiction. Let $r = \sqrt{2}+\sqrt{3}$ be a rational number. By squaring the equality, we get $r^2 = 5 + 2\sqrt{6}$ , from which we express $\sqrt{6} = \frac{r^2-5}{2}$ . Since $r$ is rational, the right side is also rational. This would mean that $\sqrt{6}$ is a rational number, which is a contradiction (the proof is analogous to that for $\sqrt{2}$ ).

Note. A typically erroneous proof might consist of the argument that the sum of two irrational numbers is always irrational. Convince yourself, however, that this is not true.

The following examples show that proof by contradiction is technically used even when we are proving that something does not hold.

Problem 5

Prove that the sum of three squares of odd integers is never a square of an integer.

1Hint

The key is to look at divisibility by eight.

2Hint

Recall the statement proved in the section on direct proof, that the squares of odd numbers leave a remainder of 1 when divided by 8.

✓Solution

According to the previously proven statement, the square of an odd number leaves a remainder of 1 when divided by 8. The sum of three such numbers therefore leaves a remainder of 3. But then it cannot be a square, since that would have to be odd and, again according to our statement, leave a remainder of 1.

Problem 6

73-CSMO-B-II-1

Patrik chose two distinct positive integers $a$ , $b$ , wrote each on 10 cards and placed all 20 cards around the circumference of a circle. He noticed that each number is now a divisor of the sum of the two numbers on the adjacent cards. Prove that the numbers on the cards alternate.

1Hint

We are proving that something cannot happen – what would it mean if it potentially could, i.e., if the numbers did not alternate? What is actually the negation of this statement?

2Hint

If the numbers did not alternate, then some two identical numbers are next to each other, e.g. $aa$ . If we now walk along the circle in some direction, e.g. to the right, we must eventually reach $b$ , so we have $aab$ . What do we get from this?

3Hint

The triple $aab$ gives us $a \mid a+b$ , so $a \mid b$ . It would be great to find something similar somewhere else.

4Hint

To obtain $b \mid a$ , we need to find a triple $bba$ . Why must there also be $bb$ on the circle? Think about the number of alternating groups: if you merge two $a$ 's into one group, you reduce the number of available groups for $b$ . Where must all the $b$ 's fit then?

5Hint

If from the triple $aab$ we find that $a \mid b$ , and from the triple $bba$ we find that $b \mid a$ , what conclusion follows for two positive integers $a, b$ ?

✓Solution

We prove the claim by contradiction. Suppose that the numbers $a$ , $b$ are not placed in alternating fashion. This clearly means that there are two adjacent $a$ 's and simultaneously two adjacent $b$ 's somewhere on the circle†. Pick two adjacent $a$ 's. If we start from this pair $aa$ and travel around the circle in one direction, we will encounter a $b$ (otherwise the circle would contain only $a$ 's). Once this happens, we will have an adjacent triple $aab$ . According to the problem statement, $a \mid a+b$ holds, from which $a \mid b$ . By an analogous argument, we find a triple $bba$ , from which we get $b \mid a$ . For positive integers $a$ , $b$ we thus have $a \mid b$ and $b \mid a$ , and therefore $a = b$ , which contradicts the fact that $a$ , $b$ are distinct. This completes the solution.

Note 1. Without loss of generality, we could have assumed from the start of the proof by contradiction that, say, $a < b$ . Then we would only need the argument about the triple $bba$ leading to the contradictory conclusion $b \mid a$ .

Note 2. Let us additionally show that for numbers $a$ , $b$ satisfying the problem statement, either $b = 2a$ or $a = 2b$ must hold. By symmetry, it suffices to prove $b = 2a$ in the case $a < b$ . With alternating placement, from the triple $aba$ we have $b \mid 2a$ , so $2a = kb$ for a suitable positive integer $k$ . From the assumption $a < b$ , however, $kb = 2a < 2b$ follows, from which $k < 2$ , i.e., $k = 1$ , and therefore $2a = kb = b$ , as we wanted to prove.

Finally, we will show perhaps the most famous proof of this widely known fact, which Euclid† was already able to prove.

Theorem 2

Prove that there are infinitely many prime numbers.

Proof

We proceed by contradiction. Assume that there are finitely many prime numbers $p_1, p_2, \dots, p_n$ . Consider the number $N = p_1 \cdot p_2 \cdots p_n + 1$ . This number is greater than 1, so it must have at least one prime divisor $p$ . This divisor $p$ must be one of our prime numbers $p_1, \dots, p_n$ . At the same time, however, $N$ leaves a remainder of 1 when divided by any $p_i$ , so no $p_i$ divides it. This is a contradiction, so there must be infinitely many prime numbers.

Try to solve the next two problems in a similar way:

Problem 7^*

Prove that there are infinitely many prime numbers $p$ that divide $n^2+1$ for a suitable natural $n$ .

1Hint

We go by contradiction. If there were finitely many of them, denote them $p_1,p_2,\dots,p_k$ . Try to construct a suitable expression.

2Hint

Think about the expression $(p_1\cdot p_2 \cdots p_k)^2+1$ .

✓Solution

Assume that there are finitely many such prime numbers, denote them $p_1, p_2, \dots, p_k$ . Consider the number

N = (p_1 \cdot p_2 \cdots p_k)^2 + 1.

This number is greater than 1, therefore it has some prime divisor $q$ . Since $q$ divides $N$ , it divides a number of the form $n^2+1$ , so $q$ must belong to our list $p_1, \dots, p_k$ . But this means that $q$ divides the product $p_1 \cdots p_k$ , and thus also divides its square. From this, it follows that $q$ divides the difference $N - (p_1 \cdots p_k)^2 = 1$ , which is a contradiction.

Problem 8^**

Prove that there are infinitely many prime numbers of the form $3n+2$ , where $n$ is a natural number.

1Hint

We proceed as in the previous cases, we label the primes, we construct a suitable expression. However, one must pay attention to the special prime number 2 (which is also of our form).

2Hint

Think about the expression $3p_1\cdots p_k+2$ , where $p_1,\dots,p_k$ are odd prime numbers of the form $3n+2$ .

3Hint

The key is to find some other prime number of the form $3n+2$ in the prime factorization of our expression. Could there be none in this factorization, and what would that mean?

✓Solution

Assume that there are finitely many prime numbers of the form $3n+2$ . Let $p_1, \dots, p_k$ denote all odd prime numbers of this form (we omit the number 2). Consider the number

N = 3p_1 \cdots p_k + 2.

Since $p_i$ are odd, $N$ is the sum of an odd number and the number 2, so $N$ is odd and is not divisible by 2. At the same time, $N$ leaves a remainder of 2 when divided by three. Therefore, $N$ must have at least one prime divisor $q$ of the form $3n+2$ (if all divisors were of the form $3n+1$ , $N$ would also have this form). Since $N$ is odd, $q \neq 2$ . At the same time, $q$ cannot be any of the $p_i$ , because otherwise it would divide $N$ as well as $3p_1 \cdots p_k$ , and thus also their difference 2. We have thus found a new prime number $q$ of the form $3n+2$ , which is a contradiction.

At the end of the section, let's return to the promised explanation of the proof by contrapositive. In general, this is a proof of the implication $A \Rightarrow B$ , which is equivalent to the implication $B' \Rightarrow A'$ , for example, the implication if $5$ does not divide $n$ , then $25$ does not divide $n$ either is equivalent to the implication if $25$ divides $n$ , then $5$ divides $n$ . We are therefore trying to prove the negation of assumption $A$ from the negation of statement $B$ – technically, we are trying to come to a specific contradiction from the assumption that $B$ does not hold, namely with assumption $A$ . From this, it can be seen that such a proof is actually a special case of proof by contradiction – in which our goal is to come to a contradiction with any statement, not necessarily an assumption.

3What we have learned

We use direct proof when we try to derive as many things as possible from the assumptions.
Proof by contradiction is useful when something can be derived from the negation of the statement to be proved; from the negation we then use direct derivation.
Proof by contrapositive is actually a special case of proof by contradiction.

4What next

In the next materials, we will focus on specific proof techniques, starting with mathematical induction, which is so important that it deserves a separate material.

Comments

Proof Basics

Proofs

Author

Patrik Bak

1Introduction

2Basic Types of Proofs

In general, we distinguish two basic types of proofs: direct proof and proof by contradiction. In short:

Direct proof: We derive the statement to be proved from valid statements.
Proof by contradiction: We assume that the statement to be proved does not hold and try to derive a mathematically invalid statement, to reach a contradiction.

A direct proof works by gradually adding new and new statements to the soup until we add the one we aim to prove.
On the other hand, in a proof by contradiction, we add the negation of the statement to be proved to the soup and proceed as if we were proving directly. We add new statements until the soup curdles and we get some nonsense, such as $0=1$ , or the opposite of one of the assumptions.

In the following two sections, we will show specific interesting examples of proofs. But first, two notes:

A very important technique is proof by mathematical induction. Strictly speaking, this is not so much a type of proof as it is a recipe for adding new valid statements to the soup.
In school, a distinction is usually made between two types of indirect proofs: indirect proof by contradiction and proof by contrapositive. We will explain that the latter is actually a special case of proof by contradiction.

2.1Direct Proof

Example 1

Prove that the squares of odd numbers leave a remainder of 1 when divided by 8.

✓Solution

First, let's take this complete written proof:

Before we go further, let's realize the structure of that proof. It consists of these statements:

$V_0$ : $m$ is an odd integer
$V_1$ : $m=2n+1$ for some integer $n$
$V_2$ : $n$ is an integer, thus $n$ is even or $n+1$ is even
$V_3$ : $n(n+1)$ is even
$V_4$ : $4n(n+1)$ is divisible by 8
$V_5$ : $4n(n+1)+1$ leaves a remainder of 1 when divided by 8
$V_6$ : $(2n+1)^2$ leaves a remainder of 1 when divided by 8
$V_7$ : $m^2$ leaves a remainder of 1 when divided by 8

The proof consists of the transitions $V_0 \Rightarrow V_1$ and $V_2 \Rightarrow V_3 \Rightarrow V_4 \Rightarrow V_5 \Rightarrow V_6$ . By combining $V_1$ and $V_6$ we get $V_7$ .

Exercise 1

Prove that for prime numbers $p \ge 5$ , it holds that $p^2-1$ is a number divisible by 24.

✓Solution

p^2-1 = (3k \pm 1)^2 - 1 = 9k^2 \pm 6k = 3(3k^2 \pm 2k),

which is clearly divisible by three.

In harder problems, it may not be immediately obvious how to use the assumptions from the problem statement and it is necessary to analyze the situation.

Example 2

Prove that if a natural number $n$ is the square of an integer, then it has an odd number of divisors.

✓Solution

The previous example can also be solved using the generally useful formula for the number of divisors:

Theorem 1

Let $n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ , where $p_1,p_2,\dots,p_k$ are distinct prime numbers and $a_1,a_2,\dots,a_k$ are integers. Then the number $n$ has exactly

(a_1+1)(a_2+1)\cdots (a_k+1)

divisors.

Proof

(a_1+1)(a_2+1)\cdots (a_k+1).

Exercise 2

✓Solution

Problem 1

Given a composite number $n > 1$ . Prove that it is divisible by a prime number not exceeding $\sqrt{n}$ .

1Hint

The number $n$ is composite, let's write it as $ab$ , where $1<a \leq b<n$ .

2Hint

✓Solution

Problem 2^*

A natural number $n$ has exactly $k$ divisors. Prove that the product of the divisors of $n$ is equal to $\sqrt{n^k}$ .

1Hint

Use the trick with the paired divisor again.

2Hint

Distinguish the cases where $n$ is and is not a square.

✓Solution

In the solution, we will consider the pairing of divisors: $d$ is a divisor of $n$ if and only if $n/d$ is a divisor of $n$ . The product of such divisors is $n$ .

Let's analyze two cases:

If $n$ is not a square, then for every divisor $d \neq n/d$ holds (otherwise $d^2=n$ ). All $k$ divisors thus form exactly $k/2$ such pairs. The total product is $n^{k/2} = \sqrt{n^k}$ .
If $n$ is a square, then $d=\sqrt{n}$ forms a pair with itself. The remaining $k-1$ divisors form $(k-1)/2$ pairs with product $n$ . The total product is therefore $n^{\frac{k-1}2} \cdot \sqrt{n} = n^{\frac{k}2 - \frac12 + \frac12} = \sqrt{n^k}.$

Example 3

When does $a \mid b$ and $b \mid a$ hold for integers $a,b$ ?

✓Solution

If $ab=0$ , i.e., if for example $a=0$ , then the relation $b=au$ gives $b=0$ . Then both relations mean $0 \mid 0$ , which is fine† and $a=b$ holds.

The conclusion is that $a \mid b$ and $b \mid a$ if and only if $a=b$ or $a=-b$ , and for non-negative numbers even directly $a=b$ .

2.2Proof by Contradiction

Example 4

Prove that the number $\sqrt{2}$ is irrational.

✓Solution

Exercise 3

This proof would not pass if we had $\sqrt{4}$ . Where would it fail?

✓Solution

Exercise 4

✓Solution

Problem 3

Prove that the sum of a rational and an irrational number is an irrational number.

1Hint

We proceed by contradiction. What if for rational $r_1,r_2$ and irrational $r'$ it holds that $r_1+r'=r_2$ ?

✓Solution

Problem 4

Prove that the number $\sqrt{2}+\sqrt{3}$ is irrational.

1Hint

We proceed by contradiction. Let $\sqrt{2}+\sqrt{3}=r$ . We need to get rid of the roots.

2Hint

The key to getting rid of the roots is squaring. By squaring the equality from the previous hint, we will have one root instead of two.

✓Solution

Note. A typically erroneous proof might consist of the argument that the sum of two irrational numbers is always irrational. Convince yourself, however, that this is not true.

The following examples show that proof by contradiction is technically used even when we are proving that something does not hold.

Problem 5

Prove that the sum of three squares of odd integers is never a square of an integer.

1Hint

The key is to look at divisibility by eight.

2Hint

Recall the statement proved in the section on direct proof, that the squares of odd numbers leave a remainder of 1 when divided by 8.

✓Solution

Problem 6

73-CSMO-B-II-1

1Hint

We are proving that something cannot happen – what would it mean if it potentially could, i.e., if the numbers did not alternate? What is actually the negation of this statement?

2Hint

3Hint

The triple $aab$ gives us $a \mid a+b$ , so $a \mid b$ . It would be great to find something similar somewhere else.

4Hint

5Hint

If from the triple $aab$ we find that $a \mid b$ , and from the triple $bba$ we find that $b \mid a$ , what conclusion follows for two positive integers $a, b$ ?

✓Solution

Finally, we will show perhaps the most famous proof of this widely known fact, which Euclid† was already able to prove.

Theorem 2

Prove that there are infinitely many prime numbers.

Proof

Try to solve the next two problems in a similar way:

Problem 7^*

Prove that there are infinitely many prime numbers $p$ that divide $n^2+1$ for a suitable natural $n$ .

1Hint

We go by contradiction. If there were finitely many of them, denote them $p_1,p_2,\dots,p_k$ . Try to construct a suitable expression.

2Hint

Think about the expression $(p_1\cdot p_2 \cdots p_k)^2+1$ .

✓Solution

Assume that there are finitely many such prime numbers, denote them $p_1, p_2, \dots, p_k$ . Consider the number

N = (p_1 \cdot p_2 \cdots p_k)^2 + 1.

Problem 8^**

Prove that there are infinitely many prime numbers of the form $3n+2$ , where $n$ is a natural number.

1Hint

We proceed as in the previous cases, we label the primes, we construct a suitable expression. However, one must pay attention to the special prime number 2 (which is also of our form).

2Hint

Think about the expression $3p_1\cdots p_k+2$ , where $p_1,\dots,p_k$ are odd prime numbers of the form $3n+2$ .

3Hint

The key is to find some other prime number of the form $3n+2$ in the prime factorization of our expression. Could there be none in this factorization, and what would that mean?

✓Solution

Assume that there are finitely many prime numbers of the form $3n+2$ . Let $p_1, \dots, p_k$ denote all odd prime numbers of this form (we omit the number 2). Consider the number

N = 3p_1 \cdots p_k + 2.

3What we have learned

We use direct proof when we try to derive as many things as possible from the assumptions.
Proof by contradiction is useful when something can be derived from the negation of the statement to be proved; from the negation we then use direct derivation.
Proof by contrapositive is actually a special case of proof by contradiction.

4What next

In the next materials, we will focus on specific proof techniques, starting with mathematical induction, which is so important that it deserves a separate material.