Exercises - Arguing by Contradiction

    As needed in the problems below, you may assume that for any prime $p$,
    if $p \mid nm$, then $p \mid n$ or $p \mid m$.

  1. Prove that there are infinitely many prime numbers.

  2. There appear to be a great many pairs of consecutive odd primes -- for example: $3$ & $5$; $5$ & $7$; $11$ & $13$; $17$ & $19$; $29$ & $31$; and so on... These pairs of primes that take the form $p$ and $p+2$ are called "twin primes", and a very famous unsolved problem in mathematics is whether one can prove that there are actually infinitely many twin prime pairs. Note that the consecutive odd numbers 3, 5, and 7 are all primes. Are there infinitely many such "prime triplets"? That is to say, are there infinitely many prime numbers $p$ so that $p+2$ and $p+4$ are also primes? Prove your conclusion.

  3. Prove that if $a$ is a rational number and $b$ is an irrational number, then $a+b$ is an irrational number.

  4. Prove that $\sqrt[3]{2}$ is irrational.

  5. Prove that $\sqrt{2}+\sqrt{5}$ is irrational.

  6. Prove that $\sqrt{2} + \sqrt{3} + \sqrt{5}$ is irrational.

  7. Prove that $\sqrt{2} \cdot \sqrt{3}$ is irrational.

  8. Prove that $\displaystyle{\frac{\sqrt{2}}{\sqrt{3}}}$ is irrational.

  9. Prove that in any group of $n \ge 2$ people, there are at least two who are acquainted with the same number of people.

  10. Prove that for positive values of $a,b,c$: if $a^2,b^2,c^2$ are the sides of a triangle, then there exists a triangle with sides $a,b,c$. (Hint: You may find it helpful to recall that three segments can only form a triangle if the sum of the lengths of any two of them is larger than the length of the remaining segment.)

  11. In each square of a checkered $5 \times 5$ board there is a bug. At a certain moment of time each bug moves to an adjacent square (the bug does not move diagonally). Prove that after the bugs move, there is more than one bug in one of the squares. (Hint: What can you say about the bugs on the white squares? ... or those on the black squares?)

  12. Prove that in any group of 7 people there is a person who knows an even number of people. You may assume that if a person $A$ "knows" a person $B$, then person $B$ also "knows" person $A$. (Hint: If for each person you count the number of acquaintances, what can you say about their total?)

  13. Prove that there are infinitely many prime numbers of the form $4k+3$. (Hint: What property do some prime divisors of $4k+3$ must have?)

  14. A king visited all squares of the usual $8 \times 8$ chessboard exactly once starting from the lower left square and finishing at the upper right square. Prove that the king made at least one diagonal move. (Hint: the squares of the chessboard are colored.)

    1. ◆ ◆ ◆