Preuve par contradiction

Exemple 1 : Preuve de l'existence d'une infinité de nombres premiers

Prouve par la contradiction qu'il existe une infinité de nombres premiers.

Solution :

La première étape consiste à supposer que l'affirmation est fausse, que le nombre de nombres premiers est fini. Disons qu'il n'y a que n nombres premiers et qu'ils sont classés de _p1 à _pn.

S'il existe une infinité de nombres premiers, alors tout nombre devrait être divisible par au moins un de ces nombres.

Construis P, où nous multiplions tous les nombres premiers ensemble et ajoutons 1, voir ci-dessus \(P = p_1p_2 ... p_n +1\). Nous constatons alors qu'aucun nombre premier ne divise ce nombre, car chacun des nombres premiers divise P-1, et pour qu'un nombre divise à la fois P et P-1, la seule possibilité est un nombre qui n'est pas premier. Cela signifie que P est un nombre premier, et comme \(P > p_i \text{ for all } p_i\), cela signifie qu'il y a un nouveau nombre premier, ce qui signifie que nous avons maintenant une contradiction. Cela signifie qu'il doit y avoir un nombre infini de nombres premiers. QED

Exemple 2 : Preuve que 2 est irrationnel

Prouve par contradiction que \(\sqrt{2}\) est irrationnel.

Solution :

Supposons que \(\sqrt{2}\) est rationnel. Cela signifie que nous pouvons écrire \(\sqrt{2} = \frac{a}{b}\), avec \(a, b \dans \mathbb{Z}, b ≠ 0, pgcd (a, b) = 1\). (Remarque - pgcd signifie plus grand diviseur commun). Cela signifie que \(\frac{a}{b}\) est une fraction dans ses termes les plus faibles. Note ici que cela signifie que a et b ne peuvent pas être tous les deux pairs, car nous pourrions alors annuler un facteur 2.

Si \(\sqrt2 = \frac{a}{b}\), alors \(2 = \frac{a^2}{b^2}\), qui se réarrange en \(a^2 = 2b^2\). Cela signifie que a² est pair, ce qui implique que a est également pair.

(Cette affirmation est facile à vérifier. Si un nombre est pair, nous pouvons l'écrire sous la forme de 2k, k étant un entier. Ce nombre au carré est égal à 4k², qui est également pair. Si un nombre est impair, on peut l'écrire sous la forme \(2k + 1. (2k + 1)^2 = 4k^2 + 4k + 1 = 2 (2k^2 + 2k) +1\), ce qui est impair. Ainsi, si a² est pair, alors a doit l'être aussi).

Cela signifie que nous pouvons remplacer a par 2c, puisque a doit être pair. La valeur de c n'a pas d'importance, mais elle doit être un nombre entier.

Alors, si \(a^2 = 2b^2\), nous avons \(4c^2 = 2b^2 \Rightarrow b^2 = 2c^2\). En suivant le même argument que ci-dessus, cela signifie que b² est pair, et qu'à son tour, b est pair. Nous pouvons donc écrire \(b = 2d, d dans \mathbb{z}\). Cela signifie que pgcd (a, b) = pgcd (2c, 2d) ≠ 1. (Comme le pgcd sera un minimum de 2). Cela signifie qu'il n'y aura pas de fraction dans ses termes les plus faibles, et donc une contradiction.

Nous pouvons maintenant conclure que \(\sqrt2\) est irrationnel. QED

Exemple 3 :

Prouve qu'il n'existe pas d'entiers a et b tels que

\N(10a + 15b = 1\N).

Solution :

Supposons que nous puissions trouver des entiers a et b qui satisfont une telle équation. Nous pouvons alors diviser les deux côtés par 5 pour obtenir \(2a + 3b = \frac{1}{5}\). Si a et b sont des entiers, et que nous les multiplions chacun par un autre entier (2 et 3 respectivement, dans ce cas), puis que nous les additionnons, il n'y a aucune possibilité que le résultat soit une fraction, ce qui est ce que la condition ci-dessus exige. Cela nous amène à une contradiction.

Il n'existe donc pas d'entiers a et b tels que \N(10a + 15b = 1\N).

Exemple 4 :

Utilise la preuve par la contradiction pour montrer que la somme d'un nombre rationnel et d'un nombre irrationnel est irrationnelle.

Solution :

Supposons que la somme d'un nombre rationnel et d'un nombre irrationnel est rationnelle. Soit le nombre rationnel noté a, et le nombre irrationnel noté b, et leur somme est notée a + b. Comme a est rationnel, nous pouvons l'écrire sous la forme \(a = \frac{c}{d}\), où d ≠ 0, et d et c des nombres entiers, dans les termes les plus faibles possibles. Comme a + b est rationnel, nous pouvons écrire \(a + b = \frac{e}{f}\), e, f ∈ ℤ, f ≠ 0, et la fraction dans ses termes les plus faibles. On peut alors écrire \(\frac{c}{d} + b = \frac{e}{f}\). Ceci implique \(b= \frac{e}{f}-\frac{c}{d} = \frac{de-cf}{fd}\). Comme \(de-cf\) est un nombre entier, et que fd est également un nombre entier, cela implique que b pourrait s'écrire comme un nombre rationnel, ce qui est une contradiction. Ainsi, la somme d'un nombre rationnel et d'un nombre irrationnel est irrationnelle.