Exercices corrigés — Raisonnement, ensembles & dénombrement

Une table à deux variables a $4$ lignes : $(V,V)$, $(V,F)$, $(F,V)$, $(F,F)$. Deux propositions sont équivalentes si leurs colonnes coïncident sur les quatre.

L'implication n'est fausse que sur la ligne $P$ vraie, $Q$ fausse. Cherche la ligne où $P\Rightarrow Q$ et $Q\Rightarrow P$ diffèrent.

Pour Morgan, remplis la colonne de gauche et celle de droite ligne par ligne ; nier « et » donne « ou ».

Une table de vérité est une preuve exhaustive. Une proposition composée de $P$ et $Q$ ne dépend que de leurs valeurs de vérité, et il n'y a que $2\times2=4$ façons de les fixer. Remplir les quatre lignes, c'est examiner tous les cas possibles : deux colonnes identiques prouvent une équivalence, une seule ligne différente la réfute. Il n'y a rien à « comprendre » de plus pour trancher — c'est d'ailleurs ce que le banc de ce chapitre fait mécaniquement sur chaque équivalence affirmée.

👉 Trois faits en sortent, et ce sont les trois qu'on utilise sans cesse : $P\Rightarrow Q$ est $\lnot P\lor Q$ ; sa négation est $P\land\lnot Q$ (un contre-exemple : hypothèse vraie, conclusion fausse) ; sa contraposée lui est équivalente, sa réciproque non.

$P$	$Q$	$\lnot P$	$\lnot P\lor Q$	$P\Rightarrow Q$	$\lnot(P\Rightarrow Q)$
V	V	F	V	V	F
V	F	F	F	F	V
F	V	V	V	V	F
F	F	V	V	V	F

Les colonnes de $\lnot P\lor Q$ et de $P\Rightarrow Q$ coïncident sur les quatre lignes :

$$\boxed{(P\Rightarrow Q)\iff(\lnot P\lor Q)}$$

La colonne de $\lnot(P\Rightarrow Q)$ ne porte qu'un seul V, sur la ligne $P$ vraie, $Q$ fausse — c'est exactement la colonne de $P\land\lnot Q$ (V seulement quand $P$ est V et $Q$ est F) :

$$\boxed{\lnot(P\Rightarrow Q)\iff(P\land\lnot Q)}$$

Lecture. Une implication est vraie dès que son hypothèse est fausse (lignes 3 et 4) ; on dit qu'elle est « vraie par défaut ». Et pour réfuter « pour tout $x$, $P(x)\Rightarrow Q(x)$ », il suffit d'un $x$ avec $P(x)$ vraie et $Q(x)$ fausse : un contre-exemple. « Tout nombre pair est multiple de $4$ » est réfuté par $6$.

$P$	$Q$	$P\Rightarrow Q$	$\lnot Q\Rightarrow\lnot P$	$Q\Rightarrow P$
V	V	V	V	V
V	F	F	F	V
F	V	V	V	F
F	F	V	V	V

La colonne de la contraposée $\lnot Q\Rightarrow\lnot P$ est identique à celle de $P\Rightarrow Q$ : sur la ligne 2, $\lnot Q$ est V et $\lnot P$ est F, donc l'implication est F ; sur les trois autres, $\lnot Q$ est F ou $\lnot P$ est V, donc V. D'où

$$\boxed{(P\Rightarrow Q)\iff(\lnot Q\Rightarrow\lnot P)}$$

et c'est ce qui autorise le raisonnement par contraposée : prouver $\lnot Q\Rightarrow\lnot P$, c'est prouver $P\Rightarrow Q$.

La réciproque $Q\Rightarrow P$ diffère sur deux lignes — la 2 et la 3. La valuation $P$ fausse, $Q$ vraie suffit à les séparer : $P\Rightarrow Q$ y est vraie, $Q\Rightarrow P$ y est fausse. Une implication vraie peut donc avoir une réciproque fausse, et c'est le cas courant : « $n$ multiple de $4$ $\Rightarrow$ $n$ pair » est vraie, « $n$ pair $\Rightarrow$ $n$ multiple de $4$ » est fausse ($n=6$). $\blacksquare$

⚠️ Le banc de ce chapitre contient précisément ce contre-témoin : il vérifie que son test d'équivalence refuse « $Q\Rightarrow P$ équivaut à $P\Rightarrow Q$ ». Un vérificateur qui accepterait tout ne prouverait rien.

$P$	$Q$	$\lnot(P\land Q)$	$\lnot P\lor\lnot Q$	$\lnot(P\lor Q)$	$\lnot P\land\lnot Q$
V	V	F	F	F	F
V	F	V	V	F	F
F	V	V	V	F	F
F	F	V	V	V	V

Colonnes 3 et 4 identiques, colonnes 5 et 6 identiques :

$$\boxed{\lnot(P\land Q)\iff(\lnot P\lor\lnot Q)\qquad\lnot(P\lor Q)\iff(\lnot P\land\lnot Q)}$$

La négation échange « et » et « ou ». « Il est faux que $x>0$ et $y>0$ » signifie « $x\leq0$ ou $y\leq0$ » — l'un des deux au moins est négatif ou nul, et rien n'interdit que ce soient les deux. L'erreur classique est d'écrire « $x\leq0$ et $y\leq0$ », qui est la négation de « $x>0$ ou $y>0$ ». $\blacksquare$

👉 Ces deux lois ont un jumeau ensembliste ($\overline{A\cap B}=\overline A\cup\overline B$) et un jumeau quantifié (nier $\forall$ donne $\exists$) : c'est trois fois la même idée.

Définitions. $\lnot P$ est vraie quand $P$ est fausse. $P\land Q$ est vraie quand les deux le sont. $P\lor Q$ est vraie dès que l'une l'est (« ou » inclusif). $P\Rightarrow Q$ n'est fausse que si $P$ est vraie et $Q$ fausse. $P\iff Q$ est vraie quand $P$ et $Q$ ont la même valeur.

Vocabulaire de l'implication $P\Rightarrow Q$. $P$ est une condition suffisante pour $Q$ ; $Q$ est une condition nécessaire pour $P$. Contraposée : $\lnot Q\Rightarrow\lnot P$ (équivalente). Réciproque : $Q\Rightarrow P$ (indépendante). Une équivalence $P\iff Q$ est l'implication et sa réciproque : elle se prouve en deux temps.

Table à $k$ variables : $2^k$ lignes. Trois variables, huit lignes ; c'est ainsi que se vérifient les distributivités $P\land(Q\lor R)\iff(P\land Q)\lor(P\land R)$ et la transitivité $\bigl((P\Rightarrow Q)\land(Q\Rightarrow R)\bigr)\Rightarrow(P\Rightarrow R)$.

⚠️ Prendre la réciproque pour la contraposée. Les deux « renversent la flèche », mais la contraposée nie aussi les deux membres. Moyen mnémotechnique : la contraposée porte deux négations, la réciproque aucune. Démontrer $Q\Rightarrow P$ quand on voulait $P\Rightarrow Q$ ne prouve rien.

⚠️ Croire qu'une implication à hypothèse fausse est fausse. « Si $1=2$ alors $3=3$ » est vraie. Une implication ne parle que du cas où l'hypothèse est réalisée ; ailleurs, elle ne promet rien, donc elle ne ment pas.

⚠️ Nier un « et » par un « et ». La négation de « $P$ et $Q$ » est « non $P$ ou non $Q$ ». Pour dire que $(x,y)\neq(0,0)$, on écrit « $x\neq0$ ou $y\neq0$ », jamais « $x\neq0$ et $y\neq0$ » (qui exclut le point $(0,1)$).

Un $\forall\,\exists$ autorise le second objet à dépendre du premier ; un $\exists\,\forall$ exige un objet qui marche pour tous.

Bornée : $\exists M\geq0,\ \forall x,\ \lvert f(x)\rvert\leq M$. Pour nier, bascule chaque quantificateur et nie l'inégalité.

Pour $(-1)^n$, prends $\varepsilon=1$ : à tout rang $N$, un terme d'indice impair au-delà de $N$ est à distance $2$ de $1$.

Un quantificateur n'est pas un ornement : l'ordre dans lequel deux quantificateurs se suivent change le sens de la phrase. Dans « $\forall x,\ \exists y,\ \dots$ », le $y$ est choisi après $x$ et a le droit d'en dépendre ; dans « $\exists y,\ \forall x,\ \dots$ », le $y$ est choisi avant, une fois pour toutes, et doit convenir à tous les $x$. La seconde phrase est donc beaucoup plus forte que la première — elle l'implique, jamais l'inverse.

👉 Et la négation d'une phrase quantifiée suit une règle mécanique : on bascule chaque quantificateur, dans l'ordre, puis on nie le prédicat. C'est ce qui permet de démontrer qu'une chose est fausse (une fonction n'est pas bornée, une suite ne converge pas) au lieu de le sentir.

« $\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ x<y$ » est vraie. Soit $x\in\mathbb{R}$ quelconque. Posons $y=x+1$ : alors $y\in\mathbb{R}$ et $x<y$. Le $y$ dépend de $x$, ce que la phrase autorise. $\blacksquare$

« $\exists y\in\mathbb{R},\ \forall x\in\mathbb{R},\ x<y$ » est fausse. Sa négation est « $\forall y\in\mathbb{R},\ \exists x\in\mathbb{R},\ x\geq y$ », et c'est elle qu'on démontre : soit $y$ quelconque, posons $x=y$ ; alors $x\geq y$. Aucun réel ne majore tous les réels — pas même lui-même strictement. $\blacksquare$

$$\boxed{\forall x\,\exists y\ (x<y)\ \text{ vraie},\qquad\exists y\,\forall x\ (x<y)\ \text{ fausse}}$$

Ce qu'on peut permuter. Deux $\forall$ consécutifs, oui ($\forall x\,\forall y$ = $\forall y\,\forall x$) ; deux $\exists$ consécutifs, oui ; un $\forall$ et un $\exists$, non — sauf dans le sens $\exists\,\forall\Rightarrow\forall\,\exists$, qui est toujours vrai (un $y$ qui marche pour tous marche en particulier pour chaque $x$).

Définition quantifiée. $f$ est bornée signifie

$$\exists M\geq0,\ \forall x\in\mathbb{R},\ \lvert f(x)\rvert\leq M.$$

Négation — on bascule $\exists$ en $\forall$, $\forall$ en $\exists$, et on nie $\lvert f(x)\rvert\leq M$ :

$$\forall M\geq0,\ \exists x\in\mathbb{R},\ \lvert f(x)\rvert>M.$$

« Quelle que soit la barre $M$ qu'on propose, $f$ la dépasse quelque part. »

$x\mapsto x^2$ n'est pas bornée. Soit $M\geq0$ quelconque. Posons $x=M+1$ : alors $x^2=(M+1)^2\geq M+1>M$. On a exhibé un $x$ pour chaque $M$ : la négation est démontrée. $\blacksquare$

$\sin$ est bornée. Il suffit d'exhiber un $M$ : $M=1$ convient, puisque $\lvert\sin x\rvert\leq1$ pour tout réel $x$. $\blacksquare$

👉 Remarque la dissymétrie : prouver « bornée » demande un $M$ (et la preuve qu'il marche pour tous les $x$) ; prouver « non bornée » demande une réponse $x$ à chaque $M$. C'est toujours ainsi qu'on démontre un $\exists$ (on exhibe) et un $\forall$ (on prend quelconque).

Définition (chapitre sur les suites) : $u_n\to\ell$ signifie

$$\forall\varepsilon>0,\ \exists N\in\mathbb{N},\ \forall n\geq N,\ \lvert u_n-\ell\rvert<\varepsilon.$$

Négation, quantificateur par quantificateur :

$$\exists\varepsilon>0,\ \forall N\in\mathbb{N},\ \exists n\geq N,\ \lvert u_n-\ell\rvert\geq\varepsilon.$$

« Il existe une marge $\varepsilon$ que la suite continue de dépasser aussi loin qu'on aille. »

$u_n=(-1)^n$ ne converge pas vers $1$. Prenons $\varepsilon=1$. Soit $N\in\mathbb{N}$ quelconque ; posons $n=2N+1$, qui est $\geq N$ et impair, donc $u_n=-1$ et $\lvert u_n-1\rvert=2\geq1=\varepsilon$. La négation est établie. $\blacksquare$

Le même argument avec $n=2N$ montre qu'elle ne converge pas non plus vers $-1$ — et en fait vers aucun $\ell$ (avec $\varepsilon=1$, l'un des deux termes $u_{2N}$, $u_{2N+1}$ est à distance $\geq1$ de $\ell$, puisqu'ils sont à distance $2$ l'un de l'autre).

$$\boxed{(-1)^n\ \text{ne converge pas : }\varepsilon=1\text{ convient}}$$

Démontrer. Un $\forall x$ se prouve en prenant $x$ quelconque ; un $\exists x$ se prouve en exhibant un $x$ (souvent construit à partir des données qui le précèdent dans la phrase).

Nier. $\lnot(\forall x,\ P(x))\iff\exists x,\ \lnot P(x)$ et $\lnot(\exists x,\ P(x))\iff\forall x,\ \lnot P(x)$. Pour une phrase à plusieurs quantificateurs, on les bascule tous, dans l'ordre, puis on nie le prédicat — sans jamais permuter deux quantificateurs de natures différentes.

Ordre. $\exists y\,\forall x\,P(x,y)\Rightarrow\forall x\,\exists y\,P(x,y)$, jamais la réciproque en général.

⚠️ Basculer les quantificateurs sans nier le prédicat. La négation de « $\forall x,\ f(x)\leq M$ » n'est pas « $\exists x,\ f(x)\leq M$ » (qui est presque toujours vraie et ne dit rien), c'est « $\exists x,\ f(x)>M$ ». Réciproquement, nier le prédicat sans basculer donne « $\forall x,\ f(x)>M$ » — beaucoup trop fort.

⚠️ Écrire « $\forall\varepsilon,\ \exists N$ » en laissant $N$ indépendant de $\varepsilon$. Le $N$ a le droit de dépendre de $\varepsilon$, et il en dépend toujours : plus la marge est fine, plus le rang est grand. Une preuve de convergence qui donne un $N$ « universel » a en général confondu $\forall\,\exists$ et $\exists\,\forall$.

⚠️ « Tous les élèves ont réussi » nié en « tous ont échoué ». La négation est « au moins un a échoué » — un seul contre-exemple suffit, et un seul est promis.

La contraposée de « $n^2$ pair $\Rightarrow$ $n$ pair » est « $n$ impair $\Rightarrow$ $n^2$ impair » : écrire $n=2k+1$ et développer.

Pour la question 2, un entier non multiple de $3$ s'écrit $3k+1$ ou $3k+2$ ; calculer le carré dans chaque cas.

Question 4 : la contraposée est « $a\neq0\Rightarrow\exists\varepsilon>0,\ \lvert a\rvert>\varepsilon$ ». Quel $\varepsilon$ prendre ?

On raisonne par contraposée quand l'hypothèse est difficile à exploiter et la conclusion facile à nier. « $n^2$ est pair » ne dit rien de commode sur $n$ (il faudrait extraire une racine) ; « $n$ est impair », en revanche, s'écrit $n=2k+1$ et se calcule. Puisque $P\Rightarrow Q$ et $\lnot Q\Rightarrow\lnot P$ ont la même table de vérité (exercice A1), prouver la seconde prouve la première.

👉 Le réflexe : avant d'attaquer $P\Rightarrow Q$, se demander si $\lnot Q$ est plus concret que $P$. Si oui, contraposer. Et bien écrire, dès la première ligne, « par contraposée, montrons que $\lnot Q\Rightarrow\lnot P$ » — sinon le lecteur croit qu'on prouve la réciproque.

Par contraposée, montrons : si $n$ est impair, alors $n^2$ est impair. Soit $n$ impair : il existe $k\in\mathbb{Z}$ tel que $n=2k+1$. Alors

$$n^2=(2k+1)^2=4k^2+4k+1=2\,(2k^2+2k)+1,$$

qui est de la forme $2m+1$ avec $m=2k^2+2k$ entier : $n^2$ est impair. La contraposée est prouvée, donc l'implication aussi :

$$\boxed{n^2\ \text{pair}\ \Rightarrow\ n\ \text{pair}}\qquad\blacksquare$$

Contrôle par instances : le banc a vérifié l'énoncé pour tous les $n\leq999$ — ce qui ne le prouve pas (il y a une infinité d'entiers) mais garantit qu'on n'a pas démontré une proposition fausse. La preuve, elle, est dans l'identité $(2k+1)^2=4k(k+1)+1$, valable pour tout $k$.

ℹ️ Cette implication est la clé de l'irrationalité de $\sqrt2$ (exercice A4) : c'est elle qui fait passer de « $p^2$ pair » à « $p$ pair ».

Par contraposée : si $n$ n'est pas multiple de $3$, alors $n^2$ n'en est pas un. Un entier non multiple de $3$ a pour reste $1$ ou $2$ dans la division par $3$ : $n=3k+1$ ou $n=3k+2$. Disjonction de cas :

$$(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1,\qquad(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1.$$

Dans les deux cas $n^2$ a pour reste $1$ : il n'est pas multiple de $3$. $\blacksquare$

$$\boxed{3\mid n^2\ \Rightarrow\ 3\mid n}$$

👉 Le même schéma prouve « $p\mid n^2\Rightarrow p\mid n$ » pour tout nombre premier $p$, mais il faut alors $p-1$ cas — ou le lemme d'Euclide du chapitre d'arithmétique, qui le fait d'un coup. Et l'énoncé est faux pour un non-premier : $4\mid36=6^2$ sans que $4\mid6$. L'exercice A1 le disait : une implication vraie sous une hypothèse peut tomber quand on l'affaiblit.

Par contraposée, montrons : si non ($x\neq0$ et $y\neq0$), alors $xy=0$. Par la loi de Morgan, l'hypothèse s'écrit « $x=0$ ou $y=0$ ». Disjonction de cas : si $x=0$, alors $xy=0\cdot y=0$ ; si $y=0$, alors $xy=x\cdot0=0$. Dans les deux cas $xy=0$. $\blacksquare$

$$\boxed{xy\neq0\ \Rightarrow\ (x\neq0\ \text{et}\ y\neq0)}$$

⚠️ Deux pièges dans ce petit énoncé. D'abord, la négation de « $x\neq0$ et $y\neq0$ » est « $x=0$ ou $y=0$ », pas « $x=0$ et $y=0$ » (Morgan). Ensuite, la réciproque — « $x\neq0$ et $y\neq0$ $\Rightarrow$ $xy\neq0$ » — est vraie dans $\mathbb{R}$ (c'est l'intégrité), mais elle demande une autre preuve ; dans $\mathbb{Z}/6\mathbb{Z}$, $2\times3=0$ avec deux facteurs non nuls, elle est fausse.

L'énoncé est : $\bigl(\forall\varepsilon>0,\ \lvert a\rvert\leq\varepsilon\bigr)\Rightarrow a=0$. Par contraposée, montrons que si $a\neq0$, alors il existe $\varepsilon>0$ tel que $\lvert a\rvert>\varepsilon$. Soit $a\neq0$ ; alors $\lvert a\rvert>0$ et l'on peut poser

$$\varepsilon=\frac{\lvert a\rvert}2>0,\qquad\text{qui vérifie}\quad\lvert a\rvert>\frac{\lvert a\rvert}2=\varepsilon.$$

Ce $\varepsilon$ exhibé prouve la négation de l'hypothèse. $\blacksquare$

$$\boxed{\bigl(\forall\varepsilon>0,\ \lvert a\rvert\leq\varepsilon\bigr)\ \Rightarrow\ a=0}$$

👉 C'est le lemme qui fait fonctionner toute l'analyse : pour prouver que deux nombres sont égaux, on prouve que leur différence est plus petite que tout $\varepsilon>0$. L'unicité de la limite d'une suite se démontre exactement ainsi. Note que le $\varepsilon$ qu'on exhibe dépend de $a$ — c'est permis, il vient après $a$ dans la phrase.

Contraposée. $(P\Rightarrow Q)\iff(\lnot Q\Rightarrow\lnot P)$. Le raisonnement par contraposée consiste à démontrer la seconde à la place de la première ; il faut l'annoncer.

Ne pas confondre avec l'absurde. Par l'absurde, on suppose $P$ et $\lnot Q$ et on cherche une contradiction quelconque ; par contraposée, on suppose seulement $\lnot Q$ et on vise $\lnot P$. La contraposée est plus disciplinée : on sait où l'on va.

Disjonction de cas. Quand l'hypothèse se découpe en cas exhaustifs (pair / impair ; reste $0$, $1$ ou $2$), on traite chaque cas ; il faut vérifier que les cas couvrent tout.

⚠️ Démontrer la réciproque en croyant contraposer. Pour « $n^2$ pair $\Rightarrow$ $n$ pair », écrire « soit $n$ pair, alors $n^2$ est pair » prouve $n$ pair $\Rightarrow$ $n^2$ pair : la réciproque, qui ne sert à rien ici. La contraposée commence par « soit $n$ impair ».

⚠️ Oublier un cas. Pour les multiples de $3$, ne traiter que $n=3k+1$ laisse $n=3k+2$ sans preuve — et c'est là que se cache l'erreur si elle existe. Toujours vérifier que les cas sont exhaustifs.

⚠️ Choisir un $\varepsilon$ qui dépend de ce qu'on n'a pas encore. Dans la question 4, $\varepsilon=\lvert a\rvert/2$ est légitime parce que $a$ est fixé avant. Écrire $\varepsilon=\lvert a\rvert/2$ dans une phrase où $a$ vient après $\varepsilon$ serait une erreur d'ordre des quantificateurs (exercice A2).

Suppose $\sqrt2=p/q$ avec la fraction irréductible ; élève au carré et regarde la parité de $p$, puis celle de $q$.

S'il existait un plus petit réel $r>0$, que dire de $r/2$ ?

Suppose qu'il n'y a qu'un nombre fini de premiers $p_1,\dots,p_r$, et regarde un diviseur premier de $p_1p_2\cdots p_r+1$.

Raisonner par l'absurde, c'est supposer le contraire de ce qu'on veut, et en tirer une contradiction. La logique derrière : si $\lnot P$ mène à une proposition fausse, alors $\lnot P$ est fausse, donc $P$ est vraie. C'est le mode de raisonnement des énoncés négatifs (« $\sqrt2$ n'est pas rationnel », « il n'existe pas de plus petit… ») et des énoncés d'infinité — parce que la négation d'un tel énoncé donne un objet concret (une fraction, un plus petit élément, une liste finie) avec lequel on peut calculer.

👉 Les trois preuves de cet exercice ont le même squelette : supposons que non ; alors voici un objet ; cet objet viole une propriété qu'il devait avoir ; contradiction.

Supposons par l'absurde que $\sqrt2\in\mathbb{Q}$ : il existe des entiers $p\in\mathbb{Z}$, $q\in\mathbb{N}^*$ tels que $\sqrt2=\dfrac pq$, et l'on peut choisir la fraction irréductible (on simplifie par le pgcd). Alors $2q^2=p^2$.

Donc $p^2$ est pair, donc $p$ est pair (exercice A3) : $p=2p'$. Alors $2q^2=4p'^2$, soit $q^2=2p'^2$ : $q^2$ est pair, donc $q$ est pair. Mais alors $p$ et $q$ sont tous deux pairs, ce qui contredit l'irréductibilité de $\dfrac pq$. Contradiction : l'hypothèse $\sqrt2\in\mathbb{Q}$ est fausse. $\blacksquare$

$$\boxed{\sqrt2\notin\mathbb{Q}}$$

ℹ️ Le banc a vérifié qu'aucune fraction $p/q$ avec $q\leq500$ n'a pour carré $2$. Ce n'est pas la preuve — il y a une infinité de fractions — mais c'est le contrôle que l'énoncé démontré n'est pas faux. La même preuve donne l'irrationalité de $\sqrt3$ (avec « $3\mid p^2\Rightarrow3\mid p$ ») et de $\sqrt p$ pour tout premier $p$.

Supposons par l'absurde qu'il existe un plus petit réel strictement positif $r$ : $r>0$, et tout réel $s>0$ vérifie $s\geq r$. Posons $s=\dfrac r2$. Alors $s>0$ (moitié d'un réel positif), donc par hypothèse $s\geq r$, c'est-à-dire $\dfrac r2\geq r$, soit $r\leq0$ après multiplication par $2$ et soustraction. Contradiction avec $r>0$. $\blacksquare$

$$\boxed{\mathbb{R}_+^*\ \text{n'a pas de plus petit élément}}$$

👉 Ce que la preuve dit vraiment : $\mathbb{R}_+^*$ a une borne inférieure, $0$, qui n'est pas atteinte. La différence entre « plus petit élément » et « borne inférieure » est le sujet de l'exercice C3. Et c'est cette propriété qui rend les $\varepsilon$ de l'analyse si puissants : aucun $\varepsilon>0$ n'est le dernier.

Supposons par l'absurde qu'il n'existe qu'un nombre fini de nombres premiers, disons $p_1,p_2,\dots,p_r$ (la liste complète). Posons

$$N=p_1p_2\cdots p_r+1.$$

$N\geq2$, donc $N$ possède un diviseur premier $p$ (exercice A6, récurrence forte). Ce $p$ est dans la liste : $p=p_i$ pour un certain $i$. Mais $p_i$ divise le produit $p_1\cdots p_r$, donc s'il divisait aussi $N$, il diviserait leur différence $N-p_1\cdots p_r=1$ — impossible pour un nombre premier. Contradiction. $\blacksquare$

$$\boxed{\text{il existe une infinité de nombres premiers}}$$

⚠️ La preuve ne dit PAS que $N$ est premier. Elle dit que $N$ a un diviseur premier hors de la liste. C'est toute la différence, et la question 4 la met en évidence.

$N=2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30\,030+1=30\,031$. Testons les premiers jusqu'à $\sqrt{30\,031}\approx173$ : $N$ n'est divisible par aucun de $2,3,5,7,11,13$ (reste $1$ par construction), ni par $17,19,23,29,31,37,41,43,47,53$… mais

$$30\,031=59\times509,$$

et $59$, $509$ sont premiers. $N$ n'est pas premier. Ce n'est pas une contradiction avec Euclide : ses deux facteurs premiers, $59$ et $509$, sont hors de la liste $\{2,3,5,7,11,13\}$ — exactement ce que la preuve promet. Les premiers produits $2+1=3$, $2\cdot3+1=7$, $2\cdot3\cdot5+1=31$, $211$, $2311$ sont premiers ; $30\,031$ est le premier qui ne l'est pas.

$$\boxed{30\,031=59\times509\ :\ \text{Euclide fournit un premier NOUVEAU, pas un premier}}$$

Raisonnement par l'absurde. Pour prouver $P$ : supposer $\lnot P$, en déduire une proposition fausse (souvent $Q\land\lnot Q$), conclure que $P$ est vraie. Justifié par $(\lnot P\Rightarrow\text{Faux})\iff P$.

Pour une implication $P\Rightarrow Q$ : supposer $P$ et $\lnot Q$. C'est plus général que la contraposée (qui ne suppose que $\lnot Q$ et vise $\lnot P$), mais moins guidé.

Rédaction. Annoncer « par l'absurde, supposons… », isoler l'objet que l'hypothèse fournit, calculer, et nommer la contradiction obtenue.

⚠️ Oublier l'irréductibilité dans la preuve de $\sqrt2$. Sans elle, « $p$ et $q$ pairs » n'est pas une contradiction : on aurait pu partir de $\frac{2}{\sqrt2}$… La contradiction vient de ce qu'on avait choisi $p/q$ simplifiée. (Variante sans ce choix : une descente infinie $p>p'>p''>\dots$ d'entiers positifs, impossible.)

⚠️ Conclure que $p_1\cdots p_r+1$ est premier. Faux dès $r=6$ : $30\,031=59\times509$. La preuve d'Euclide construit un entier dont un diviseur premier est nouveau, ce qui suffit — et c'est tout.

⚠️ Prouver une implication en supposant seulement $\lnot Q$ sans utiliser $P$. Si la preuve n'emploie jamais l'hypothèse $P$, c'est qu'on démontre $\lnot Q\Rightarrow\text{Faux}$, c'est-à-dire $Q$ tout court — soit l'énoncé est plus fort que prévu, soit il y a une erreur.

Nomme la propriété $P(n)$, vérifie $P(1)$, puis suppose $P(n)$ pour un $n$ fixé et ajoute le terme suivant.

Pour l'hérédité de la divisibilité, écris $4^{n+1}-1=4(4^n-1)+3$.

Pour Bernoulli, multiplie $(1+x)^n\geq1+nx$ par $1+x$ : pourquoi faut-il $1+x\geq0$ ?

Une récurrence, c'est deux étapes, et le principe qui les relie est admis. On nomme la propriété $P(n)$ ; on vérifie l'initialisation $P(n_0)$ ; on démontre l'hérédité — pour un entier $n\geq n_0$ fixé tel que $P(n)$ est vraie, $P(n+1)$ l'est aussi. Le principe de récurrence conclut alors que $P(n)$ est vraie pour tout $n\geq n_0$. Ce principe est une propriété fondatrice de $\mathbb{N}$ : on l'admet — c'est la seule chose admise dans ce chapitre.

👉 Ce qui rend une récurrence convaincante n'est pas la formule finale, c'est la phrase d'hérédité : « soit $n\geq n_0$ tel que $P(n)$ ; montrons $P(n+1)$ ». Elle suppose $P(n)$ pour un $n$, pas pour tous.

Soit $P(n)$ : « $1+3+\dots+(2n-1)=n^2$ », c'est-à-dire $\sum_{k=1}^n(2k-1)=n^2$.

Initialisation. $P(1)$ : la somme se réduit à $1=1^2$. Vraie.

Hérédité. Soit $n\geq1$ tel que $P(n)$ soit vraie. Alors

$$\sum_{k=1}^{n+1}(2k-1)=\underbrace{\sum_{k=1}^{n}(2k-1)}_{=\,n^2\ \text{par }P(n)}+\bigl(2(n+1)-1\bigr)=n^2+2n+1=(n+1)^2,$$

ce qui est $P(n+1)$.

Conclusion. Par le principe de récurrence, $P(n)$ est vraie pour tout $n\geq1$. $\blacksquare$

$$\boxed{1+3+\dots+(2n-1)=n^2}$$

ℹ️ Vue autrement : un carré $n\times n$ se construit en ajoutant à chaque étape une équerre de $2n+1$ cases. Le banc a recalculé la somme pour $n\leq200$ et fait vérifier l'identité $n^2+(2n+1)=(n+1)^2$ par sympy — deux contrôles, la preuve étant dans l'hérédité.

Soit $P(n)$ : « $3\mid4^n-1$ ».

Initialisation. $4^0-1=0=3\times0$ : $P(0)$ est vraie.

Hérédité. Soit $n\in\mathbb{N}$ tel que $3\mid4^n-1$, c'est-à-dire $4^n-1=3m$ pour un entier $m$. Alors

$$4^{n+1}-1=4\cdot4^n-1=4(4^n-1)+3=4\cdot3m+3=3\,(4m+1),$$

donc $3\mid4^{n+1}-1$ : $P(n+1)$.

Conclusion. $3\mid4^n-1$ pour tout $n\in\mathbb{N}$. $\blacksquare$

$$\boxed{\forall n\in\mathbb{N},\ 3\mid4^n-1}$$

👉 L'astuce de l'hérédité est toujours la même : écrire la quantité au rang $n+1$ en fonction de celle au rang $n$. Ici $4^{n+1}-1=4(4^n-1)+3$. (Le chapitre d'arithmétique le dira en une ligne : $4\equiv1\pmod3$, donc $4^n\equiv1$.)