Montrer par l'absurde que p_i divise N

Bonjour, j’ai besoin de montrer par l’absurde que pour $N = (\displaystyle \prod_{i = 1}^{r} p_i) + 1$ où $(p_i)_{0 \leq i \leq r}$ est une famille de nombres premiers, il n’existe aucun des entiers $p_i$ qui divise N.

Voici mon raisonnement, on suppose $\exists (k, j) \in \mathbb Z \times \mathbb N^* : N = k p_j$. Auquel cas $\frac{N}{p_j} = k \iff \frac{(\displaystyle \prod_{i = 1}^{r} p_i) + 1}{p_j} = (\displaystyle \prod_{i = 1 i \neq j}^{r - 1} p_i) + \frac{1}{p_j} = k$.

Or, 1 n’est pas premier donc $0 < \frac{1}{p_j} < 1$ et on sait que $\displaystyle \prod_{i = 1 i \neq j}^{r - 1} p_i \in \mathbb N$ d’où $k = \frac{N}{p_j}$ n’est pas un entier. Donc il n’existe aucun des $p_i$ qui divise N.

Cependant, le raisonnement sur cette page (exercice 14 - cliquez sur correction) semble être sensiblement différent : qu’est-ce qui ne va pas dans le mien?

Merci d’avance!

Tu pourrais partir dans la direction de

Pardon.

Pourquoi ne pas directement prendre Je modulo $p_i$ ?

C’est essentiellement ce que propose la correction

"Je" ?

Donc ce que j’écris est faux?

Ton raisonnement est juste et ça revient à prendre modulo p_i comme le dit Holosmos (en moins bien dit).

Par contre vraiment la correction est très peu claire. Ça revient encore à la même chose, mais ne t’en inspires pas. Ouais bon finalement j’ai rien dit.

En regardant de plus près la correction, ils supposent qu’il existe $p_j$ qui divise N, puis $N - \displaystyle \prod_{i = 1}^{r} p_i = p_j k - p_j (\displaystyle \prod_{i = 1 i \neq j}^{r - 1} p_i) = p_j(k - \displaystyle \prod_{i = 1 i \neq j}^{r - 1} p_i) = 1$.

Donc pour $q = k - \displaystyle \prod_{i = 1 i \neq j}^{r - 1} p_i$, $p_j q = 1 \iff p_j = \frac{1}{q} \in \mathbb Z$ d’où $p_j = 1$ ou $-1$.

Donc finalement, c’est un raisonnement par contraposition et non par l’absurde, d’où ma confusion…

(Un raisonnement par contraposée est un cas particulier de raisonnement par l’absurde.)

Bah oui :

$P \implies Q \equiv \neg Q \implies \neg P$ donc on ne peut avoir $\neg P$ et $Q$ vrais en même temps.

EDIT : C’est $\neg Q$ et $P$ vrais en même temps.

Euh je voulais dire $P$ et $\neg Q$ vrais en même temps.

J’ai bien noté tes remarques Elegance, mais j’ai du mal à comprendre ce que tu écris. Qu’est-ce que signifie $i <> j$?

Je pense que ça signifie $i \neq j$.

D’accord, je vois où veux en venir elegance. Il faut grosso-modo que je fasse ressortir le nombre premier qui va diviser N. J’ai édité le post original.

J’ai édité mon message précédent, pour le rendre un peu plus lisible.

Tu n’as pas rectifié suite au dernier point. Sinon, Ok pour la correction que tu as apportée.

C’est édité.

Merci pour votre aide.

@Holosmos: Oui. Il suffit que P soit vrai pour que Q le soit. Mais rien ne nous indique que Q ne puisse être vrai si P ne l’est pas. En revanche, il est nécessaire que Q soit vrai pour que P le soit.

Ce n’est pas vrai. Dans un raisonnement par l’absurde, on est amenés à écrire une assertion fausse, ce qui n’est pas le cas lors d’un raisonnement par contraposée.

Lorsque l’on raisonne par l’absurde, en général on ne démontre pas d’implication. Alors que dans un raisonnement par contraposée, on démontre que (non B) implique (non A) pour monter que A implique B. Le fait de supposer B fausse n’est pas contradictoire, car la vérité de (A implique B) et celle de B ne sont pas reliées en général.

@c_pages : Oui, ce que j’ai écrit est vraiment bancal, ça veut pas dire grand chose. J’avais en tête la chose suivante. Dans un raisonnement par contraposée, on montre $\lnot B \implies \lnot A$, et pour passer de ça à $A \implies B$ on utilise le fait que $\lnot \lnot A \implies A$ (un raisonnement par l’absurde). Mais bref, c’est complètement inintéressant.

Je pense pas qu’il y ait un moyen de montrer que la contraposée est équivalente à l’implication sans passer par un tiers exclus. Si ?

D’ailleurs :

Dans un raisonnement par l’absurde, on est amenés à écrire une assertion fausse, ce qui n’est pas le cas lors d’un raisonnement par contraposée.

Ce n’est pas clair. Si tu retires le tiers exclus, tu peux montrer que machin implique le faux, mais tu peux pas en conclure que machin est une assertion fausse.

Et si tu retires pas le tiers exclus, il me semble que les deux procédures sont équivalentes.

Je pense pas qu’il y ait un moyen de montrer que la contraposée est équivalente à l’implication sans passer par un tiers exclus. Si ?

En effet, on peut déduire le tiers exclu « par contraposée ». Si on prend $\lnot A = A \to \bot$, on a $(A \to \bot) \to (((A \to \bot) \to \bot) \to \bot)$, et si on s’autorise à déduire $A \to B$ de $\lnot B \to \lnot A$, alors on obtient $((A \to \bot) \to \bot) \to A$.

(La contraposée de $A \to B$ est $\lnot B \to \lnot A$, il y a implication sans tiers exclu, donc ici parle de raisonnement « par contraposée » pour l’implication réciproque.)

Et si tu retires pas le tiers exclus, il me semble que les deux procédures sont équivalentes.

Il y a une différence en général entre une proposition fausse et une proposition impliquant le faux ?

Il y a une différence en général entre une proposition fausse et une proposition impliquant le faux ?

Une proposition qui serait ni vraie ni fausse pourrait impliquer le faux. D’où la nécessité de retirer le tiers exclus.