Les nombres premiers
2 déc. 2016 des entiers de 2 à n. • Les nombres de Mersenne : On pose Mn = 2n ? 1. Proposition (exos bac) : Si Mn est premier alors n est premier.
Les nombres premiers - Lycée dAdultes
22 juil. 2015 Théorème 1 : Tout entier naturel n n ? 2
Raisonnement 1 Différents types de raisonnements
Si n n'est pas premier il possède un diviseur d différent de 1 et de n. On peut écrire n = kd. 1. Page 2. Alors 2n ? 1 = (2d
NOMBRES de MERSENNE (1588-1648)
Démonstration : Nous allons tout d'abord montrer qu'il vient alors forcément a = 2 puis nous démontrerons que si 2 n. - 1 est premier
Exercices de mathématiques - Exo7
Montrer que si p est premier et 8p2 +1 est premier alors 8p2 ?1 est premier. Correction ?. [005297]. Exercice 8 **I. 1. Montrer que ?(kn) ? (N?)2
Exercices de logique
Correction 1. 1. n pair n = 2 ? n non premier. Démo : si n pair
PGCD ET NOMBRES PREMIERS
Si D un diviseur de b et r alors D divise a = bq + r et donc D est un diviseur Démontrer que pour tout entier naturel n 2n + 3 et 5n + 7 sont premiers ...
Nombres premiers. ( )n ( )1
2 n ? . Le nombre n se décompose en produit de facteurs premiers (unique à l'ordre CS : Toujours par contraposée si 2n+1 n'est pas premier
Correction : 27 p. 82 Correction : 28 p. 82 Correction : 29 p. 82
Si n = 2 alors n2 – 2n + 1 = 1 n'est pas premier. Si n ? 3 alors n - 1 est supérieur à 2. Donc : (n - 1) divise n2 – 2n + 1
CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE
congru à 0 1 ou 2 modulo 3
[PDF] Les nombres premiers - Lycée dAdultes
2 déc 2016 · des entiers de 2 à n • Les nombres de Mersenne : On pose Mn = 2n ? 1 Proposition (exos bac) : Si Mn est premier alors n est premier
[PDF] Les nombres premiers - Lycée dAdultes
22 juil 2015 · Théorème 1 : Tout entier naturel n n ? 2 admet un diviseur premier Si n n'est pas premier alors il admet un diviseur premier p tel que
Collection de nombres - Mersenne propriétés conjecture record
Propriétés fondamentales Si on connaît un nombre de MERSENNE premier: 2n – 1 Alors on connaît un nombre PARFAIT beaucoup plus grand: 2n – 1 (2n – 1)
[PDF] chapitre 3 : congruences et arithmétique modulaire
Si a et n sont premiers entre eux alors il existe une solution x de ax ? b (mod n) et c'est unique modulo n Existence On cherche une relation de Bezout 7u
[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques
- Sinon le plus petit diviseur p1 de n est premier et il existe un entier naturel n1 tel que : n = p1n1 - Si n1 est premier l'existence est démontrée -
[PDF] Nombres premiers
2 Soit n > 1 n non premier n admet donc un diviseur d autre que 1 et n En effet si p1 divisait k comme p1 divise le produit p1p2 pn alors p1
[PDF] Nombres premiers Applications
1 2 2 — Nombres de Mersenne : de la factorisation Xpq ?1=(Xp ?1)(Xp(q?1) +···+Xp +1) on en déduit que si 2n ?1 est premier alors n est un nombre premier
[PDF] 1´Enoncé
Montrer que si p est un nombre premier congru `a 1 modulo n alors p divise ?n 9 On se donne un entier n ? 2 et un nombre premier p qui divise ?n (a)
Exercices - Les-Mathematiquesnet
1963264.pdf
[PDF] Nombres premiers ( )n ( )1 - Thierry Sageaux
Proposition (2 F) : Si n n'est pas premier alors il admet au moins un diviseur premier p tel que p n
Pourquoi 2 n'est pas premier ?
2 est un nombre premier car il n'est divisible que par 1 (2 ÷ 1 = 2) et par lui-même (2 ÷ 2 = 1) ; 4 n'est pas un nombre premier car il admet 3 diviseurs : 1, 2 et 4 ; 123 n'est pas un nombre premier, car il est divisible par 3.Comment savoir si un nombre est premier PDF ?
Un nombre entier naturel (supérieur ou égal à 2) est un nombre premier s'il admet exactement 2 diviseurs : 1 et lui-même. Exemple : 2, 3, 5, 7, 11, 13, 17, 19 … sont des nombres premiers.Comment montrer que n et n 1 sont premiers entre eux ?
En effet, on peut écrire (n + 1) x 1 - n x 1 = 1, donc d'après le théorème de Bézout, les entiers n et n + 1 sont premiers entre eux. On a donc PGCD(n ; n+1) = 1 = (n + 1) - n.- En 1947 la liste correcte des nombres de Mersenne premiers pour n < 258, est établie et vérifiée : n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 et 127. On connaît actuellement une quarantaine de nombres de Mersenne.
Les nombres premiers
Table des matières
1 Définition et propriétés immédiates2
1.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Critère d"arrêt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Infinité des nombres premiers. . . . . . . . . . . . . . . . . . . . . . 3
1.4 Crible d"Ératosthène. . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Nombres de Mersenne. . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Divisibilité et nombres premiers6
2.1 Théorème de Gauss et nombres premiers. . . . . . . . . . . . . . . 6
2.2 Conséquences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Décomposition, diviseurs d"un entier6
3.1 Théorème fondamental de l"arithmétique. . . . . . . . . . . . . . . 6
3.2 Diviseurs d"un entier. . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Problèmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Petit théorème de Fermat - Hors programme10
4.1 Théorème, remarque et exemple. . . . . . . . . . . . . . . . . . . . 10
4.2 Nombre de Poulet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
PAUL MILAN1TERMINALE S SPÉ
TABLE DES MATIÈRES
1 Définition et propriétés immédiates
1.1 Définition
Définition 1 :Un nombre premier est un entier naturel qui admet exacte- ment deux diviseurs : 1 et lui-mêmeConséquence:
1 n"est pas un nombre premier (il n"a qu"un seul diviseur) Un nombre premierpest un naturel supérieur ou égal à 2 soit :p?2.Les nombres premiers inférieurs à 100 sont :2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97
1.2 Critère d"arrêt
Théorème 1 :Tout entier natureln,n?2, admet un diviseur premier. Sinn"est pas premier, alors il admet un diviseur premierptel que :2?p?⎷
nDémonstration :
Sinest premier, il admet donc un diviseur premier : lui-même. Sinn"est pas premier, l"ensemble des diviseursddentel que : 2?dExemple :Montrer que 109 est un nombre premier.
On a 10<⎷
109<11.
On teste tous les nombres premiers strictement inférieurs à 11, soit:2, 3, 5 et 7.
Des règles de divisibilité, on déduit que 109 n"est divisible nipar 2, ni par 3, ni par 5. En effectuant la division euclidienne de 109 par 7, on obtient :109=7×15+4 109 n"est donc pas divisible par 7
Conclusion : comme 109 n"est pas divisible par 2, 3, 5, et 7, 109est premier.PAUL MILAN2TERMINALE S SPÉ
1. DÉFINITION ET PROPRIÉTÉS IMMÉDIATES
Algorithme :Un petit programme
pour déterminer si un nombreNest premier. N"ayant pas à notre disposi- tion la liste des nombres premiers, on teste siNest divisible par 2, puis on teste les diviseurs impairs par ordre croissant tant que ceux-ci sont inférieur N.On obtient alors :
527 est divisible par 17
719 est premier
11 111 est divisible par 41
37 589 est premier
Variables:N,Ientiers
Entrées et initialisation
LireN2→I
Traitement
siE?NI? =NIalorsAfficherN, "div. par :" ,I
Stop finI+1→I
tant queI?⎷Nfaire
siE?NI? =NIalorsAfficherN, "div. par :" ,I
Stop finI+2→I
finSorties: AfficherN, "est premier"
1.3 Infinité des nombres premiers
Théorème 2 :Il existe une infinité de nombres premiers ROCDémonstration :Supposons qu"il existe un nombre fini de nombres premiers : p1,p2,...,pi, ...,pn. PosonsN=p1×p2× ··· ×pi× ··· ×pn+1
D"après le critère d"arrêt,Nadmet un diviseur premier. Soitpice diviseur premier.pidivise doncp1×p2× ··· ×pi× ··· ×pnetN. Il divise donc la différenceN-(p1×p2× ··· ×pi× ··· ×pn) =1. Ceci est impossible, donc l"hypothèse qu"il existe un nombre finide nombres pre- miers est absurde.1.4 Crible d"Ératosthène
Pour dresser la liste des nombres premiers entre 2 et 150, la méthode du crible d"Ératosthène consiste à : écrire la liste des nombres entiers de 2 à 150; éliminer successivement les multiples propres1de 2, de 3... puis ceux dep, où pest le premier nombre non encore éliminé, etc Les entiers éliminés (sur fond bleu dans le tableau ci après) sont les entiers non premiers entre 2 et 150. Les entiers restant (sur fond jaune) sont donc les nombres premiers inférieur à 150.Remarque :
1) Pour éliminer les multiples propre de 7, commencer à 7
2, car les multiples
inférieurs ont déjà été éliminés.1. multiple propre den: multiple dendistinct den
PAUL MILAN3TERMINALE S SPÉ
TABLE DES MATIÈRES
2) Il est possible de savoir à l"avance " jusqu"où aller ». En effet grâce au critère
nSin?150, alors⎷
n?⎷150, or 12<⎷150<13 et donc tout entier non premier sera éliminés en tant que multiple propre de 2, 3, 5, 7 et 11.2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
101102103104105106107108109110
111112113114115116117118119120
121122123124125126127128129130
131132133134135136137138139140
141142143144145146147148149150
On peut écrire l"algorithme suivant :
Les entiersAcorrespondent aux
nombres premiers de la liste des en- tiers de 2 àNLes entiersMcorrespondent aux
multiples deAinférieurs àNLes entiersPcorrespondent aux
rangs des nombres premiersA.Les entiersQcorrespondent au
nombre de multiples deAinférieurs àNLa listeL1correspond à la liste des
entiers de 2 àNLa ListeL2correspond à la liste des
nombres premiers inférieurs àNÀ chaque fois que l"on trouve un
nombre premierA, on le met dans la listeL2et l"on remplace tous les mul- tiples deAdans la listeL1par un 0 (re- vient à rayer tous ces multiples)On trouve le nombre premier suivant
A, en prenant dans la listeL1le nombre
suivant non nulAvec la Ti, pour visualiser la listeL2
faire :...puis "edit"Variables:N,I,A,M,P,Qentiers
L1,L2listes
Entrées et initialisation
LireNEffacer listeL1
Effacer listeL2
pourI de 2 à N *faireI→L1(I)
fin2→A
0→P
Traitement
tant queA?Nfaire tant queL1(A) =0faireA+1→A
fin siA?NalorsP+1→P
L1(A)→L2(P)
E?N A? →Q fin pourI de 1 à QfaireA?I→M
0→L1(M)
fin finSorties: AfficherP,L2
*Pour les TI faire : Ide 1 àN+1.De plus comme les listes sont limitées, ren-
trer un nombre N inférieur à 999PAUL MILAN4TERMINALE S SPÉ
1. DÉFINITION ET PROPRIÉTÉS IMMÉDIATES
1.5 Nombres de Mersenne
On appelle nombres de Mersenne, les nombresMnde la forme : M n=2n-1 avecn?N*1) Calculons les 6 premiers nombres de Mersenne :
M1=2-1=1
M2=4-1=3
M3=8-1=7
M4=16-1=15
M5=32-1=31
M6=64-1=63
On constate que pour lesnégaux à 2, 3, 5, les nombres de Mersenne sont premiers. Est-ce que sinest premier,Mnest premier? Cela permettrait de connaître un nombre premier aussi grand que l"on souhaite. Remarque :Actuellement (janvier 2013) le plus grand nombre premier trouvé (nombre de Mersenne) est : 257 885 161-1 qui possède 17 425 170 chiffres!
2) Montrons que sinn"est pas premier alorsMnne l"est pas non plus.
On rappelle la factorisation standard :
x n-1= (x-1)(xn-1+xn-2+···+x+1) Sinn"est pas premier, alors il existed, diviseur propre dentel que : n=dqavecq>1Factorisons alorsMn:
M n=2n-1 = (2d)q-1 carn=dq = (2d-1)[(2d)q-1+ (2d)q-2+···+2d+1] donc 2 d-1 est un diviseur propre deMnet doncMnn"est pas premier. Conclusion :Sinn"est pas premier alorsMnne l"est pas non plus.On peut aussi utiliser la contraposée :
SiMnest premier alorsnl"est également.
3) La réciproque est-elle vraie?
Malheureusement la réciproque est fausse, ce qui met à mal une formule per- mettant de trouver un nombre premier aussi grand que l"on souhaite. En effet sin=11 alorsM11=211-1=2 047 or 2 047=23×89. M11n"est pas premier mais 11 l"est.
PAUL MILAN5TERMINALE S SPÉ
TABLE DES MATIÈRES
2 Divisibilité et nombres premiers
2.1 Théorème de Gauss et nombres premiers
Les résultats qui suivent ne sont que des reformulations du théorème de Gauss et de ses conséquences dans le cas particulier des nombres premiers. Théorème 3 :Un nombre premier divise un produit de facteurs si, et seulement si, il divise l"un de ces facteurs.Sipdiviseab?pdiviseaoupdiviseb
En particulier, sippremier divise une puissanceak, alors nécessairementpdivise a, d"où découle quepkdiviseak.2.2 Conséquences
Si un nombre premierpdivise un produit de facteurs premiers, alorspest l"un de ces facteurs premiers Soitp1,p2,...,pkdes nombres premiers distincts etα1,α2,...,αkdes entiers na- turels non nuls. Si, pour touti?{1,2,...,k},pαiidivise un entiernalors le produitpα11pα22...pαkkdivise aussi l"entiern.3 Décomposition, diviseurs d"un entier
3.1 Théorème fondamental de l"arithmétique
Théorème 4 :tout entiern?2, peut se décomposer de façon unique (à l"ordre des facteurs près) en produit de facteurs premiers. n=pα11×pα22× ··· ×pαmm Exemple :Décomposons 16 758 en produit de facteur premier16 758
2 8 379 3 2 793 3 9317 133
7 19 19 1
Pour décomposer un entier, on effec-
tue des divisions successives par des nombres premiers dans l"ordre crois- sant. on a donc 16 758=2×32×72×19PAUL MILAN6TERMINALE S SPÉ
3. DÉCOMPOSITION, DIVISEURS D"UN ENTIER
Algorithme :: On peut proposer l"al-
gorithme suivant : Il faut donc chercher les facteurs premiers d"un entierN?2.On teste siDest un diviseur deNen
commençant par 2 puis les nombres im- pairs dans l"ordre croissant en appli- quant le critère d"arrêtD?⎷N. On ré-
initialiseNenprenantlequotientN/D.Le dernier nombre qui ne vérifie par le
critère d"arrêt est alors premier et on le rajoute à la liste des diviseurs. On peut tester la programme avec :16 758, on obtientL1={2,3,3,7,7,19}
87 616,onobtientL1={2,2,2,2,2,37,37}
77 986 545, on obtient :
L1={3,5,7,13,19,31,97}
Variables:N,D,I,Centiers
L1liste
Entrées et initialisation
LireN2→D
1→I
1→C
Traitement
tant queD?⎷Nfaire siE?ND? =NDalorsD→L1(I)
I+1→IN
D→N
sinonD+C→D
2→Cfin
finN→L1(I)
Sorties: AfficherL1
Application :Soit à calculer pgcd(126,735)et ppcm(126,735)Décomposons les deux nombres
1262 63
3 21
3 7 7 1 7353
245
5 49
7 7 7 1
On a donc :
quotesdbs_dbs41.pdfusesText_41[PDF] nombre de mersenne démonstration
[PDF] a^n-1 premier alors a=2
[PDF] le tourisme des français en 2016
[PDF] français vacances statistiques 2016
[PDF] tourisme français ? l'étranger
[PDF] ou partent les français en vacances
[PDF] pourcentage de français qui partent en vacances ? l'étranger
[PDF] nombre marche tour eiffel 2 etage
[PDF] hauteur tour eiffel 1er etage
[PDF] 1 etage combien de marches
[PDF] combien de marches pour monter au deuxième étage de la tour eiffel
[PDF] fonction logarithme bac pro exercice
[PDF] nombre de molécules dans 1 litre d'air
[PDF] nombre d'atomes sur terre