Approfondissements de lycée/Premiers
Approfondissements de lycée
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
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 :
Par exemple
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
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
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
Exemple 2
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
Exercices.
Décomposer les nombres suivants :
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 ?
Neuf est divisible par 3, par conséquent 45 est divisible par 3, par conséquent 123456789 est divisible par 3 !
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".
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. xn qui veut dire formula_7n 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 xn récursivement, nous écrivons :
Qu'est-ce que 99 ? C'est 9 x 98. Mais qu'est-ce que 98 ?, c'est 9 x 97. Répéter cette manière de faire est un exemple de récursivité.
Exercices.
Factoriser ces entiers :
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
On enlève 1, car il n'est pas premier.
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 ...
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 ...
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.
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.
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 112 > 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 :
par conséquent
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 :
Alors, soit "y" égal à un plus que "x" :
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
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,
dans cette liste plutôt courte, 3, 7, 11, 19, 23 et 31 sont premiers et ils sont tous égaux à 4"k" + 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.
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
9. Montrer qu'il n'existe pas d'entier x et y tels que
10.
Soit "p" un nombre premier. Montrer que
où
C.a.d. 3! = 1*2*3 = 6
Maintenant, montrer que
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
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 à
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.
4. Si "p" ≡ 1 (mod 4) premier et "q" ≡ 3 (mod 4) premier. Est-ce que
a une solution ? Pourquoi ?
5. Si "p" ≡ 1 (mod 4) premier et "q" ≡ 1 (mod 4) premier et p ≠ q. Montrer que
a plus que 4 solutions.
6. Trouver les 4 solutions pour
noter que 493 = 17 x 29.
7. Prendre un entier "n" avec plus de 2 facteurs premiers. Considérons :
Sous quelle conditions existe-t'il une solution ? L'expliquer.