Wednesday, April 26, 2006

La preuve de la semaine

Bienvenue à toi à ce rendez-vous semestriel.

Tout d'abord merci au commentaire anonyme sur le dernier post qui fait ressortir une erreur dans la preuve. Ma réponse précise l'erreur d'écriture faite et apporte une correction.

Cette semaine je parlerai sommairement des nombres premiers pour ensuite m'intéresser à la preuve démontrant leur infinité.

Qu'est-ce qu'un nombre premier

Un nombre n est un premier si et seulement si:
  1. n > 1
  2. n n'a que deux diviseurs, 1 et n

L'intérêt du nombre premier.

En informatique on s'intéresse aux nombres premiers dans le domaine de la cryptologie (voir l'algorithme RSA). En effet le test de primalité - qui consiste à décider si un nombre est premier ou non - bien qu'ayant des algorithmes polynomiaux, reste dans la pratique un problème difficile.

Proposition intermédiaire

Pour cette preuve nous nous appuierons sur le théorème fondamental de l'arithmétique qui dit que tout nombre composé supérieur à 1 peut être écrit sous la forme d'un produit de facteurs premiers.

La preuve d'Euclide

Il existe une infinité de nombres premiers.
Pour s'en convaincre nous procédons par un raisonnement par l'absurde.

Faisons l'hypothèse que , l'ensemble des nombres premiers, soit fini. Nous pouvons alors énumérer de façon exhaustive ses éléments:



Nous posons . Alors deux cas se présentent:

1. est premier.

Si est premier, alors . Donc nous avons bien une contraction de l'hypothèse.

2. est un nombre composé.

Si est composé, alors on peut l'écrire comme un produit de facteurs premiers. Or , divisé par aurait pour reste 1. D'où l'existence de facteurs premiers n'étant pas inclut dans . Ce qui contredit l'hypothèse.

Nous pouvons alors conclure qu'il existe bien une infinité de nombres premiers.

Sunday, April 16, 2006

La preuve de la semaine

Cher lecteur,
me revoilà cette semaine avec encore une preuve triviale issue de la théorie des nombres. Nous cherchons à démontrer qu'il existe deux nombres irrationnels et tels que soit rationnel.

Qu'est-ce qu'un nombre rationnel?

Un nombre rationnel est un nombre qui peut s'écrire sous la forme d'une fraction, notamment . La forme duale étant le nombre irrationnel.

Première étape

Pour les besoins de la preuve nous établirons en premier lieu
l'irrationalité de . Pour cela nous procédons par un raisonnement par l'absurde.

Faisons l'hypothèse que soit rationnel. Alors , tels que , pour une fraction irréductible (pour non nul).

Nous élevons l'équation posée au carré pour obtenir

Donc nous avons qui nous permet de dire que
est divisible par deux. Comme est un nombre pair, l'est aussi.

Or si est divisible par deux, alors tel que .

Nous pouvons alors écrire et donc . Maintenant nous constatons que est divisible par deux, donc a fortiori aussi.

Nous avons obtenu et divisible par deux, or nous avons supposé et premiers entre eux, donc il y a bien contraction de l'hypothèse.

Alors est un nombre irrationnel. (CQFD)

Et maintenant la preuve.
Démontrons maintenant qu'il existe deux nombres irrationnels et tels que soit rationnel.

Notre preuve s'appuie sur la loi du tiers exclu qui en formulation
simple suppose qu'une proposition est soit vraie ou fausse.

Posons et .

Nous avons et deux cas se présentent:
1) Soit est un nombre rationnel, dans quel cas nous avons trouvé un rationnel validant la proposition.

2) Soit est irrationnel.

Dans quel cas nous posons et . En effet, nous avons bien établi l'irrationalité de et nous avons .

En simplifiant, nous obtenons , soit , un rationnel.

Dans les deux cas, nous obtenons un nombre rationnel.

Mot de la fin
Cette preuve est d'autant plus intéressante qu'elle fait appel au principe du tiers exclu qui est un raisonnement logique rejetté dans une démonstration constructive.

!Erreur!
Je remercie le commentaire anonyme pour avoir signalé l'erreur dans cette preuve. Voir les commentaires.