[PDF] Les nombres premiers - Lycée dAdultes

Exemple :Montrer que 109 est un nombre premier.

On a 10<⎷

109<11.

2, 3, 5 et 7.

109=7×15+4 109 n"est donc pas divisible par 7

PAUL MILAN2TERMINALE S SPÉ

1. DÉFINITION ET PROPRIÉTÉS IMMÉDIATES

Algorithme :Un petit programme

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

2→I

Traitement

AfficherN, "div. par :" ,I

I+1→I

Nfaire

AfficherN, "div. par :" ,I

I+2→I

Sorties: AfficherN, "est premier"

1.3 Infinité des nombres premiers

1,p2,...,pi, ...,pn. PosonsN=p1×p2× ··· ×pi× ··· ×pn+1

1.4 Crible d"Ératosthène

Remarque :

1) Pour éliminer les multiples propre de 7, commencer à 7

2, car les multiples

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

Sin?150, alors⎷

2345678910

11121314151617181920

21222324252627282930

31323334353637383940

41424344454647484950

51525354555657585960

61626364656667686970

71727374757677787980

81828384858687888990

919293949596979899100

101102103104105106107108109110

111112113114115116117118119120

121122123124125126127128129130

131132133134135136137138139140

141142143144145146147148149150

On peut écrire l"algorithme suivant :

•Les entiersAcorrespondent aux

•Les entiersMcorrespondent aux

•Les entiersPcorrespondent aux

•Les entiersQcorrespondent au

•La listeL1correspond à la liste des

•La ListeL2correspond à la liste des

À chaque fois que l"on trouve un

On trouve le nombre premier suivant

A, en prenant dans la listeL1le nombre

Avec la Ti, pour visualiser la listeL2

Variables:N,I,A,M,P,Qentiers

1,L2listes

Entrées et initialisation

Effacer listeL1

Effacer listeL2

I→L1(I)

2→A

0→P

Traitement

A+1→A

P+1→P

1(A)→L2(P)

A?I→M

0→L1(M)

Sorties: AfficherP,L2

De plus comme les listes sont limitées, ren-

PAUL MILAN4TERMINALE S SPÉ

1. DÉFINITION ET PROPRIÉTÉS IMMÉDIATES

1.5 Nombres de Mersenne

1) Calculons les 6 premiers nombres de Mersenne :

1=2-1=1

2=4-1=3

3=8-1=7

4=16-1=15

5=32-1=31

6=64-1=63

57 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 :

Factorisons alorsMn:

On peut aussi utiliser la contraposée :

SiMnest premier alorsnl"est également.

3) La réciproque est-elle vraie?

11n"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

Sipdiviseab?pdiviseaoupdiviseb

2.2 Conséquences

3 Décomposition, diviseurs d"un entier

3.1 Théorème fondamental de l"arithmétique

16 758

Pour décomposer un entier, on effec-

PAUL MILAN6TERMINALE S SPÉ

3. DÉCOMPOSITION, DIVISEURS D"UN ENTIER

Algorithme :: On peut proposer l"al-

On teste siDest un diviseur deNen

N. On ré-

Le dernier nombre qui ne vérifie par le

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 :

1={3,5,7,13,19,31,97}

Variables:N,D,I,Centiers

1liste

Entrées et initialisation