Approfondissements de lycée/Premiers

Nombres premiers

Introduction

Un nombre premier (ou premier en abrégé) est un 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.

Les 20 premiers nombres premiers sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

Les nombres premiers sont une source sans fin de fascination pour les mathématiciens. Certains des problèmes concernant les nombres premiers sont si difficiles que même le travail de certains des plus brillants mathématiciens n'a pas suffi à les résoudre. Un de ceux-ci est la conjecture de Goldbach, qui énonce que tous les nombres pairs supérieurs à 3 peuvent être exprimés comme somme de deux nombres premiers.

Signification géométrique des nombres premiers

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

{\begin{matrix}12&=&12\times 1\\&=&6\times 2\\&=&4\times 3\\\end{matrix}}

Nous ne distinguons pas 2 x 6 et 6 x 2 parce que ce sont des arrangements équivalents.

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

Théorème fondamental de l'arithmétique

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.

Avec ces définitions posées, le théorème fondamental de l'arithmétique énonce simplement que :

Tout nombre entier supérieur ou égal à 2 peut être décomposé en un unique produit de nombres premiers.

Par exemple

12=2\times 2\times 3

Le réarrangement de l'ordre de la multiplication n'est pas considéré comme une représentation différente du nombre, ainsi, il n'existe pas d'autre manière d'exprimer 12 comme le produit de nombres premiers.

Quelques exemples supplémentaires

{\begin{matrix}99&=&3\times 3\times 11\\52&=&2\times 2\times 13\\17&=&17\end{matrix}}

Un nombre qui peut être décomposé en plus d'un facteur premier est appelé un nombre composé (ou composé pour abréger). Composé est l'opposé de premier.

Réfléchir à cela

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 ?

Décomposition

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 qu'on peut maintenant se poser est la suivante: pour un nombre donné x, existe-t'il une manière facile de trouver tous les facteurs premiers de x ?

Si x est un petit nombre, c'est facile. Par exemple 90 = 2 x 3 x 3 x 5. Mais si x est grand ? Par exemple x = 4539 ? La plupart des gens ne peuvent pas décomposer 4539 en facteurs premiers de tête. Mais un ordinateur le peut, quasi instantanément, pour donner ce résultat: 4539 = 3 x 17 x 89.

Puisque les ordinateurs sont très bons pour faire de l'arithmétique, nous pouvons extraire tous les facteurs de x en indiquant simplement à l'ordinateur de diviser x par 2 et par 3 et par 4 et par 5 et par 6 ... et ainsi de suite, et vérifier si à chaque fois le résultat est un nombre entier. Considérons les trois exemples suivants de la méthode des divisions en action.

Exemple 1

x=21

x/2=10.5

n'est pas un nombre entier

x/3=7

donc 3 et 7 sont les facteurs de 21.

Exemple 2

x = 153

x / 2 = 76,5 donc 2 n'est pas un facteur de 153

x / 3 = 51 donc 3 et 51 sont les facteurs de 153

51 / 3 = 17 donc 3 et 17 sont les facteurs de 153

Il est clair que 3, 9, 17 et 51 sont les facteurs de 153. Les facteurs premiers de 153 sont 3, 3 et 17 (3 x 3 x 17 = 153)

Exemple 3

2057 / 2 = 1028,5

...

2057 / 11 = 187

187 / 11 = 17

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

Exercices

Décomposer les nombres suivants :

13
26
59
82
101
121
2187 Si cela prend trop de temps, il existe une manière rapide...

info — Décomposition en facteurs premiers

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, ni même prouvé qu'elle existe. Certains des schémas de cryptologie les plus largement utilisés aujourd'hui (tel que le 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 deviendront non sécurisées.
Avec les développements récents, des méthodes qui ne déterminent pas directement si un nombre est premier ou non, mais donnent une probabilité qu'il soit premier, ont été définies. Ces méthodes sont aujourd'hui suffisamment affinées pour pouvoir dire rapidement, avec l'aide d'un programme informatique, si un nombre est premier avec une précision proche de 100%.

Deux, cinq et trois

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 ?

Théorème - Divisibilité par 3

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

c.a.d. 272 n'est pas divisible par 3, parceque 2+7+2=11. Et 11 n'est pas divisible par 3.

945 est divisible par 3, parceque 9+4+5 = 18. Et 18 est divisible par 3. En fait 945 / 3 = 315

Est-ce que 123456789 est divisible par 3 ?

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) x 9 / 2 = 45

4 + 5 = 9

Neuf est divisible par 3, par conséquent 45 est divisible par 3, par conséquent 123456789 est divisible par 3 !

(Ce qui fait que la méthode marche est un théorème, bien que la démonstration ne soit pas donnée ici.)

La beauté de ce théorème réside dans sa nature récursive. Un nombre est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3. Comment savoir si la somme de ses chiffres est divisible par 3 ? Appliquer le théorème de nouveau ! Ceci est tellement vrai "... la récursivité, [est] divine".

Essayez quelques nombres vous-mêmes.

info — Récursivité

Un scientifique éminent d'informatique a dit un jour "L'itération est humaine, la récursivité, divine." Mais que veut dire récursivité ? Avant cela, qu'est-ce que l'itération ?
"Itérer" veut dire simplement faire la même chose encore et encore, les ordinateurs font cela très bien. Un exemple d'itération en mathématiques est l'opération d'exponentiation, c.a.d. xⁿ qui veut dire $x\times x\times x\times x...$ n fois. C'est un exemple d'itération.
Penser à l'itération économiquement (en termes de ressources mentales), en définissant un problème en termes de lui-même, est "récursif". Pour représenter xⁿ récursivement, nous écrivons :

$x^{n}=1$ si n est égal à 0.

$x^{n}=x\times x^{n-1}$ si n > 0

Qu'est-ce que 9⁹ ? C'est 9 x 9⁸. Mais qu'est-ce que 9⁸ ?, c'est 9 x 9⁷. Répéter cette manière de faire est un exemple de récursivité.

Exercices

Factoriser ces entiers :

45
4050
2187

Trouver des nombres premiers

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.

Premièrement, nous écrivons tous les nombres compris entre 0 et 51 dans une table comme ci-dessous

{\begin{matrix}1&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}

On enlève 1, car il n'est pas premier.

{\begin{matrix}X&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}

Maintenant, 2 est le plus petit nombre pas encore rayé dans la table. Nous marquons 2 comme un nombre premier et nous rayons tous ses multiples 4, 6, 8, 10 ...

{\begin{matrix}X&2_{p}&3&X&5&X&7&X&9&X\\11&X&13&X&15&X&17&X&19&X\\21&X&23&X&25&X&27&X&29&X\\31&X&33&X&35&X&37&X&39&X\\41&X&43&X&45&X&47&X&49&X\\\end{matrix}}

Maintenant, 3 est le plus petit nombre pas encore marqué. Nous marquons 3 comme un nombre premier et nous rayons tous ses multiples 6, 9, 12, 15 ...

{\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}

Maintenant 5 est le plus petit nombre pas encore marqué. Nous marquons 5 comme un nombre premier et nous rayons tous les multiples de 5.

{\begin{matrix}X&2_{p}&3_{p}&X&5_{p}&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\end{matrix}}

Maintenant 7 est le plus petit nombre pas encore marqué. Nous marquons 7 comme un nombre premier et nous rayons tous les multiples de 7.

{\begin{matrix}X&2_{p}&3_{p}&X&5_{p}&X&7_{p}&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&X&X\\\end{matrix}}

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² > 50. (Pourquoi ?)

Exercice

1. Trouver tous les nombres premiers inférieurs à 200

Infinité des nombres premiers

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 :

Démonstration de l'infinité des nombres premiers

D'abord, supposons la proposition suivante :

il existe un nombre fini de nombres premiers

par conséquent

il doit exister un nombre premier qui est plus grand que tous les autres,

appelons ce nombre premier n. Nous allons maintenant montrer que les deux propositions sont contradictoires, et ainsi montrer qu'il existe une infinité de nombres premiers.

Prenons le produit de tous les nombres premiers pour former un nombre x. Ainsi :

x=2\times 3\times 5\times \ldots \times n

Alors, soit y égal à un plus que x :

y=x+1

On peut maintenant conclure que y n'est divisible par aucun des nombres premiers formant x, 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.

info — Nombres premiers dans une progression arithmétique

Considérons la progression arithmétique

a, a + b, a + 2b, a + 3b ....

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 ! Par exemple, considérons a = 3, b = 4,

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

dans cette liste plutôt courte, 3, 7, 11, 19, 23 et 31 sont premiers et ils sont tous égaux à 4k + 3 pour un certain k. Et il existe une infinité de nombres premiers dans cette progression (voir : Exercices sur la démonstration par l'absurde Démonstrations).

Ensemble de problèmes

1. Montrer que le théorème "divisible par 3" marche pour tout nombre à 3 chiffres (Astuce : Exprimer un nombre à 3 chiffres sous la forme 100a + 10b + c, où 0 ≤ a, b et c ≤ 9)

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.

3. Existe-t'il une règle pour déterminer si un nombre à 3 chiffres est divisible par 11 ? Si oui, déterminer cette règle.

4.

{\begin{matrix}X&2&3&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}

Le crible premier a été appliqué à la table ci-dessus. Noter que chaque nombre situé directement sous 2 et 5 sont rayés. Construire une grille rectangulaire de nombre allant de 1 à 60 telle que le crible premier ayant été exécuté sur elle, tous les nombres situés directement sous 3 et 5 soient rayés. Quelle est la largeur de la grille ?

5. Montrer que p, p + 2 et p + 4 ne peuvent pas être tous des nombres premiers, p un nombre entier positif supérieur ou égal à 4.

6. Montrer que n - 1 a lui-même comme inverse modulo n.

7. Montrer que 10 n'a pas d'inverse modulo 15.

8. Trouver x

{\begin{matrix}x\equiv 3^{7}+1^{7}+2^{7}++4^{7}+5^{7}+6^{7}+7^{7}\ {\pmod {7}}\\\end{matrix}}

9. Montrer qu'il n'existe pas d'entier x et y tels que

x^{2}-5y^{2}=3

10. Soit p un nombre premier. Montrer que

(a)

(p-1)!\equiv -1\ {\mbox{(mod p)}}

où

n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n

C.a.d. 3! = 1*2*3 = 6

(b)

Maintenant, montrer que

{\sqrt {-1}}\equiv {\frac {p-1}{2}}!{\pmod {p}}

pour p ≡ 1 (mod 4)

Projet — La racine carrée de -1

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

{\sqrt {-1}}\equiv {\sqrt {p-1}}{\pmod {p}}

existe pour p ≡ 1 (mod 4) premier. Expliquer pourquoi aucune racine carrée de -1 n'existe si p ≡ 3 (mod 4) est premier.

2. Montrer que pour p ≡ 1 (mod 4) premier, il existe exactement 2 solutions à

x =

{\sqrt {-1}}{\pmod {p}}

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 :

x ≡ a (mod m)

x ≡ b (mod n)

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

x ≡ 0 (mod 2)

x ≡ 1 (mod 3)

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.

4. Si p ≡ 1 (mod 4) premier et q ≡ 3 (mod 4) premier. Est-ce que

{\sqrt {-1}}{\pmod {pq}}

a une solution ? Pourquoi ?

5. Si p ≡ 1 (mod 4) premier et q ≡ 1 (mod 4) premier et p ≠ q. Montrer que

x={\sqrt {-1}}{\pmod {pq}}

a plus que 4 solutions.

6. Trouver les 4 solutions pour

x={\sqrt {-1}}{\pmod {493}}

noter que 493 = 17 x 29.

7. Prendre un entier n avec plus de 2 facteurs premiers. Considérons :

x={\sqrt {-1}}{\pmod {n}}

Sous quelle conditions existe-t'il une solution ? L'expliquer.