Skip to content

10.23 Proof

Workshop 2.pdf

Exercise 1

Recall that \(\sqrt{2}\) is an irrational number.

  1. Prove that if \(a\) and \(b\) are two relative integers such that \(a + b\sqrt{2} = 0\), then \(a = b = 0\).

    Suppose \(a\neq 0 ~or~ b\neq 0\), then since \(a+\sqrt2b=0\Rightarrow a=-\sqrt2b\equiv b=-\frac{\sqrt2}{2}a\)​

    Assume \(b\in \Z\neq0\), then \(a\) has to be irrational number which is a contradiction

    Assume \(a\in \Z\neq0\), then \(b\) has to be irrational number which is a contradiction

    Thus \(a=b=0\)​

  2. Deduce that if \(m, n, p\), and \(q\) are relative integers, then:
    ​\(m + n\sqrt{2} = p + q\sqrt{2} \iff (m = p \text{ and } n = q)\).

    \(m+n\sqrt2=p+q\sqrt2\;\;\iff\;\;\left(m-p\right)+\sqrt2\left(n-q\right)=0\)​

    \(\Rightarrow\)) Since the first question we know \(m-p=n-q=0\) which is \(m=p\) and \(n=q\)

    \(\Leftarrow\)) Since \(m=p\) and \(n=q\), then \(m-p=0\) and \(n-q=0\)​

    Then \(\sqrt{2}(n-q)=0\), then \(\left(m-p\right)+\sqrt2\left(n-q\right)=0\;\iff\;m+n\sqrt2=p+q\sqrt2\;\;\)​

Exercise 2

Prove that if you store \((n+1)\) pairs of socks in \(n\) separate drawers, then there is at least one drawer containing at least 2 pairs of socks.

Suppose there is no one drawer containing more than 1 pair of socks

Thus the number of drawer \(\geq\) the number of socks.

Which is \(n\geq n+1\Rightarrow 0\geq 1\) ,Contradiction!

Exercise 3

Let \(n \geq 1\) be a natural integer. We are given \(n+1\) real numbers \(x_0, x_1, \dots, x_n\) of \([0, 1]\) verifying \(0 \leq x_0 \leq x_1 \leq \dots \leq x_n \leq 1\). We want to demonstrate by contradiction the following property: there are two of these real numbers whose distance is less than or equal to \(1/n\).

  1. Write using quantifiers and the values \(x_i - x_{i-1}\) a logical formula equivalent to the property.

    \(\exists i\)​, \(x_i-x_{i-1}\leq \frac1n\)

  2. Write the negation of this logical formula.

    \(\forall i\), \(x_{i}-x_{i-1}>\frac{1}{n}\)​

  3. Write a proof by contradiction of the property (we can show that \(x_n - x_0 > 1\)).

    Since \(\forall i\), \(x_{i}-x_{i-1}>\frac{1}{n}\), then \(\begin{cases}x_1-x_0>\frac{1}{n}\\ x_2-x_1>\frac{1}{n}\\ x_3-x_2>\frac{1}{n}\\ \ldots\\ x_{n-1}-x_{n-2}>\frac{1}{n}\\ x_{n}-x_{n-1}>\frac{1}{n}\end{cases}\)​

    We can add them together and get \(x_n-x_0>1\), which is a contradiction

  4. Give a proof using the drawer principle.

    Let plan \(n\) intervals, each interval is \(\frac1n\). And we have \(n+1\) elements.

    By drawer principle, at least two elements are in the same interval and thus their distance is less or equal than \(\frac1n\)

    ‍

Exercise 4

Let \(a \in \mathbb{R}\). Show that:
\(\forall \epsilon > 0, \ |a| \leq \epsilon \implies a = 0\).

Suppose \(a\neq 0\), then \(-\varepsilon\leq a\leq \varepsilon\).

Since \(\varepsilon\) is arbitrary, thus we take \(\varepsilon=\frac a2\), then \(-\frac a2\leq a\leq\frac a2\Rightarrow-a\leq 2a\leq a\)

Then we get \(a\geq 0\) and \(a\leq 0\) which means \(a=0\)

Contradiction!

Exercise 5

Let \(a\) and \(b\) be two real numbers. Consider the following proposition: if \(a + b\) is irrational, then \(a\) or \(b\) are irrational.

  1. What is the contrapositive of this proposition?

    If \(a\) and \(b\) are rational, then \(a+b\) is rational

  2. Prove the proposition.

    Let \(a=\frac mn,b=\frac pq\) (\(m,n,p,q\in\mathbb{Z}\))

    Then \(a+b=\frac{mq+np}{nq}\)​

    Since \(m,n,p,q\in\mathbb{Z}\), then \(mq+np\in\Z\) and \(nq\in \Z\)​

    Thus \(a+b\in Q\)​

  3. Is the converse of this proposition always true?

    if \(a\) or \(b\) are irrational, then \(a + b\) is irrational.

    No!! Since \(a=\sqrt2,b=-\sqrt2\).

Exercise 6

Show that, for any relative integer \(n\), \(n(n - 5)(n + 5)\) is divisible by 3.

Use induction

Basic step: \(n=1\), \(1\cdot (-4)\cdot 6=-24\) \(\checkmark\)

Inductive step: Suppose it is true for \(n\), which is \(3\mid n(n-5)(n+5)\Rightarrow3m=n\left(n-5\right)\left(n+5\right)=n^3-25n\)

Then N.T.P. \(3k=\left(n+1\right)(n-4)(n+6)\)

\(\left(n+1\right)(n-4)(n+6)=n^3+3n^2-22n-24=n^3-25n+3n^2+3n-24=n^3-25n+3\left(n^2+n-8\right)=3\left(m+n^2+n-8\right)\)

True

Exercise 7

The goal of the exercise is to demonstrate that the product of two integers that are not divisible by 3 is not divisible by 3.

  1. Let \(n\) be an integer. What are the possible remainders in the Euclidean division of \(n\) by 3?

    \(0,1,2\)​

  2. Deduce that if \(n\) is not divisible by 3, then \(n\) is written as \(3k + 1\) or \(3k + 2\), with \(k\) an integer. Is the converse true?

    The converse: If \(n\) is written as \(3k + 1\) or \(3k + 2\), then \(n\) is not divisible by 3.

    Yes

  3. Let \(n\) be an integer written as \(3k + 1\) and \(m\) be an integer written as \(3l + 1\). Verify that:
    ​\(n \times m = 3(3kl + k + l) + 1\).

    \(n\times m=(3k+1)(3l+1)=9kl+3k+3l+1=3(3kl+k+l)+1\)​

    Deduce that \(n \times m\) is not divisible by 3.

    Since \(3kl+k+l=t\in\mathbb{Z}\), then \(3t+1\) is not divisible by \(3\)​

  4. Demonstrate the property announced by the exercise.

    The product of two integers that are not divisible by 3 is not divisible by 3.

Exercise 8

Determine the real numbers \(x\) such that \(\sqrt{2} - x = x\).

\(x=\frac{\sqrt2}{2}\)​

Exercise 9

In this exercise, we want to determine all functions \(f: \mathbb{R} \to \mathbb{R}\) verifying the following relation:

\(\forall x \in \mathbb{R}, \ f(x) + x f(1 - x) = 1 + x\).

  1. Consider \(f\) a function satisfying the previous relation. What is the value of \(f(0)\)? \(f(1)\)?

    Let \(x=1\), \(f(1)+f(0)=2\) and let \(x=0\), \(f(0)=1\)​

    Then \(f(1)=1\)​

  2. Let \(x \in \mathbb{R}\). Substituting \(x\) by \(1 - x\) in the relation, determine \(f(x)\).

    \(f(1-x)+(1-x)f(x)=2-x\)​

    \(\begin{cases}f(x)+xf(1-x)=1+x\\ xf(1-x)+x(1-x)f(x)=2x-x^2\end{cases}\)

    \(2-1\): \(x(1-x)f(x)-f(x)=2x-x^2-1-x\)

    Then \((-1+x-x^2)f(x)=-x^2+x-1\Rightarrow f(x)=1\) since \(1-x+x^2\neq 0\)

  3. What are the functions \(f\) that solve the problem?

    \(f(x)=1,\forall x\in \R\)

Exercise 10

Let \(f: \mathbb{R} \to \mathbb{R}\). Show that \(f\) can be uniquely written as the sum of an even function and the sum of an odd function.

Analysis: We need to express \(f(x)\) in another way, so the intuition is to define some equation contained \(f(x)\) and also can be even or odd function

\(f(x)=f(x)_{even}+f(x)_{odd}\)

\(f(x)_{even}=f(-x)_{even}\Rightarrow\frac{f\left(x\right)+f\left(-x\right)}{2}=\frac{f\left(-x\right)+f\left(x\right)}{2}\)​

\(f(x)_{odd}=-f(-x)_{odd}\Rightarrow\frac{f\left(x\right)-f\left(-x\right)}{2}=-\frac{f\left(-x\right)+f\left(x\right)}{2}\)

Then \(f(x)=\frac{f\left(x\right)+f\left(-x\right)}{2}+\frac{f\left(x\right)-f\left(-x\right)}{2}=f\left(x\right)\)

Then we prove uniqueness

Suppose there is another way to compose it, then the even function is \(g(x)_{even}\) and the odd function is \(g(x)_{odd}\)

Then \(f(x)_{even}+f(x)_{odd}=g(x)_{even}+g(x)_{odd}\Rightarrow f(x)_{even}-g(x)_{even}=g(x)_{odd}-f(x)_{odd}\)

The left hand is an even function and the right hand is an odd function.

The the only possibility is that they are all \(0\), which means \(f(x)_{even}=g(x)_{even}\) and \(g(x)_{odd}=f(x)_{odd}\)​

Exercise 11 (⋆)

Let \(a\) and \(n \geq 2\) be two integers. Prove the following assertions.

  1. If \(a^n - 1\) is prime, then \(a = 2\) and \(n\) is prime.

    Remark: \(x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+\cdots+x+1)\)

    \(x^n+1=(x+1)(x^{n−1}−x^{n−2}+x^{n−3}−\cdots−x+1)\) only when \(n\) is odd

    Since \(a^{n}-1=(a-1)(a^{n-1}+a^{n-2}+\cdots+a+1)\) is a prime, then \(a=2\) and \(a^{n}-1\) is a prime

    Then \(2^{n}-1\) must be a prime and need to prove \(n\) is prime

    Suppose \(n\) is not prime \(\Rightarrow n=mk~(m,n\geq 2)\), then \(2^{n}-1=2^{mk}-1=\left(2^{m}-1\right)\left(\left(2^{m}\right)^{k-1}+\left(2^{m}\right)^{k-2}+\cdots+2^{m}+1\right)\)​

    Since \(2^m-1\geq 3\) and \(\left(2^{m}\right)^{k-1}+\left(2^{m}\right)^{k-2}+\cdots+2^{m}+1>1\), then \(2^n-1\) must be not prime

    Contradiction!

  2. If \(a^n + 1\) is prime, where \(a \geq 2\), then \(n\) is even.

    Suppose \(n\) is odd, then \(a^{n}+1=(a+1)(a^{n−1}−a^{n−2}+a^{n−3}−\cdots−a+1)\)​

    Then \(a+1\geq 3\) and since \(a^{n-1}>a^{n-2},a^{n-3}>a^{n-4},...,a^{2}>a,1>0\), then \(a^{n−1}−a^{n−2}+a^{n−3}−\cdots−a+1>1\)​

    Thus \(a^n+1\) is not a prime.

    Contradiction!

  3. If \(a^n + 1\) is prime, where \(a \geq 2\), then \(a\) is even and \(n\) is a power of 2.

    Since \(n\) is even, then \(n=2m\Rightarrow a^{2m}+1\) is prime.

    1. \(a\) is even

      Suppose \(a=2k+1\), then \((2k+1)^{2m}+1\) is even which is a contradiction to a prime 2. \(n\) is a power of \(2\)

      Suppose \(n\) has at least one factor which is not \(2\).

      Then \(n=2^k\cdot m\) where \(m\geq 3\) and is odd

      \(a^{n}+1=a^{2^{k}\cdot m}+1=(a^{2^{k}}+1)(a^{2^{k}\cdot\left(m-1\right)}−a^{2^{k}\cdot\left(m-2\right)}+a^{2^{k}\cdot\left(m-3\right)}−\cdots−a^{2^{k}}+1)\) Then it is a contradiction obviously

Exercise 12 (⋆)

Let \(p\) be a prime number. Show that \(\sqrt{p}\) is irrational. Generalize to \(\sqrt{n}\) where \(n\) is not a perfect square.

Let \(p=\frac{m}{n}\)​

Similarly, \(m^2=pn^2\)

Since \(m^2\) must have at least one \(p\), after square, \(m^2\) can have at least evenly \(p\)

Thus \(n^2\) has the same evenly \(p\), after multiply \(p\), the right hand has oddly \(p\).

Contradiction!!

‍