[PDF] Modèle mathématique. Méthode 4 : Trouver le

View - Download Modèle mathématique.

Previous PDF

Next PDF

1

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Les nombres premiers

A) Définition et premières propriétés.

1. Définition.

Définition :

Un nombre premier est un entier naturel qui admet exactement deux diviseurs : ͳ et lui-même.

Conséquences :

Un nombre premier ݌ est un entier naturel supérieur ou égal à ʹ, soit :݌൒ʹ.

Les nombres premiers inférieurs à ͳͲͲ sont : Remarque : un entier naturel non premier est parfois appelé un nombre composé. 2. .

Propriété :

Tout entier naturel ݊, ݊൒ʹ admet un diviseur premier. Si ݊ mier, alors il admet un diviseur premier ݌ tel que : ʹ൑݌൑ξ݊.

Démonstration :

Si ݊ est premier, il admet donc un diviseur premier : lui-même. ncipe du bon ordre, il admet donc un plus petit élément ݌. ceci est impossible car ݌ est le plus petit.

Donc ݌ est premier.

On a donc ݌ premier et ݊ൌ݌ൈݍ avec ݌൑ݍ multipliant cette inégalité par ݌, on

Méthode 1 : M

" Si ݊ ݌ tel que ʹ൑݌൑ξ݊, alors ݊ est premier. ».

Montrer que ͳͲͻ est un nombre premier.

On a ͳͲ൑ξͳͲͻ൑ͳͳ. Donc si ͳͲͻ diviseur premier inférieur à ͳͳ.

On teste tous les nombres premiers strictement inférieurs à ͳͳ, soit : ʹǡ͵ǡͷ et ͹.

Des règles de divisibilité, on déduit que ͳͲͻ ʹ, ni par ͵, ni par ͷ.

Donc ͳͲͻ ͹.

Conclusion : ͳͲͻ ʹǡ͵ǡͷ et ͹ donc ͳͲͻ est premier. 2

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

3. Infinité des nombres premiers.

Propriété :

Il existe une infinité de nombres premiers.

Démonstration :

diction est celle proposée au IIIe siècle av. J.-C., par Euclide, dans son ouvrage " Les Éléments ». Soit ܰ un nombre entier non premier, supérieur à 2, tel que : ܰ

Il divise donc la différence ܰ

Ceci est impossible car ݌௜൒ʹ premiers est absurde. 4. .

Algorithme :

Pour dresser la liste des nombres premiers inférieurs ou égaux à ܰ

Écrire la liste des entiers de ʹ à ܰ

posés (non premiers) plus petits que ܰ facteur premier inférieur ou égal à ξܰ Éliminer de la liste tous les multiples de ʹ sauf ʹ. Le nombre suivant non éliminé est alors premier. Ici on trouve ͵. Éliminer de la liste tous les multiples de ͵ sauf ͵. Le nombre suivant non éliminé est alors premier. Ici on trouve ͷ. - multiples de nombres premiers inférieurs ou

égaux à ξܰ

Remarques :

1) Pour éliminer les multiples de ܽ supérieurs à ܽ, commencer à ܽ

à ܽ ont déjà été éliminés. En effet, les multiples de ܽ inférieurs à ܽ

de nombres inférieurs à ܽ

2) Si ܰ

multiple de ʹǡ͵ǡͷǡ͹ et ͳͳ.

Exemple : Pour ܰ

3

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

B) Divisibilité et nombres premiers.

1. Théorème de Gauss et nombres premiers.

Propriété :

Soit ݌ un nombre premier et ܽ et ܾ

Si ݌ divise ܾܽ ฻ ݌ divise ܽ ou ݌ divise ܾ

Démonstration :

après le théorème de Gauss, ݌ divise ܾ

Remarques :

Le " où » de cette propriété est bien un " ou » inclusif car ݌ peut diviser ܽ et ܾ

En particulier, si ݌ est premier et divise une puissance ܽ௞, alors nécessairement ݌ divise ܽ

De cela découle que ݌௞ divise ܽ

2. Conséquences.

Si un nombre premier ݌ divise un produit de facteurs premiers, alors ݌ premiers.

Si un nombre ݊ est un carré, alors toutes les puissances des facteurs de sa décomposition en facteurs

premiers sont paires. nuls. Si, pour tout ݅א ఈ೔ divise un entier ݊, alors le produit ݌ଵ ఈೖ divise C)

1. Théorème .

Théorème :

Tout entier ݊൒ʹ dre des facteurs près) en produit de facteurs premiers. naturels non nuls : Méthode 2 : Décomposer un nombre en produit de facteurs premiers Décomposer ͳ͸͹ͷͺ en produit de facteurs premiers.

On présente la décomposition avec une barre

diviseurs premiers et, à gauche, le quotient des divisions successives par ces diviseurs premiers

On a donc :

4

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Démonstration :

Soit ݊ un entier naturel supérieur ou égal à 2. Si ݊ est premier, alors ݊ se décompose en lui-même.

Sinon ݊ൌ݌ଵൈݍଵ avec ݌ଵ൑ݍଵ et ݌ଵ ݊ admet un

diviseur premier ݌ଵ tel que ʹ൑݌ଵ൑ξ݊. Si ݍଵ est premier, alors ݊ se décompose en ݊ൌ݌ଵൈݍଵ.

Sinon on réitère le processus, obtenant ݍଷǡݍସǡǥǡݍ௡ avec ݍଷ൐ݍସ൐ڮ

Toute suite strictement décroissante dans Գ ang ݊ donc ݍ௡ regroupe alors sous la forme ݌ଵ non nuls.

existence de la décomposition est alors démontrée : lunicité de la décomposition est admise.

Méthode 3 : Déterminer le ܦܥܩܲ

Déterminer ܦܥܩܲ

On décompose les deux nombres en produit de facteurs premiers. On détermine les facteurs premiers communs pour trouver le ܦܥܩܲ

Remarque :

car il est plus économe en opérations :

On obtient ܦܥܩܲ

2. .

Théorème :

Alors tout diviseur ݀ de ݊ a pour décomposition :

Et le nombre ܰ

5

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Remarques :

Le nombre de divi

ip peut toutes les puissances ߙ Méthode 4 : Trouver le nombre de diviseurs de ͳʹͲ puis déterminer tous ces diviseurs.

On décompose ͳʹͲ en facteurs premiers : ͳʹͲൌʹଷൈ͵ൈͷ.

On alors : ܰ

ͳʹͲ a donc ͳ͸ diviseurs.

Pour déterminer tous ces diviseurs, on peut utiliser un tableau double entrée en séparant les

puissances de ʹ et les puissances de ͵ et ͷ. On obtient alors :

On peut aussi utiliser un arbre pondéré dont les coefficients sont les facteurs premiers

possibles :

Les 16 diviseurs de 120 sont donc :

Méthode 5 : Déterminer un entier conditionné par ses diviseurs Un entier naturel ݊ a ͳͷ diviseurs et il est divisible par ͸ mais pas par ͺ.

Déterminer cet entier ݊.

݊ ayant ͳͷ diviseurs, déterminons toutes les décompositions de ͳͷ en facteurs

supérieurs à ͳ. On peut décomposer ͳͷ en ͳ ou ʹ facteurs ቄͳͷ

On sait que ݊ est divisible par ͸, il est donc divisible par ʹ et par ͵ ݊ admet ʹ facteurs

premiers.

Comme ͳͷ ne peut se décomposer en plus de ʹ facteurs, alors ݊ ne peut admettre que ʹ

facteurs premiers ʹ et ͵. On a donc : ݊ൌʹ௔ൈ͵௕. On sait enfin que ݊ ͺൌʹଷ, donc ܽ 6

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Méthode 5 : Déterminer un entier conditionné par ses diviseurs Déterminer le plus petit entier naturel ݊ ayant ʹͺ diviseurs.

Soit ݊ cet entier.

toutes les décompositions de ʹͺ en facteurs supérieurs à ͳ. On peut décomposer ʹͺ en un, deux ou trois facteurs : ൞

Procédons ensuite par disjonction de cas :

En 1 facteur : ʹͺ.

Le plus petit entier ݊ est alors :

Avec ߙ൅ͳൌʹͺ donc ߙ

Le plus petit entier ݊ est alors :

On trouve alors :

Donc :

Le plus petit entier ݊ est alors :

On trouve alors :

Donc :

En trois facteurs : ʹͺൌʹൈʹൈ͹.

Le plus petit entier ݊ est alors :

On trouve alors :

Donc :

Conclusion : Le plus petit entier naturel ayant ʹͺ diviseurs est 960. 7

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

8

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Exercice n°1 :

t, déterminer si les entiers suivants sont premiers ou non : ͻ͹ ; ͳͲͻ ; ͳͳ͹ et ʹ͹ͳ.

Exercice n°2 :

݌ est premier et ݌൒ͷ.

Exercice n°3 :

݌൐͵ est un nombre premier

1) Quels sont les restes possibles dans la division de ݌ par ͳʹ ?

Exercice n°4 :

Démontrer que pour tout ݊אԳכ

Exercice n°5 :

Les quatre questions sont indépendantes :

1) Trouver un nombre de trois chiffres qui soit un carré parfait divisible par ͷ͸.

Exercice n°6 :

3) On sait de plus que ܽ et ܾ ont six diviseurs communs et ܽ

a) Démontrer que ݀ൌͳͺ. b) En déduire ܽ et ܾ

Exercice n°7 :

2) En déduire ݊.

Exercice n°8 :

Un entier ݊ a 5 diviseurs et ݊െͳ͸ est le produit de deux nombres premiers.

1) Prouver que ݊ൌ݌ସ, avec ݌ premier.

2) Écrire ݊െͳ͸ ݌.

3) En déduire la valeur de ݊.

Exercice n°9 :

9

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Exercice n°10 :

1) Écrire ʹͻ݌ comme le produit de deux facteurs en fonction de ݊.

2) Citer le théorème de Gauss appliqué aux nombres premiers.

3) En déduire ݊, puis ݌.

Exercice n°11 : Bac S Pondichéry 2015

Les nombres de la forme ʹ௡െͳ où ݊ est un entier naturel non nul, sont appelés nombres de

Mersenne.

uss, que : " Si ܾ divise ܽ et c divise ܽ, alors le produit ܾܿ divise ܽ

2) On considère le nombre de Mersenne ʹଷଷെͳ. Un élève utilise sa calculatrice et obtient les

résultats ci-dessous : a) En quoi cette affirmation contredit elle le résultat démontré à la question 1) ? c) En remarquant que ʹؠ e) En déduire que ͹ divise ʹଷଷെͳ.

3) On considère le nombre de Mersenne ʹ଻െͳ. Est-il premier ? Justifier.

4) ܦܱܯ

de ݊ par ݇. a) ݊ൌ͵͵ ? Et si on saisit ݊ൌ͹ ? b) Que représente le CAS 2 pour le nombre de Mersenne étudié ? Que représente alors le nombre ݇ affiché pour le nombre de Mersenne étudié ? c) Que représente le CAS 1 pour le nombre de Mersenne étudié ?

Tant que ܦܱܯ

Fin Tant que

Afficher ݇

Si ݇൐ξʹ௡െͳ

Afficher " CAS 1 »

Sinon

Afficher " CAS 2 »

Fin de Si

10

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

D) Système RSA : cryptage à clé pu.

1. Fonctionnement du système RSA.

Clé publique : on choisit deux nombres premiers ݌ et ݍ très grands et on calcule ܰ

Chiffrement :

un entier ݔ est chiffré par un entier ݕ tel que : ݕൌݔ௖݉݋݀ܰ

Déchiffrement :

݀ tel que ݀ؠܿ

un entier ݕ est chݔ tel que : ݔؠݕௗ݉݋݀ܰ Dans la pratique ݌ݍ est public mais pas ݌ et ݍ (ils sont gardés secrets).

La sécurité du sys݌

Petit théorème de Fermat :

si ݌ est un nombre premier et ܽ est un nombre non divisible par ݌ alors : ܽ௣ିଵؠ

2. Démonstrations.

1) ݀.

On pose ܰ

a) ܿ tels que : ܿ ݀ est donc de la forme : ݀ൌݑ଴൅݊݇. b) On veut ݀൒Ͳ donc ݑ଴൅݊݇൒Ͳ.

2) Validité du déchiffrement.

Soit x un entier.

a) Si ݌ est premier et ݔ ݌. après le petit théorème de Fermat on peut affirmer que : ݔ௣ିଵؠ

On en déduit que ݔ௡௩ؠ

Or ܿ݀െ݊ݒൌͳ donc ܿ

b) Si ݌ est premier et ݔ est divisible par ݌. ݔؠͲ݉݋݀݌ et de même ݔ௖ௗؠ

On a donc ݔ௖ௗؠ

11

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

c) Si ݍ est premier et ݔ ݍ.

On en déduit que ݔ௡௩ؠ

Or ܿ݀െ݊ݒൌͳ donc ܿ

d) Si ݍ est premier et ݔ est divisible par ݍ. ݔؠͲ݉݋݀ݍ et de même ݔ௖ௗؠ

On a donc ݔ௖ௗؠ

e) D ݔ௖ௗെݔ est divisible par ݌ et par ݍ.

Comme ݌ et ݍ sont premiers alors ݔ௖ௗെݔ est divisible par ݌ݍൌܰ

Donc ݔ௖ௗെݔؠͲ݉݋݀ܰ Exercice n°12 : Bac S Centres étrangers 2018 numérique Leonard Adleman, qui ont inventé cette méthode de cryptage en 1977 Les questions 1) et 2) sont des questions préparatoires, la question 3) aborde le cryptage, la question 4) le décryptage.

1) Cette question envisage de calculer le reste dans la division euclidienne par 55 de certaines

puissances de a) Vérifier que ͺ଻ؠ

3) Cryptage dans le système RSA

Une personne ܣ choisit deux nombres premiers ݌ et ݍ, puis calcule les produits ܰ envoyer un nombre crypté. Les messages sont numérisés et transformés en une compris entre 0 et ܰ Pour crypter un entier ܽ de cette suite, on procède ainsi : on calcule le reste ܾ euclidienne par ܰ du nombre ܽ௖ܾ méthode est sûre si la personne ܣ avec plusieurs dizaines de chiffres. lus simples : ݌ൌͷ et ݍൌͳͳ.

La personne ܣ choisit également ܿ

a) Calculer les nombres ܰ et ݊, puis justifier que la valeur de ܿ b) Un émetteur souhaite envoyer à la personne ܣ le nombre ܽ

Déterminer la valeur du nombre crypté ܾ

12

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

4) Décryptage dans le système RSA

La personne ܣ

Elle garde secret ce nombre ݀ qui lui permet, et à elle seule, de décrypter les nombres qui lui

ont été envoyés cryptés avec sa clé publique. Pour décrypter un nombre crypté ܾ, la personne ܣ calcule le reste ܽ euclidienne par ܰ du nombre ܾ est le nombre ܽ On adme݀, et le fait que le décryptage fonctionne. Les nombres choisis par ܣ sont encore ݌ൌͷ ; ݍൌͳͳ et ܿ a) Quelle est la valeur de ݀ ?

b) En appliquant la règle de décryptage, retrouver le nombre en clair lorsque le nombre crypté

est ܾ

Exercice n°13 : Bac S Liban 2018

pour ݊൒ͳ.

On appelle cette suite la suite de Fibonacci.

1) orithme ci-ܣ

contienne le terme ܽ On obtient ainsi les premières valeurs de la suite ܽ

2) Soit la matrice ܣ

Vérifier que ܣ

3) On peut démontrer, et nous admettrons, que pour tout entier naturel ݊ non nul, on :

a) Soit ݌ et ݍ deux entiers naturels non nuls. Calculer le produit ܣ௣ൈܣ c) Soit ݌ un entier naturel non nul. Démontrer, en utilisant un raisonnement par récurrence sur ݊, que pour tout entier naturel ݊ non nul, ܽ௣ divise ܽ

4) Soit ݊ un entier supérieur ou égal à 5. Montrer que si ݊

premier, alors ܽ

5) On peut calculer ܽ

Que penser de la réciproque de la propriété obtenue dans la question 4) ? 13

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Exercice n°14 : Amérique du Sud 2018

Pour tout entier naturel ݊ , on note ܨ

Partie A :

Pierre de Fermat, leur inventeur, a conjecturé que : " Tous les nombres de Fermat sont premiers », de cette partie est de tester cette conjecture.

2) Peut-on en déduire que tous les nombres de Fermat sont premiers ?

3) On considère -dessous :

Que peut-on en déduire ?

Partie B

de cette partie est de prouver que deux nombres de Fermat distincts sont toujours premiers entre eux.

2) Pour tout entier naturel ݊ on note :

On a donc :

Montrer par récurrence et en utilisant le résultat de la question précédente que pour tout entier

naturel n non nul on a :

3) Justifier que, pour tous entiers naturels ݊ et ݉ tels que ݊൐݉, il existe un entier naturel ݍ tel

que :

4) En déduire que deux nombres de Fermat sont toujours premiers entre eux.

Exercice n°15 : Bac S Pondichéry 2018

x compris entre 0 et 25 comme indiqué dans le tableau ci-dessous :

Le " chiffre de RABIN » est un dispositif de cryptage asymétrique inventé en 1979 par

Michael Rabin.

14

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Alice veut communiquer de manière sécurisée en utilisant ce cryptosystème. Elle choisit deux

nombres premiers distincts ݌ et ݍ.

Ce couple de nombres est sa clé garde secrète. Elle calcule ensuite ݊ൌ݌ൈݍ et elle

Si Bob veut envoyer un message secret à Alice, il le code lettre par lettre. sentée par le nombre entier ݔ est le nombre ݕ tel que :

Partie A : Cryptage

Bob veut envoyer le mot " NO » à Alice.

1) Montrer que Bob code la lettre " N » avec le nombre 8.

2) Déterminer le nombre qui code la lettre " O ».

Partie B : Décryptage

Alice a reçu un message crypté qui commence par le nombre 3. Pour décoder ce premier nombre, elle doit déterminer le nombre entier ݔ tel que : Déterminer, sans justification, chacune de ces solutions.

9) ci-dessous

question précédente :

10) Alice peut-elle connaître la première lettre du message envoyé par Bob ?

11) Le " chiffre de RABIN » est-il utilisable pour décoder un message lettre par lettre ?

15

Lycée Français de DOHA TS1 Spé

Année 2019 2020 M. Evanno

Interrogation de mathématiques

Devoir maison

Niveau : TS Spécialité

Thème : Les nombres premiers

Exercice n°1 : Bac S Antilles-Guyane 2017

On considère la suite définie par son premier terme ݑ଴ൌ͵ et, pour tout entier naturel ݊, par :

1) Démontrer que, pour tout entier naturel ݊, ݑ௡ൌͻൈʹ௡െ͸.

2) Démontrer que, pour tout entier ݊൒ͳ, ݑ௡ est divisible par 6.

pour tout entier naturel ݊൒ͳ, ݒ௡ est un nombre premier ». Indiquer si cette affirmation est vraie ou fausse en justifiant la réponse.quotesdbs_dbs46.pdfusesText_46

[PDF] Le poème " La voix " de Robert Desnos

[PDF] le poème définition

[PDF] le poème demain des l'aube de victor hugo

[PDF] Le poème lyrique

[PDF] le poid d'un corp

[PDF] Le poids

[PDF] Le poids : ne force d'attraction

[PDF] le poids d un corps

[PDF] le poids dun corps

[PDF] Le poids du foyer de peuplement européen dans le monde depuis l'Antiquité

[PDF] Le Poids et la masse d'un objet sont-ils les mêmes sur la Terre et sur la Lune

[PDF] Le poids et la taille

[PDF] le poids santé

[PDF] Le point D appartient-il au cercle C Justifier

[PDF] le point d chez la femme