« Approfondissements de lycée/Premiers » : différence entre les versions

[[Approfondissements de lycée]]

 

 

Un nombre premier (ou premier en abrégé) est un nombre entier naturel qui admet deux et seulement deux diviseurs : 1 et lui-même. Pour des raisons théoriques, le nombre 1 n'est pas considéré comme un nombre premier (nous verrons pourquoi plus tard dans ce chapitre). Par exemple, 2 est un nombre premier, 3 est premier, et 5 est premier, mais 4 ne l'est pas parce qu'il est divisible par 2.

 

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

 

 

Prenons un exemple : si nous avons 12 carreaux de carrelage, pouvons-nous les assembler en une forme rectangulaire de plus d'une façon ? Bien sur, nous le pouvons : ceci est dû au fait que

 

Mais qu'en est-il du nombre 7 ? Pouvez-vous arranger 7 carreaux de carrelage en une forme rectangulaire de plus d'une facon ? La réponse est non, parce que 7 est un nombre premier.

 

Un '''théorème''' est un fait mathématique non-évident (on dit aussi non-trivial). Un théorème doit être démontré ; une proposition qui est généralement reconnue comme vraie, mais sans démonstration, est appelée '''conjecture'''. Les '''axiomes''' sont les faits de base que nous supposons vrais, et qui sont utilisés pour démontrer les théorèmes. Ils tendent à être des énoncés évidents mais ils sont importants lorsque nous voulons démontrer formellement les choses.

 

:''Garder à l'esprit la définition du théorème fondamental de l'arithmétique, pourquoi le nombre 1 n'est-il pas considéré comme premier ?''

 

Nous savons, à partir du théorème fondamental de l'arithmétique que tout nombre entier peut être exprimé comme un produit de nombres premiers. La question est : pour un nombre donné ''x'', existe-t'il une manière ''facile'' de trouver tous les facteurs premiers de ''x'' ?

 

:donc 11, 11 et 17 sont les facteurs premiers de 2057.

 

Décomposer les nombres suivants :

# 13

# 2187 Si cela prend trop de temps, il existe une manière rapide...

 

<blockquote style="padding: 1em; border: 2px dotted purple;">

Il existe une manière ''facile'' de décomposer un nombre en facteurs premiers. En appliquant simplement la méthode décrite ci-dessus (en utilisant un ordinateur). Mais la méthode ci-dessus est trop lente pour les grands nombres : essayer de décomposer un nombre avec des milliers de chiffres prendrait plus de temps que l'age actuel de l'univers. Mais existe-t'il une manière ''rapide'' ? Ou plus précisément, existe-t'il une manière ''efficiente'' ? Cela se peut, mais personne ne l'a encore trouvée. Certains des schémas de cryptologie les plus largement utilisés aujourd'hui (tel que le [http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman RSA]) utilisent le fait que nous ne pouvons pas décomposer des grands nombres en facteurs premiers rapidement. Si une telle méthode est trouvée, 90 % des transactions sur internet seront non sécurisées. Donc, s'il vous arrive de découvrir une telle méthode, ne soyez pas trop empressé de la publier, consultez votre ministère de sécurité nationale avant !

</blockquote>

 

Les nombres premiers 2, 5 et 3 tiennent une place spéciale dans la décomposition. Premièrement, tous les nombres pairs ont 2 comme l'un de leurs facteurs premiers. Deuxièmement, tous les nombres qui finissent par 0 ou 5 peuvent être divisés entièrement par 5.

 

Le troisième cas, où 3 est un facteur premier, est le but de cette section. La question sous-jacente est : existe-t'il une manière simple de décider si un nombre possède 3 comme l'un de ses facteurs premiers ? La réponse est oui. Mais comment ?

 

<blockquote style="padding: 1em; border: 2px dotted purple;">

''Un nombre est divisible par 3 si et seulement si la '''somme de ses chiffres''' est divisible par 3''

:''Essayez quelques nombres vous-mêmes.''

 

<blockquote style="padding: 1em; border: 2px dotted purple;">

Un scientifique éminent d'informatique a dit un jour "L'itération est humaine, la récursivité, divine." Mais que veux dire ''récursivité'' ? Avant cela, qu'est-ce que l'''itération'' ?

</blockquote>

 

Factoriser ces entiers :

# 45

# 2187

 

Le crible des nombres premiers est une méthode relativement efficiente pour trouver tous les nombres premiers inférieurs ou égaux à un nombre précis. Disons que nous voulons tous les nombres premiers inférieurs ou égaux à 50.

 

\begin{matrix}

X & 2_p & 3 & X & 5 & X & 7 & X & 9 & X \\

\end{matrix}

</math>

\begin{matrix}

X & 2_p & 3_p & X & 5 & X & 7 & X & X & X \\

X & X & 23 & X & 25 & X & X & X & 29 & X \\

\end{matrix}

</math>

\begin{matrix}

X & 2_p & 3_p & X & 5_p & X & 7 & X & X & X \\

X & X & 23 & X & X & X & X & X & 29 & X \\

\end{matrix}

</math>

\begin{matrix}

X & 2_p & 3_p & X & 5_p & X & 7_p & X & X & X \\

X & X & 23 & X & X & X & X & X & 29 & X \\

\end{matrix}

</math>

La méthode décrite ci-dessus peut être répétée, mais elle n'éliminera pas un nombre composé pas encore éliminé. ''Essayez de le prouver vous-même !'' Mais pourquoi est-ce ainsi ? Parceque le prochain nombre non marqué est 11 et 11² &gt; 50. (Pourquoi ?)

 

1. Trouver tous les nombres inférieurs à 200

 

Nous savons que certains nombres peuvent être décomposés en nombres premiers. Certains ont seulement eux-mêmes comme nombre premier, parcequ'ils sont premiers. Donc, combien de nombres premiers existe-t'il ? Il en existe une infinité ! Voici une démonstration classique de l'infinité des nombres premiers datant de plus de 2 000 ans et due au mathématicien grec Euclide :

 

 

 

On peut maintenant conclure que ''y'' n'est divisible par aucun des nombres premiers formant ''n'', puisque ''y'' diffère d'un multiple de chacun des nombres premiers par exactement 1. Puisque ''y'' n'est divisible par aucun nombre premier, ''y'' doit être soit un nombre premier, ou ses facteurs premiers doivent tous être plus grands que ''n'', une contradiction de la proposition originale qui énonce que ''n'' est le plus grand nombre premier ! Par conséquent, on peut déclarer que la proposition originale est incorrecte, et ainsi, qu'il existe une infinité de nombres premiers.

 

<blockquote style="padding: 1em; border: 2px dotted purple;">

Considérons la progression arithmétique

:''a'', ''a'' + ''b'', ''a'' + 2''b'', ''a'' + 3''b'' ....

si ''a'' et ''b'' partagent un facteur commun plus grand que 1, alors ''a'' + ''kb'' pour tout k n'est pas un nombre premier. Mais si ''a'' et ''b'' sont premiers entre eux, alors il existe une infinité de ''k'''s tels que ''a'' + ''kb'' est premier !

:3, 7, 11, 15, 19, 23, 27, 31...

</blockquote>

 

== Ensemble de problèmes ==

 

2. "Un nombre est divisible par 9 si et seulement si la somme est divisible par 9." Vrai ou faux ? Déterminer si 89, 558, 51858, et 41857 sont divisibles par 9. Vérifier vos réponses.

:<math>

\begin{matrix}

\end{matrix}

</math>

Maintenant, montrer que

:<math>\sqrt{-1} \equiv \frac{p - 1}{2}! \pmod{p}</math>

 

== Projet — La racine carrée de -1 ==

1. La question 10 de l'ensemble des problèmes a montré que

:<math>\sqrt{-1} \equiv \sqrt{p-1} \pmod{p}</math>

 

:x = <math>\sqrt{-1} \pmod{p}</math>

 

3. Supposons ''m'' et ''n'', des nombres entiers avec pgdc(''n'',''m'') = 1. Montrer que pour chacun des nombres 0, 1, 2, 3, .... , ''nm'' - 1, il existe une paire unique de nombre ''a'' et ''b'' tel que le plus petit nombre ''x'' qui satisfait :

est ce nombre.

C.a.d. Supposons m = 2, n = 3, alors 4 est uniquement représenté par

comme le plus petit ''x'' qui satisfait les deux congruences précédentes est ''4''. Dans ce cas, l'unique paire de nombres est 0 et 1.

 

:<math>\sqrt{-1} \pmod{pq}</math>

a une solution ? Pourquoi ?

 

:<math>x = \sqrt{-1} \pmod{pq}</math>

a plus que 4 solutions.