Séquence 3 - Académie en ligne : tous les cours de l… · 2018-03-25 · Séquence 3 – MA03 1 Séquence 3 Arithmétique et problèmes de codages (suite) Cette séquence fait

1Séquence 3 – MA03

Séquence 3

Arithmétiqueet problèmes de codages (suite)

Cette séquence fait suite à la séquence 1. En utilisant à nouveau des problèmes de codages, nous allons introduire ou approfondir des éléments d’arithmétique.

Sommaire

1. Prérequis

2. Plus grand commun diviseur (PGCD) 3. Entiers premiers entre eux4. Retour sur les nombres premiers

et application au chiffrement RSA5. Synthèse

© Cned - Académie en ligne


Congruence

Soit n un entier naturel non nul donné, et soit x et y deux entiers relatifs quel-conques.

On dit que x est congru à y modulo n si la différence x y− est un multiple de n.

Dans ce cas, on note :

x y n≡ mod ou encore x y n≡ [ ] ou encore x y n≡ ( ) et on lit « x congru à y modulo n ».

Définition

Un nombre est congru à 0 modulo n si, et seulement si, c’est un multiple de n.

Tout nombre pair est congru à 0 modulo 2 ; tout nombre impair est congru à 1 modulo 2.

Tout nombre est congru à son chiffre des unités modulo 10.

Tout nombre est congru modulo n au reste de sa division euclidienne par n.

Conséquences

Si x y n≡ [ ] et y z n≡ [ ] alors x z n≡ [ ]. Transitivité

Si x y n≡ [ ] et ′ ≡ ′x y n[ ] alors x x y y n+ ′ ≡ + ′ [ ],

x x y y n− ′ ≡ − ′ [ ] et xx yy n′ ≡ ′ [ ]. Compatibilités

Si x y p≡ [ ] alors, pour tout entier naturel n, on a : x y pn n≡ [ ].

Propriété

A

1 Prérequis


4 Séquence 3 – MA03

Calcul matriciel

Une matrice de dimension n p× est un tableau de nombres à n lignes et p colonnes.

�

� � ��

A

a a a

a a a

a a a

=

p

p

n n np

11 12 1

21 22 2

1 2

Si n p= la matrice est dite carrée.

La matrice unité d’ordre n est une matrice carrée à n lignes et n colonnes dont la diagonale principale est composée de 1 et dont les autres coefficients sont nuls. Généralement, elle est notée I.

I I2 3= 1 00 1

, =1 0 00 1 00 0 1

.

Définitions

Opérations

Multiplication par un réel k d’une matrice : on multiplie par k chaque coefficient.

Addition de matrices de mêmes dimensions : on ajoute les coefficients correspon-dants.

Multiplication de deux matrices A et B : lorsque le nombre de colonnes de A est égal au nombre de lignes de B, le produit de la ligne i de A par la colonne j de B donne le coefficient du produit A B⋅ correspondant.

Définitions

En général, le produit n’est pas commutatif : A B B A⋅ ≠ ⋅ .

Puissance n-ième d’une matrice carrée non nulle A :

A Ip0 = et A A A A nn

n= 1⋅ ⋅ ⋅ ≥... .

foissi� ��

Inverse d’une matrice carrée : s’il existe une matrice B telle que A B B A I⋅ ⋅= = alors A est inversible et son inverse notée A−1 est B.

B



Matrices 2 2×

Si A a bc d

=

et det( ) = 0A ad bc− ≠ alors A est inversible et

AA

d bc a

− −−

1 =

1( )det

.

Propriétés

Décomposition en produit de facteurs premiers

Soit n un entier naturel strictement supérieur à 1 dont la décomposition en produit de facteurs premiers est :

n p p pk k= × × ×1 21 2α α α... .

Alors les diviseurs de n dans Nsont les entiers naturels p p pk k1 21 2β β β× × ×... où pour tout 1≤ ≤i k , 0 ≤ ≤β αi i .

Théorème

Soit n un entier naturel strictement supérieur à 1 dont la décomposition en produit de facteurs premiers est :

n p p pk k= × × ×1 21 2α α α... .

Alors le nombre de diviseurs positifs de n est ( 1) ( 1) ... ( 1).k1 2α α α+ × + × × +

Corollaire

C



2 Plus grand commun diviseur (PGCD)

Objectifs du chapitre

À travers des problèmes de pavages, nous allons revoir la notion de PGCD déjà vue en classe de troisième.

Pour débuter

Carrelage (1)

Dans une maison nouvellement construite, on veut carreler les sols de certaines pièces.

� Le sol de la salle à manger est un rectangle de longueur 4,54 m et de largeur 3,75 m. On veut carreler cette pièce avec des carreaux carrés de 33 cm de côté. On commence la pose par un coin de la pièce, comme le suggère la figure ci-dessous :

Calculer le nombre de carreaux non découpés qui auront été posés.

� Le sol de la cuisine est un rectangle de longueur 4,55 m et de largeur 3,85 m. On veut carreler cette pièce avec un nombre entier de dalles carrées, sans aucune découpe.

a) Donner la liste des diviseurs de 455 puis la liste des diviseurs de 385.

b) Donner la liste des diviseurs communs à 455 et 385.

c) Quel est alors le plus grand côté possible des dalles carrées pour carreler cette cuisine sans découpe ?

A

B

Activité 1



Carrelage (2)

Pour le couloir, on choisit une façon originale de carreler le sol.

On commence par poser des carreaux carrés dont le côté est le plus grand pos-sible. On les pose les uns à côté des autres sans laisser d’espace vide. Sur la surface restante, on pose, les uns à côté des autres sans laisser d’espace vide, des carreaux carrés dont le côté est le plus grand possible. On procède ainsi jusqu’à ce que le couloir soit entièrement carrelé.

Voici le plan du couloir :

140

cm

540 cm

� a) Quel est le plus grand côté possible pour un carreau carré ?

b) Combien peut-on en poser ?

c) Faire un plan du couloir à l’échelle 1/20 et représenter ces carreaux de carrelage.

d) Effectuer la division euclidienne de 540 par 140.

� a) Quelles sont les dimensions de la surface non carrelée ?

b) Pour carreler cette surface, quel est le plus grand côté possible pour un carreau carré ?

c) Combien peut-on en poser ?

d) Représenter ces carreaux de carrelage sur le plan de la question � c).

e) Effectuer la division euclidienne de 140 par 120.

� a) Quelles sont les dimensions de la surface non carrelée ?

b) Pour carreler cette surface, quel est le plus grand côté possible pour un carreau carré ?

c) Combien peut-on en poser ?

d) Représenter ces carreaux de carrelage sur le plan de la question � c).

e) Effectuer la division euclidienne de 120 par 20.

f) Pourrait-on carreler tout le couloir en utilisant uniquement des carreaux carrés de cette dimension ?

On dit que 20 est le plus grand commun diviseur de 140 et de 540. L’algo-rithme associé au pavage du rectangle est appelé algorithme d’Euclide.

Activité 2



Cours

1. Définition

Soit a et b deux entiers relatifs. On suppose que a et b ne sont pas tous les deux nuls.

Un entier qui divise a et b est appelé diviseur commun à a et b.

L’ensemble des diviseurs communs à a et b admet un plus grand élément appelé plus grand commun diviseur de a et b et noté PGCD (a, b).

Propriété 1 et Définition 1

On note D( )n l’ensemble des diviseurs dans � d’un entier relatif n.

L'ensemble D D( ) ( )a b∩ est alors l’ensemble des diviseurs communs à a et à b.

On admet que toute partie non vide et finie de �admet un plus grand élément.

Intéressons-nous aux éventuels éléments communs aux deux ensembles D( )a et D( ).b

Le nombre 1 divise a et divise b, 1∈ ∩D D( ) ( )a b donc D D( ) ( )a b∩ est une partie non vide de .�� Supposons a = 0 et b ≠ 0.

On a (0) ,D =� donc les diviseurs communs à 0 et à b sont les diviseurs de b, et le plus grand de ces diviseurs communs est |b|. Donc PGCD (0, b) = |b|.

� Supposons a b≠ ≠0 0et .

L’ensemble des diviseurs de a est fini car il est majoré par |a|, donc l’ensemble des diviseurs communs à a et à b est lui aussi fini (c’est un ensemble plus petit), donc il admet un plus grand élément. Ce plus grand élément est un diviseur à la fois de a et de b, et c’est le plus grand des diviseurs communs.

Soit a et b deux entiers naturels supérieurs ou égaux à 2.

Si, dans leur décomposition en produit de facteurs premiers, a et b n’ont pas de facteur premier commun, PGCD (a, b) = 1.

Sinon, le PGCD de a et de b est égal au produit des facteurs premiers communs de a et de b, chacun d’eux étant affecté du plus petit exposant figurant dans la décomposition de a et de b.

Propriété 2

C

Notation

Démonstration



Soit a p p pk k= × × ×1 21 2α α α... et b q q qk n= × × ×1 21 2β β β... la décomposition de a et de b en produit de facteurs premiers.

Notons d = PGCD (a, b).

� Démontrons le premier point.

Supposons que d ≠ 1.

Comme d divise a et d ≠ 1, la décomposition en produit de facteurs premiers de d comporte (au moins) un des pi . Comme d divise b, on en déduit que pi divise b. Donc les décompositions en produit de facteurs premiers de a et de b admettent un facteur premier commun. Cela prouve bien par contraposition le premier point.

� Démontrons le second point.

On suppose donc que d a b= PGCD ( , ) 2.≥

Soit δ un diviseur commun à a et b tel que : δ ≥ 2.

Comme δ divise a et δ ≠ 1, la décomposition en produit de facteurs premiers de δ est formée des facteurs premiers de a avec un exposant γ i tel que, pour tout 1≤ ≤i k , 0 < ≤γ αi i . Comme δ divise b et d ≠ 1, la décomposition en produit de facteurs premiers de d est formée des facteurs premiers de b avec un exposant χi tel que, pour tout 1≤ ≤i n, 0 < ≤χ βi i .Ainsi, la décomposition en produit de facteurs premiers de δ est formée des facteurs premiers communs à a et à b avec un exposant λ β αi i i≤ min( , ).Réciproquement, tous les entiers naturels dont la décomposition en produit de facteurs premiers vérifie ce qui précède sont un diviseur commun à a et b.

La décomposition en produit de facteurs premiers du plus grand diviseur d commun à a et b est donc formée des facteurs premiers communs à a et à b avec pour exposant min( , ).α βi i

Déterminer les PGCD de 2 070 et 368.

On cherche la décomposition de 2 070 et de 368 en produit de facteurs premiers :

2070 2 3 5 232= × × × et 368 2 234= ×

donc PGCD (2070, 368) = 2 23 46× = .

Pour tous a, b de Z non tous deux nuls :

PGCD (a, b) est un entier strictement positif ;

PGCD (a, a) = |a| ; PGCD (a, 1) = 1 ; PGCD (a, 0) = |a| ;

PGCD (a, b) = PGCD (b, a) = PGCD (|a|, |b|).

D D D( ) ( ) , )a b a b∩ = ( )PGCD( (conséquence de la proposition 2), ce qui signifie que les diviseurs commun à a et b sont les diviseurs de leur PGCD.

Démonstration

Exemple 1

Solution

Remarques



Pour tous entiers relatifs a et b non tous deux nuls et tout k de ,*�PGCD (ka, kb) = k PGCD (a, b).

Conséquence

Soit d le PGCD de a et de b, a'=ka, b'=kb et d’ le PGCD de a’ et de b’.

Comme d divise a et b, kd divise a’=ka et b'=kb. Ainsi, kd divise d’, le PGCD de a’ et de b’.

Donc, il existe un entier k’ tel que d’ = k’(kd).

Or, d’ divise ka et kb, donc k’kd divise ka et kb. Ainsi, k’d divise a et b et donc k’d divise d, le PGCD de a et de b. Ainsi, k’ = 1 et on a d’ = kd soit

PGCD (ka, kb) = k PGCD (a, b).

2. Propriétés

Si a divise b alors PGCD (a, b) = |a |.

Propriété 3

Si a divise b, tout diviseur de a est un diviseur de b et ainsi D D D( ) ( ) ( ).a b a∩ =Comme |a| est le plus grand élément de D( ),a PGCD (a, b) = |a |.

Soit a un entier naturel et b un entier naturel non nul et a = bq + r la division eucli-dienne de a par b.

Alors :

D D D D( ) ( ) ( ) ( )a b b a bq∩( ) = ∩ −( ) et donc

PGCD (a ; b) = PGCD (b ; a – bq) et ainsi PGCD (a ; b) = PGCD (b ; r).

Propriété 4

� Si d divise a et b alors d divise b et a – bq donc D D D D( ) ( ) ( ) ( ) .a b b a bq∩( ) ⊂ ∩ −( )

� Si d divise b et a – bq alors d divise b et (a – bq)+ bq = a donc D D D D( ) ( ) ( ) ( ) .b a bq a b∩ −( ) ⊂ ∩( )

Ainsi D D D D( ) ( ) ( ) ( ) .b a bq a b∩ −( ) = ∩( )D’où PGCD (a ; b) = PGCD (b ; a – bq).

Démonstration

Démonstration

Démonstration



Soit a et b deux entiers relatifs non tous les deux nuls.

Alors PGCD (a ; b) = PGCD (a – b ; b).

Propriété 5

On raisonne comme précédemment.

3. Recherche pratique de PGCD par l’algorithme d’Euclide

Euclide, mathématicien grec, environ 330 avant J.-C. – 275 avant J.-C.

Euclide est l’auteur de ce qu’on appelle Les Éléments d’Euclide, dans lesquels il donne un exposé magistral des mathématiques de son temps : théorème de Pythagore, construction du pentagone régulier à la règle et au compas, résultats d’arithmétique, démonstration de la formule donnant le volume d’une pyramide.

L’exposé d’Euclide a longtemps été considéré comme un modèle de rigueur logique : Euclide précise les propriétés qu’il admet (les axiomes), cite soigneuse-ment les théorèmes qu’il utilise et détaille chacune des étapes de ses démons-trations […]. Les Éléments sont à la base de l’enseignement de la géométrie élémentaire jusqu’à ces dernières années.

Cned, revue Diagonales

Soit a bet deux entiers tels que 0 < ≤b a.

Considérons l’algorithme :

Entrée : a, b

Traitement : Calculer le reste r de la division euclidienne de a par b

Tant que r ≠ 0,

a prend la valeur b et b prend la valeur r

Calculer le reste r de la division euclidienne de a par b

Fin du Tant que

Sortie : Afficher b.

Cet algorithme est appelé algorithme d’Euclide. En un nombre fini d’étapes, il permet de calculer le PGCD de a bet .

Propriété 6

Le PGCD de a et b est le dernier reste non nul obtenu dans la succession des divisions de l’algorithme d’Euclide.

Démonstration

Point historique

Remarque



On écrit les divisions euclidiennes successives : a bq r= +0 0 avec 0 0≤ <r b.

� Si r0 0= , on arrête à cette étape et PGCD (a, b) = b car b divise a.

� On suppose maintenant que r0 0≠ .

L’entier a prend la valeur b et b prend la valeur r0 : b r q r= +0 1 1 avec 0 1 0≤ <r r .

Si r1 0= , on arrête à cette étape et PGCD (b, r0 ) = PGCD ( r0 , r1 ) = r .0

Si r1 0≠ , b prend la valeur r0 et r0 prend la valeur r1 : r r q r0 1 2 2= + avec 0 2 1≤ <r r .

Si r2 0= , on arrête à cette étape et PGCD ( r r0 1, ) = PGCD ( r r1 2, ) = r1 car r2 =0.

Si r2 0≠ , r0 prend la valeur r1 et r1 prend la valeur r2 : r r q r1 2 3 3= + avec 0 3 2≤ <r r .

…

On construit ainsi une suite de restes r r r r0 1 2 3, , , , etc.

Si aucun reste n’est nul, la suite rn( ) est une suite strictement décroissante d’entiers naturels, ce qui est absurde puisqu’une telle suite ne peut exister.

Il existe donc un entier naturel n tel que rn+ =1 0 et rn ≠ 0 (car on a supposé que r0 0≠ ). Comme rn+ =1 0, l’algorithme s’arrête et comporte bien un nombre fini d’étapes.

De plus, comme rn+ =1 0,

r r r r r r rn n n n n= ( ) = ( ) = =+ −PGCD PGCD PGCD, , ... ,1 1 2 1(( )= ( ) = ( )= ( )

PGCD PGCD

PGCD

r r b r

a b1 0 0, ,

, .

Présentation pratique de l’algorithme

Calculons à nouveau PGCD (2070,368).

On écrit les divisions euclidiennes successives :

2070 5 368 230 ;

368 1 230 138 ;

230 1 138 92 ;

138 1 92 46 ;

92 2 46 0.//

= × += × += × +

= × += × + condition d’arrêt

Démonstration

Point méthode



PGCD et calculatrice

Les calculatrices disposent d’une fonction permettant le calcul du PGCD :Texas instrument Casio

MATH NUM gcd OPTN NUM GCD

Dans le chapitre 3, l’algorithme de recherche des coefficients de Bézout donne également le PGCD de deux entiers.

Exercices d’apprentissage

� Déterminer la décomposition en produit de facteurs premiers de 4 512 et 4 128.

� En déduire leur PGCD.

� Écrire sous la forme d’une fraction irréductible 41284 512

.

En utilisant l’algorithme d’Euclide, déterminer le PGCD de 1071 et 1029.

Déterminer tous les ensembles constitués de couples entiers naturels (a ; b) dont le PGCD est 50 et dont la somme est 600.

Sur tableur, construire une feuille de calcul permettant d’obtenir le PCGD de 1617 et 325 (sans utiliser la fonction PGCD).

Pour tout entier naturel n, on définit deux entiers a et b en posant :

a = 4n + 1 et b = 5n + 3.

On s’intéresse aux valeurs du PGCD de a et de b en fonction de n.

Remarque

D

Exercice 1

Exercice 2

Exercice 3

Exercice 4

Exercice 5



� Conjecture

a) Sur un tableur, créer trois colonnes donnant les valeurs de n, a et b pour n variant de 0 à 100.

b) Remplir la quatrième colonne avec les valeurs du PGCD de a et de b.

c) Quelles semblent être les valeurs possibles de PGCD(a, b) ?

d) En observant les résultats obtenus sur le tableur, comment pensez-vous pouvoir caractériser les valeurs de n telles que PGCD(a, b) = 7 ?

� Démonstrations

a) Démontrer la conjecture faite au 1. c.

b) En raisonnant par disjonction des cas, déterminer les valeurs de n telles que PGCD(a, b) = 7.




En utilisant un nouveau système de chiffrement, nous allons étudier la notion d’entiers premiers entre eux.

Pour débuter

Chiffrement de Hill

1. Principe du chiffrement

On fixe quatre entiers a, b, c et d qui constituent la clé du chiffrement.

Les lettres du message sont regroupées par blocs de 2. Chaque lettre est ensuite codée par un nombre compris entre 0 et 25 suivant son ordre dans l’alphabet (A 00, B 02, etc.).

On obtient une suite de nombres P P P P1 2 3 4, , , ...

On chiffre ensuite le bloc de deux nombres P P1 2 par le bloc C C1 2 de la manière suivante :

on effectue le calcul matriciel a bc d

P

P

⋅

1

2 ;

en remplaçant chaque coordonnée du vecteur obtenu par son reste dans la

division euclidienne par 26, on obtient C

C1

2

.

On procède de la même façon avec le bloc P P3 4...

Le texte sera chiffré par le texte où les nombres C C C C1 2 3 4... sont remplacés par les lettres correspondant à leur rang dans l’alphabet.

Prenons a = 3, b = 5, c = 6 et d = 17 et chiffrons le texte MATHEMATIQUE.

� Compléter le tableau suivant :

Lettre M A T H E M A T I Q U E

Rang Pi 12 0

A

B

Activité 3

Exemple

3 Entiers premiers entre eux



� a) Le premier bloc est (12 0). Indiquer les autres blocs.

b) Chiffrons ce bloc.

Écrivons «C

C3 56 17

120

(mod 26)1

2

=

⋅

» pour

C

C1

2

3 12 5 0 26

6 12 17 0 26

= × + ×= × + ×

(mod )

(mod ).

On a alors : C

C1

2

10

20

==

.

De la même façon, chiffrer les blocs suivants et compléter le tableau suivant :

Rang Ci 10 20

Lettre K U

2. Principe du déchiffrement

Le rang P P P P1 2 3 4... de chaque lettre du texte clair est obtenu par le calcul matri-ciel suivant :

«P

Pa bc d

C

C(mod 26).1

2

11

2

=

⋅

−»

On sait calculer la matrice a bc d

−1

.

Cette égalité « (mod 26) » signifie que l’on doit donc chercher, si elle existe, une

matrice à coefficients entiers dont le produit matriciel avec a bc d

nous

donne « modulo 26 », la matrice I2.

Prenons un exemple.

� Calculer

−

3 56 17

1

à l'aide d'une écriture utilisant des entiers.

� a) Compléter la table de multiplication par 21 modulo 26 ci-dessous :

21 0 2621 1 2621 2

× ≡× = ≡×

...... (mod )...... ...... (mod )

== ≡× = ≡

...... ...... (mod )

...... ...... (mod )26

21 3 26221 4 2621 5

× = ≡× = ≡

...... ...... (mod )...... ...... (modd )...... ...... (mod )...... .....

2621 6 2621 7

× = ≡× = ≡ .. (mod )

...... ...... (mod )

...... .

2621 8 2621 9

× = ≡× = ≡ ...... (mod )

...... ...... (mod )26

21 10 26× = ≡

21 11 2621 12

× = ≡× = ≡

...... ...... (mod )...... ...... (mood )...... ...... (mod )...... ..

2621 13 2621 14

× = ≡× = ≡ ..... (mod )

...... ...... (mod )

...

2621 15 2621 16

× = ≡× = .... ...... (mod )

...... ...... (mod )≡

× = ≡×

2621 17 2621 118 2621 19

= ≡× = ≡

...... ...... (mod )

...... ...... (mod22621 20 26

)...... ...... (mod )× = ≡



b) En déduire « un inverse de 21 modulo 26 » (c’est-à-dire un entier qui, multiplié

par 21, est égal à 1 modulo 26 et une matrice « 3 56 17

261

−mod . »

� a) Compléter la deuxième ligne du tableau ci-dessous.

Lettre chiffrée J W K T

Rang Ci 9

Rang Pi 7

Lettre claire H

b) En utilisant l’égalité « P

P

C

C1

2

1

25 17 5

6 326

= −−

⋅

(mod )) », com-

pléter la troisième ligne du tableau et déchiffrer le message JWKT.

3. À l’aide du tableur pour chiffrer

� Préparer la feuille de calcul suivante :

On utilise la fonction « =CODE » du tableur pour obtenir le code ASCII d’une lettre puis on soustrait 65 pour obtenir son rang dans l’alphabet. (Cf. Prérequis C de la séquence 1.)

� Compléter la ligne 5.

� Compléter les cellules B6 et C6.

� Compléter les cellules B7. On pourra utiliser la fonction « =MOD » du tableur.

� Compléter les cellules B8. On pourra utiliser la syntaxe « =CAR(B7+65) » pour obtenir :

� Copier-glisser les formules.



4. À l’aide du tableur pour déchiffrer

� Sur la même feuille de calcul, ajouter les informations suivantes :

� Compléter la ligne 13.

� Calculer l’inverse de 21 modulo 26. Pour cela, effectuer le produit modulo 26 de chacun des entiers de 1 à 25 par 21. Saisir en Q3 « = MOD(O3*$Q$1;26) » et copier-glisser jusqu’en Q27.

Retenir celui qui donne un produit égal à 1. Saisir en R3 « =SI(Q3=1;O3;»» ) » et copier-glisser jusqu’en R27.

Afficher l’inverse de 21 modulo 26 en faisant la somme des éléments de R3 à R27. Saisir en R28 « =SOMME(R3;R27) ».

On obtient :

� Compléter les cellules B14 et C14.



� Compléter les cellules B15 puis B16. On obtient :

� Copier-glisser les formules.

5. Modification de la clé

� Modifier la feuille de calcul précédente en prenant successivement :

a) a = 3, b = 9, c = 2 et d = 20.

b) a = 7, b = 8, c = 4 et d = 6.

c) a = 12, b = 8, c = 4 et d = 5.

d) a = 10, b = 5, c = 3 et d = 5.

� En regardant dans chaque cas le nombre ad – bc, conjecturer une condition nécessaire pour que le calcul de l’inverse modulo 26 soit possible et, ainsi, le déchiffrement du message.

Combinaison linéaire

Pour stocker des matériaux, une entreprise dispose au maximum de 9 petits conteneurs et de 6 grands conteneurs. Un petit conteneur peut contenir 10 m3 de matériaux et un grand 15 m3.

L’entreprise veut stocker 120 m3.

On note x le nombre de petits conteneurs nécessaires et y celui de grands.

� Justifier que x et y vérifient le système suivant :

xxyy

y x

090

6

23

8

≥≤≥≤

≥−

+

.

Activité 4



� Représenter dans un repère la zone du plan définie par le système ci-dessus.

� Donner la liste de toutes les solutions possibles pour l’entreprise. Quelle est celle qui nécessite le moins de conteneurs ?

Cours

1. Définition

Entiers premiers entre eux

Soit a et b deux entiers relatifs non nuls.

Les entiers a et b sont premiers entre eux lorsque PGCD (a, b) = 1.

Définition 2

Il ne faut pas confondre nombres premiers et nombres premiers entre eux.

Soit a et b deux entiers relatifs non nuls. On note PGCD (a, b) = d et a’ et b’ les entiers tels que a = da’ et b = db’.

Alors on a PGCD (a’, b’ ) = 1.

Propriété 7

Supposons que PGCD( , ) ,′ ′ = ′ ≠a b d 1 alors a’ = d’a’’ et b’ = d’b’’ où a’’ et b’’ sont des entiers.

Par conséquent, a = dd’a’’ et b = dd’b’’ et ainsi dd ′ (qui est strictement supérieur à d) est un diviseur de a et de b, ce qui contredit PGCD (a, b) = d.

Donc PGCD (a’, b’ ) = 1.

2. Théorème de Bézout

a) Le théorème

Étienne Bézout (1730-1783)

Bézout est d’une famille de magistrats de Nemours. La lecture d’Euler décide Bézout à ne pas suivre la voie familiale ; ses premiers mémoires de mathéma-tiques lui donnent accès à l’Académie des sciences en 1758.

C’est en 1763 que la carrière de Bézout prend une nouvelle orientation. Bézout est chargé par le duc de Choiseul d’être l’examinateur des Gardes du pavillon et de la marine. Le poste est important : il décide de la carrière de nombreux

C

Remarque

Démonstration

Point historique



jeunes militaires. Il est lucratif : Bézout écrit son propre cours de mathématiques en 6 volumes (arithmétique, géométrie et trigonométrie, algèbre, mécanique, applications de la mécanique, traité de navigation). En 1768, Bézout accroît son influence en devenant examinateur des élèves de l’artillerie. Il écrit un nouveau Cours complet de mathématiques à l’usage de la marine et de l’artillerie, qui aura un succès considérable. Napoléon Bonaparte a connu les livres de Bézout quand il était élève à l’école de Brienne. Il continuait à les étudier dans son exil de Sainte-Hélène.


Théorème de Bézout


On a PGCD (a, b) = 1 si, et seulement si, il existe deux entiers relatifs u et v tels que au + bv = 1.

Théorème

La relation au + bv = 1 est appelée relation de Bézout.

On rappelle que toute partie non vide de �admet un plus petit élément.

� Supposons que PGCD (a, b) = 1.

Considérons l’ensemble E des entiers naturels non nuls s’écrivant sous la forme aU + bV où U et V sont des entiers relatifs.

L’ensemble E est une partie non vide de ,� il possède donc un plus petit élément. Notons n0 le plus petit élément de E, n0 est de la forme n au bv0 = + .

La division euclidienne de a par n0 donne :

a n q r au bv q r= + = + +0 ( ) avec 0 0≤ <r n .

On a donc r a au bv q a u b vq= − + = − + −( ) ( ) ( )1 donc r est de la forme aU + bV.

Si r ≠ 0, comme r n< 0 et que r est de la forme aU + bV, r est un élément de E strictement plus petit que n0. Il y a contradiction, on en déduit que r = 0.

Donc n0 divise a. De la même façon, n0 divise b.

L’entier n0 est donc un entier naturel diviseur commun à a et à b. Ces entiers sont premiers entre eux donc n0 1= et, ainsi, il existe des entiers relatifs u et v tels que 1= au + bv.

� Réciproque

Supposons qu’il existe des entiers u et v tels que au + bv = 1.

Si d est le PGCD de a et b, il divise a et b donc d divise au + bv soit d divise 1. Ainsi d = 1 (car d est positif).

On a donc PGCD (a, b) = 1, c’est-à-dire que a et b sont premiers entre eux.

Remarque

Démonstration



Déterminer les coefficients de la relation de Bézout

Par tâtonnements !

Soit a = 4 et b = 7.

Trouver trois couples (u, v) tels que au + bv = 1.

On cherche un multiple de 4 et un multiple de 7 qui diffèrent de 1.

On a 4 2 8 7 1 7× = × =et donc 2 4 1 7 1× + − × =( ) . Ainsi, u = 2 et v = −1 conviennent.

On a 4 9 36 7 5 35× = × =et donc 9 4 5 7 1× + − × =( ) . Ainsi, u = 9 et v = −5 conviennent.

On a 4 5 20 7 3 21× = × =et donc − × + × =5 4 3 7 1. Ainsi, u = −5 et v = 3 conviennent.

Le couple (u, v) n’est pas unique.

À l’aide d’un algorithme

� En utilisant l’algorithme d’Euclide, démontrer que 392 et 33 sont premiers entre eux.

� En déduire deux entiers relatifs u et v tels que 392u + 33v = 1.

� On écrit les divisions euclidiennes successives de l’algorithme d’Euclide :392 11 33 29

33 1 29 4

29 7 4 1

4 4 1 0//

= × += × +

= × += × +

donc PGCD(392, 33) = 1 et, ainsi, 392 et 33 sont premiers entre eux.

� Pour déterminer u et v, on écrit chaque reste en repartant de la fin :

29 7 4 1= × + donc 1 29 7 4= − × ,

33 1 29 4= × + donc 4 33 1 29= − × ,

392 11 33 29= × + donc 29 392 11 33= − × ;

puis on reporte chaque reste :

1 29 7 4= − × ;

on remplace 4 :

1 29 7 33 1 29

8 29 7 33

= − × − ×= × − ×

( )

;

on remplace 29 : 1 8 392 11 33 7 33

8 392 95 33

= × − × − ×= × − ×

( )

.

Ainsi, 1 8 392 95 33= × − × donc u = 8 et v = −95 conviennent.

Point méthode

Exemple 2

Solution

Remarque

Exemple 3

Solution



b) Coefficients de la relation de Bézout et TICE

Soit a et b deux entiers relatifs non nuls premiers entre eux avec a > b.

On souhaite écrire un algorithme donnant un couple d’entiers relatifs (u ; v) tels que au + bv = 1.

� Langage naturel

Entrées a ; b

Initialisation u prend la valeur 1, v prend la valeur 0

x prend la valeur 0, y prend la valeur 1

c prend la valeur 0, d prend la valeur 0

Traitement Tant que b >0

q prend la valeur Partie Entière (a / b) ; r prend la valeur a – bq ;

c prend la valeur u ; d prend la valeur v ;

u prend la valeur x ; v prend la valeur y ;

x prend la valeur c – xq ; y prend la valeur d – yq ;

a prend la valeur b ; b prend la valeur r ;

Fin du Tant que

Sortie Afficher a, u et v



� Calculatrice

Texas Instrument Casio

Exemple :

3. Théorème de Gauss

a) Théorème de Gauss

Karl Friedrich Gauss (1777-1855)

Gauss naît dans une famille très pauvre à Brunswick [en Allemagne] à 150 kilo-mètres de Hambourg. Il aimait à raconter des histoires de son enfance à ses

Point historique



proches. Il avait appris à lire et compter seul vers 3 ans, questionnant les adultes autour de lui. À 7 ans, il est remarqué par son instituteur pour avoir calculé ins-tantanément la somme des nombres de 1 à 100, expliquant qu’il suffisait de grouper les nombres en 50 paquets de somme 101 : 100+1, 99+2, 98+3, etc. Il a la chance de rencontrer un jeune mathématicien qui le guide (il a une dizaine d’années) dans ses premières lectures mathématiques. Le soutien financier du duc de Brunswick lui permet de continuer ses études.

Les découvertes de Gauss en arithmétique se succèdent alors rapidement et Gauss publie (il a 24 ans) en 1801 ses Recherches arithmétiques (en latin).

Il est impossible de décrire l’ensemble de l’œuvre de Gauss. Toute sa vie, Gauss poursuivra ses travaux théoriques et pratiques en mathématiques (géométrie des surfaces, arithmétique, analyse numérique), en astronomie, en statistique (loi normale et courbe en cloche), en topographie (cartographie de Hanovre), en physique et géologie (magnétisme), en économie, etc. Dans tous ces domaines, la contribution de Gauss est exceptionnelle et c’est à juste titre qu’on l’a appelé Prince des mathématiciens.


Théorème de Gauss

Soit a, b et c des entiers.

Si a divise le produit bc et si a est premier avec b alors a divise c.

Théorème 2

Si a est premier avec b, d’après le théorème de Bézout, il existe des entiers relatifs u et v tels que au + bv = 1.

En multipliant par c, on obtient : acu + cbv = c.

Or, a divise acu et, comme a divise bc, a divise bcu.

Ainsi, a divise acu + cbv c’est-à-dire a divise c.

Si deux entiers a et b premiers entre eux divisent un entier c, alors ab divise c.

Si un nombre premier p divise un produit ab, alors p divise a ou p divise b.

Conséquences

� Comme c est divisible par a et b, il existe des entiers k et k’ tels que c = ka = k’b.Comme a divise c, a divise k’b.

Comme a et b sont premiers entre eux, d’après le théorème de Gauss, a divise k’, donc il existe un entier n tel que k’ = na.

On en déduit que c = k’b = nab, donc que c est divisible par ab.

� Soit un nombre premier p divisant un produit ab.

Si p divise a, la propriété est démontrée.

Démonstration

Démonstration



Si p ne divise pas a, alors p et a sont premiers entre eux. Comme p divise le pro-duit ab, d’après le théorème de Gauss, p divise b.

b) Applications

Résolution d’équations diophantiennes

Une équation diophantienne est une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également entières.

� Équation du type ax = by d’inconnues x et y appartenant à �

Déterminer les entiers x et y tels que 4x = 3y.

L’entier 4 divise 3y et 4 est premier avec 3. D’après le théorème de Gauss, 4 divise y. Ainsi, il existe un entier k tel que y = 4k.

On a donc 4 3 4x k= × d’où x = 3k.

Réciproquement, si x = 3k et y = 4k,

4 4 3 12x k k= × = et 3 3 4 12y k k= × = donc on a bien 4x = 3y.

Les solutions de cette équation sont les couples (3k ; 4k) avec k .∈�� Équation du type ax + by = c d’inconnues x et y appartenant à �

� Déterminer les entiers x et y tels que 2x + 3y = 1.


� On remarque que 2 1 3 1 1× − + × =( ) donc le couple −( )1 1; est solution de cette équation.

De plus, 2 3 1x y+ = équivaut à 2 3 2 1 3 1x y+ = × − + ×( )

équivaut à 2 1( )x + = 3 1( ).− +ySupposons que (x ; y) soit solution de 2x + 3y = 1 alors 3 divise 2 1( )x + . Comme 3 est premier avec 2, d’après le théorème de Gauss, 3 divise (x + 1).

Donc il existe un entier k tel que x + 1 = 3k soit x k= − +1 3 .

En reportant la valeur de x dans 2 1 3 1( ) ( ),x y+ = − + on obtient

2 3 3 1× = − +k y( ) soit − + =y k1 2 , soit y k= −1 2 .

Réciproquement, si x k= − +1 3 et y k= −1 2 ,

2 3 2 1 3 3 1 2

2 6 3 6

x y k kk k

+ = − + + −= − + + −

( ) ( )

on a bien 2 3 1x y+ = .

Les solutions de cette équation sont les couples − + −( )1 3 1 2k k; avec k .∈�� Comme 2 1 3 1 1× − + × =( ) , en multipliant par 5 on a : 2 5 3 5 5× − + × =( ) ,

donc le couple (–5 ; 5) est solution de cette équation.

De plus, 2 3 5x y+ = équivaut à 2 3 2 5 3 5x y+ = × − + ×( ) équivaut à 2 5 3 5( ) ( ).x y+ = − +

Exemple 4

Solution

Exemple 5

Solution



Supposons que (x ; y) soit solution de 2x + 3y = 5 alors 3 divise 2 5( )x + . Comme 3 est premier avec 2, d’après le théorème de Gauss, 3 divise (x + 5).

Donc il existe un entier k tel que x + 5 = 3k soit x k= − +5 3 .

En reportant la valeur de x dans 2 5 3 5( ) ( ),x y+ = − + on obtient

2 3 3 5× = − +k y( ) soit − + =y k5 2 ou encore y k= −5 2 .

Réciproquement, si x k= − +5 3 et y k= −5 2 ,

2 3 2 5 3 3 5 2

10 6 15 6

x y k kk k

+ = − + + −= − + + −

( ) ( )

on a bien 2 3 5x y+ = .

Les solutions de cette équation sont les couples − + −( )5 3 5 2k k; avec Zk .∈

Remarquons que l’on aurait aussi pu raisonner comme au 1 en remarquant que (1 ; 1) était solution de cette équation diophantienne.

Petit théorème de Fermat

Pierre de Fermat

Il a vécu de 1601 à 1665. Originaire de la région de Toulouse, il a une brillante carrière de magistrat dans cette ville. Cela lui laisse peu de temps pour faire, en amateur, des recherches en mathématiques. La vie scientifique commence à s’animer en France dans les années 1630 sous l’impulsion du Père Mersenne qui écrit inlassablement aux uns et aux autres pour les informer de leurs recherches respectives. C’est ainsi que Fermat prend contact avec les autres grands scienti-fiques de son époque : Descartes, Desargues, Pascal.

Dans tous les domaines qu’il étudie, il apporte des contributions importantes : il participe à la fondation des calculs différentiel et intégral en donnant, par exemple, une méthode nouvelle de recherche de maxima et minima et en 1654, un échange célèbre de lettres avec Blaise Pascal est à l’origine du calcul des probabilités.

Mais il est un domaine où personne n’est capable de rivaliser avec Pierre de Fermat, c’est celui de l’arithmétique. Les questions qu’il pose sont profondes et d’une très grande difficulté. Il donnera heureusement, en 1659, un aperçu de ses méthodes.

L’un des problèmes que s’est posé Fermat a une histoire extraordinaire : montrer qu’un entier strictement positif qui est une puissance n-ième d’entier ne peut être, pour n > 2, une somme de deux puissances n-ièmes d’entiers strictement posi-tifs, autrement dit, l’équation an + bn = cn n’admet pas de solution en nombres entiers strictement positifs. Ce problème, Fermat a cru l’avoir résolu, mais on en doute, tellement les mathématiciens des siècles suivants ont « séché » dessus. Ce n’était pas toujours en pure perte, car de belles théories, utiles pour les mathéma-tiques, ont été construites pour essayer de le résoudre. Mais le problème résistait toujours. Dans les années 1970-1980, le problème de Fermat a été réinterprété : on a montré que ce serait une conséquence d’une propriété très générale.

C’est en 1993-1994 que le mathématicien anglais Andrew Wiles a démontré cette propriété. Du coup, le théorème de Fermat était enfin prouvé. Pour une fois,

Point historique



tous les journaux ont parlé de mathématiques. Ce théorème a un énoncé d’une grande simplicité, compréhensible par tout lycéen. A-t-il un intérêt pratique ? Pour le moment aucun, mais les mathématiques qu’il a contribué à développer en ont certainement un !


Le théorème suivant n’est pas une connaissance exigible du programme.

Soit n un entier.

Si p est un nombre premier ne divisant pas n, alors n pp− ≡1 1[ ].

Théorème 3

Si p est un entier naturel premier et n est un entier naturel alors n n pp ≡ [ ].

Corollaire

La démonstration du théorème et de son corollaire font l’objet de l’exercice I.


Les nombres suivants sont-ils premiers entre eux ?

� 171 et 760

� 2635 et 4 807

� Déterminer les entiers x et y tels que 55x = 9y.

� Déterminer les entiers x et y tels que 21x = 56y.



À l’aide du petit théorème de Fermat, montrer que, pour tout entier n, n n7 − est divisible par 21.

On se propose de déterminer l’ensemble � des entiers relatifs n vérifiant le sys-

tème : n

n

≡≡

9 17

3 5

[ ]

[ ].

Démonstration

D

Exercice 6

Exercice 7

Exercice 8

Exercice 9

Exercice 10



� Recherche d’un élément de �

On désigne par (u ; v) un couple d’entiers relatifs tel que 17 u + 5 v = 1.

a) Justifier l’existence d’un tel couple (u ; v).

b) On pose n u v0 3 17 9 5= × + × .

Démontrer que n0 appartient à �.

c) Donner un exemple d’entier n0 appartenant à �.

� Caractérisation des éléments de �

a) Soit n un entier relatif appartenant à �.

Démontrer que n n− ≡0 0 85[ ].

b) En déduire qu’un entier relatif n appartient à � si, et seulement si, il peut s’écrire sous la forme n = 43 + 85k où k est un entier relatif.

� Application

Zoé sait qu’elle a entre 300 et 400 jetons.

Si elle fait des tas de 17 jetons, il lui en reste 9.

Si elle fait des tas de 5 jetons, il lui en reste 3.

Combien a-t-elle de jetons?

Le but de l’exercice est d’étudier certaines propriétés de divisibilité de l’entier 4 1n − , lorsque n est un entier naturel.

� Démontrer que, pour tout entier naturel n, 4n est congru à 1 modulo 3.

� Prouver, à l’aide du petit théorème de Fermat, que 4 128 − est divisible par 29.

� Pour 1 4≤ ≤n , déterminer le reste de la division de 4n par 17. En déduire que, pour tout entier k, le nombre 4 14k − est divisible par 17.

� Pour quels entiers naturels n le nombre 4 1n − est-il divisible par 5 ?

� À l’aide des questions précédentes, déterminer quatre diviseurs premiers de 4 128 − .

Exercice 11



4Retour sur les nombres premiers et application au chiffrement RSA


La notion de nombre premier est une notion de base en arithmétique. Nous allons observer quelques résultats sur la répartition des nombres premiers et une des applications des nombres premiers dans un système de chiffrement utilisé actuel-lement.

En exercices, nous étudierons deux familles de nombres liées aux nombres pre-miers.

Pour débuter

Crible de Matiiassevitch

Youri Matiiassevitch, mathématicien russe, né en 1947.

� a) À l’aide d’un logiciel de géométrie, représenter dans un repère orthonormé la parabole � d’équation y x= 2.

b) Placer tous les points de � d’abscisse entière n avec − ≤ ≤7 7n , n ≠ 0 et n ≠ 1.

c) Relier par un segment les points de la parabole d’abscisse entière positive aux points de la parabole d’abscisse entière négative.

d) Sur l’axe des ordonnées, donner la liste des points vérifiant les conditions suivantes :

l’ordonnée est supérieure ou égale à 5 ;

l’ordonnée est inférieure ou égale à 25 ;

qui ne sont pas point d’intersection d’un segment tracé à la question précédente et de l’axe des ordonnées.

A

B

Activité 5



e) Quelle conjecture peut-on formuler sur l’ordonnée des points de la figure précédente ?

� Démonstration de cette conjecture.

Soit m et n où m n deux entiers naturels.

a) Déterminer l’équation de la droite (MN) où M(m ; m2 ) et N(n ; n2 ).

b) Que vaut l’ordonnée à l’origine de la droite (MN) ?

c) Justifier que l’ordonnée des points de la liste correspond à des nombres premiers.

d) Le point de l’axe des ordonnées d’ordonnée 22 est dans la liste. Expliquer.

Le crible d’Ératosthène (vu à la séquence 1) permet également de déterminer tous les nombres premiers inférieurs ou égaux à un entier N.

Répartition des nombres premiers

Cette activité peut être traitée même si la séquence du tronc commun sur la fonction logarithme n’a pas encore être étudiée.

� a) Écrire un algorithme qui, prenant en entrée un nombre N, affiche en sortie tous les nombres premiers inférieurs ou égaux à N (N ≥ 2 ).

b) Modifier l’algorithme précédent pour permettre l’affichage des nombres premiers compris entre N et M.

c) Combien y a-t-il de nombres premiers entre 50 et 60 ? entre 850 et 860 ? entre 1 850 et 1 860 ? entre 2 850 et 2 860 ?

d) Les nombres premiers sont-ils répartis régulièrement ?

Remarque

Activité 6



� Le nombre de nombres premiers inférieurs ou égaux à un entier n est noté π ( ).n

Compléter le tableau suivant :

N π ( )nnnln( )

10 4

100 25

1000 168

10 000 1 229

105 9 592

106 78 498

107 664 579

108 5 761 455

109 50 847 534

1010 455 052 511

1011 4 118 054 813

1012 37 607 912 018

1013 346 065 536 839

1014 3 204 941 750 802

1015 29 844 570 422 669

1016 279 238 341 033 925

1017 2 623 557 157 654 233

1018 24 739 954 287 740 860

1019 234 057 667 276 344 607

1020 2 220 819 602 560 918 840

Que constate-t-on ?

� On définit le nombre n! par n n! ...= × × × ×1 2 3 et on lit « factoriel n ».

a) Sans effectuer de calcul, justifier que chacun des nombres des deux listes suivantes n’est pas premier :

Liste A : 5! + 2 ; 5! + 3 ; 5! + 4 ; 5! + 5.

Liste B : 6! + 2 ; 6! + 3 ; 6! + 4 ; 6! + 5 ; 6! + 6.

Qu’ont de particulier les quatre nombres de la liste A les uns par rapport aux autres ?

Qu’ont de particulier les cinq nombres de la liste B les uns par rapport aux autres ?

b) Sur le même principe, créer une liste de 20 nombres consécutifs ne compor-tant aucun nombre premier.



Cours

Les résultats évoqués dans cette partie ne sont pas exigibles mais la sensibilisa-tion à ces notions est au programme.

1. Répartition des nombres premiers

L’activité 6 a permis d’émettre des conjectures sur la répartition des nombres premiers. Voici quelques résultats :

il y a une infinité de nombres premiers (voir séquence 1) ;

la répartition des nombres premiers est irrégulière ;

il y a des listes de nombres entiers consécutifs aussi longue que l’on veut qui ne contiennent pas de nombre premiers ;

pour de grandes valeurs de n, le nombre n( )π (nombre de nombres premiers

inférieurs ou égaux à n) est proche de nnln( )

(loi de raréfaction des nombres

premiers).

2. Utilisation des nombres premiers : chiffrement à clé publique RSA

Rivest Shamir Adleman (presque toujours abrégé en RSA) est un algorithme de chiffrement très utilisé pour échanger des données confidentielles sur Internet, notamment dans le commerce électronique. Cet algorithme a été décrit en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman.

Le fonctionnement de RSA repose sur une idée simple : il est facile de multiplier deux grands nombres premiers entre eux alors qu’il est très difficile de retrouver les facteurs premiers du nombre ainsi obtenu.

RSA est un algorithme de chiffrement à clé publique. Cela signifie que la clé de codage et l’algorithme de calcul ne sont pas cachés : n’importe quel émetteur peut envoyer un message au destinataire. Par contre, seul le destinataire peut le déchiffrer grâce à une clé de décodage privée qu’il tient secrète.

Le système est dit dissymétrique car les clés de codage et décodage sont diffé-rentes.

C



Le protocole du RSA repose sur le théorème suivant :

Théorème du RSA

Soit p et q deux nombres premiers distincts et supérieurs ou égaux à 3. On pose n = pq.

Si le nombre e est un entier premier avec m p q= − −( )( ),1 1 alors il existe un entier d strictement positif tel que ed p q≡ − −1 1 1mod ( )( ) et, pour cet entier d et un entier naturel A quelconque, on a : A A ned ≡ mod( ).

Théorème 4

� Soit e un entier premier avec m. Montrons l'existence d’un entier d strictement positif tel que ed p q≡ − −1 1 1mod ( )( ).

Comme e est premier avec m p q= − −( )( ),1 1 d’après le théorème de Bézout, il existe un couple d’entiers u v( ; )0 0 tel que eu p q v0 01 1 1+ − − =( )( ) .

On a eu0 – 1 = (p – 1)(q – 1)v0 donc eu0 1 mod (p – 1)(q – 1).

Mais on veut : ed 1 mod (p – 1)(q – 1) avec d > 0, on peut remplacer u0 par d = u0 + k(p – 1)(q – 1) où k est un entier relatif sans rien changer à la congruence modulo (p – 1)(q – 1) On choisit donc k de telle sorte que :

d = u0 + k(p – 1)(q – 1) > 0.

Posons v v ke= − +0 .

On a alors :eu p q v0 01 1 1+ − − =( )( ) ⇔ e d k p q p q v ke− − −( )+ − − − + =( )( ) ( )( )( )1 1 1 1 1

⇔ ed ek p q v p q

ke p q

− − − − − − +

− − =

( )( ) ( )( )

( )( )

1 1 1 1

1 1 1

⇔ ed v p q− − − =( )( )1 1 1

⇔ ed v p q1 ( 1)( 1)= + − − (*).

Ainsi, ed p q≡ − −1 1 1mod ( )( ).

On a trouvé un entier d strictement positif qui vérifie ed p q≡ − −1 1 1mod ( )( ).

� Montrons que pour tout entier naturel A, on a A A ned ≡ mod( ).

Si p divise A alors A p≡ 0 mod( ) et A ped ed≡ ≡0 0 mod( ) donc A A ped ≡ mod( ).

Si p ne divise pas A, comme p est un nombre premier, p est premier avec A.

On peut alors utiliser le petit théorème de Fermat et A pp− ≡1 1mod( ).

Ce qui implique :

A pp

v p q v q( )( ) ( ) mod( )

mod( ).

− − −≡≡

1 1 11

1

En utilisant l’égalité (*), on a A ped − ≡1 1mod( ) et en multipliant par A, on a A A ped ≡ mod( ).

Démonstration



Donc, pour tout entier naturel A, on a A A ped ≡ mod( ).

On raisonne de la même façon avec q et on obtient, pour tout entier naturel A, on a A A qed ≡ mod( ).

Comme A A ped ≡ mod( ) et A A qed ≡ mod( ), cela signifie que A Aed − est un multiple de p et un multiple de q. Comme p et q sont deux nombres premiers, cela implique que A Aed − est un multiple de pq = n et donc que A A ned ≡ mod( ).

Alice, l’émettrice, souhaite envoyer un message chiffré à Bob, le destinataire.

Création de la clé privée

Bob se donne un quadruplet de nombres (p ; q ; e ; d ) tel que : p et q sont deux nombres premiers ; e est un entier premier avec le produit ( )( )p q− −1 1 et d est un entier strictement positif tel que ed p q≡ − −1 1 1mod ( )( ). L’entier d constitue la clé privée tenue secrète par Bob.

Création de la clé publique

On pose n = pq. Bob rend public le couple (n ; e) qui constitue la clé publique.

Codage

Alice veut transmettre une information sous la forme d’un nombre A à Bob avec A < n (si A n≥ , elle transmet plusieurs nombres). Pour cela, elle calcule B A ne= mod( ) et envoie le nombre B à Bob.

Décodage

Pour décoder B, Bob calcule B A A nd ed≡ ≡ mod( ) , ce qui lui redonne A d’après le théorème du RSA.

Création des clés

Prenons p = 31 et q = 47 donc ( )( )p q− −1 1 = 1380.

Prenons e = 71. On a bien PGCD e p q, ( )( ) .− −( ) =1 1 1

Prenons d = 311. On a bien ed = = × +22081 16 1380 1 donc

ed p q≡ − −1 1 1mod(( )( )).

On a : n = 1457.

Codage

Alice veut transmettre le message « RSA » à Bob ; elle dispose de la clé (1457 ; 71).

Elle transforme chaque lettre en un nombre suivant le code A --> 01, B --> 02, etc.

Ainsi, elle veut transmettre le code A = 181901. Elle le coupe en deux nombres inférieurs à n, par exemple A1 181= et A2 901= .

Elle doit calculer suivant Ae1

711457 181 1457mod( ) mod( ).≡

Principe

Exemple



En utilisant la compatibilité des congruences avec les puissances, en élevant chaque égalité au carré et en réduisant, on obtient :

181 707 1457

181 98 1457

2

4

≡

≡

mod( )

mod( )

;

;

181 8628 ≡ modd( )

mod( )

mod(

1457

181 1431 1457

181 676 145

16

32

;

;≡

≡ 77

181 935 145764

)

mod( )

;

;≡

puis 181 181 935 98 1457 1296 145764 4 68+ = ≡ × ≡mod( ) mod( ) ;

181 181 1296 707 1457 1276 145768 2 70+ = ≡ × ≡mod( ) mod( ) ;

181 181 1276 181 1457 750 145770 1 71+ = ≡ × ≡mod( ) mod( ).

Donc 181 750 145771 ≡ mod( ) ;

Elle procède de même avec A2 901= et elle obtient 901 64 145771 ≡ mod( ).

Alice transmet le code 750 064 à Bob.

Décodage

Bob reçoit le code 750 064.

Il doit calculer 750 1457311 mod( ). En procédant comme Alice, il obtient :

750 98 1457

750 862 1457

750 143

2

4

8

≡

≡

≡

mod( )

mod( )

mo

;

;

dd( )

mod( )

mod(

1457

750 676 1457

750 935 1457

16

32

;

;≡

≡ ))

mod( )

mod( )

;

;

;

750 25 1457

750 625 1457

750

64

128

≡

≡2256 149 1457≡ mod( ) ;

puis 750 750 149 935 1457 900 1457256 32 288+ = ≡ × ≡mod( ) mod( ) ;

750 750 900 676 1457 831 1457288 16 304+ = ≡ × ≡mod( ) mod( ) ;

750 750 831 862 1457 935 1457304 4 308+ = ≡ × ≡mod( ) mod( ) ;

750 750 935 98 1457 1296 1457308 2 310+ = ≡ × ≡mod( ) mod( ) ;

750 750 1296 750 1457 181 1457310 1 311+ = ≡ × ≡mod( ) mod( ).

Donc 750 181 1457311 ≡ mod( ).

Il procède de même avec 064 et obtient : 64 911 1457311 ≡ mod( ).

Le code 18 19 11 donne bien les lettres R, S et A.



On utilise, en réalité, de très grand nombres n, p et q. L'inviolabilité du système en dépend. La sécurité du RSA réside en la difficulté de factoriser n en produit de deux nombres premiers : si l’on réussit à factoriser n, le calcul de d étant aisé, le code est facile à briser.


On se donne les entiers premiers p = 13 ; q = 31 et e = 37. Chaque lettre sera remplacée par son rang dans l’alphabet (A --> 001 ; B --> 002, etc.) et on fera des blocs de trois chiffres.

� Calculer la clé privée du chiffrement RSA d avec 0 ≤ ≤d n.

� Calculer la clé publique.

� Chiffrer le message « TOM ».

� Déchiffrer le message « 005 054 001 ».

Nombres de Fermat

Les nombres de Fermat sont les nombres de la forme Fnn

= +2 12 avec Nn .∈Au XVIIe siècle, Pierre de Fermat émit la conjecture que ces nombres étaient premiers.

Définition

Partie A

� a) En utilisant le tableur et une liste des nombres premiers inférieurs à 100 000, écrire la liste des entiers 0 19≤ ≤k tels que 2 1k + soit un nombre premier.

b) Émettre une conjecture.

� a) Pour x ≠ 1, écrire plus simplement ( ) ( ) ( ) ... ( ) .− + − + − + + − −x x x x k0 1 2 1

b) Pour x ≠ 1, en déduire une factorisation de 1− −( ) .x k

� a) Pour x ≠ 1, montrer que si k est impair alors xk +1 est divisible par x + 1.

b) Pour x ≠ 1, en déduire que si k n’est pas une puissance de 2 alors xk +1 n’est pas premier.

� À quelle famille appartiennent les nombres de la forme 2 1m + qui sont pre-miers ?

Partie B

� Vérifier que F F F F F0 1 2 3 4; ; ; et sont des nombres premiers.

� Qu’en est-il de F5 ? Que dire de la conjecture de Fermat ?

Remarque

D

Exercice 12

Exercice 13



Partie C

� Vérifier que pour tout entier naturel n, F Fn n+ = − +121 1( ) et en déduire que

F F Fn n n+ − = −1 2 2( ).

� Montrer par récurrence que F F F Fn n+ − = × × ×1 0 12 ... .

� Soit n < n’. Montrer qu’un diviseur commun de F Fn net divise 2.

� En déduire que deux nombres de Fermat distincts sont premiers entre eux.

Nombres de Carmichael

On sait, par le petit théorème de Fermat, que pour tout nombre premier p et tout entier a, a a pp ≡ [ ]. La réciproque de ce résultat, appelée test de Fermat, est fausse, c’est-à-dire qu'il existe des nombres vérifiant les congruences précé-dentes sans qu’ils soient premiers : ce sont les nombres de Carmichael.

Un nombre de Carmichael est un nombre entier n (n > 1) qui n’est pas premier et pour lequel a nn− ≡1 1[ ]pour tout entier a.

Soit n un nombre de carmichael.

� Soit p un facteur premier de n. En utilisant p p nn ≡ [ ], montrer que p2 ne divise pas n.

� Le critère de Korselt permet de reconnaître un nombre de Carmichael à partir de sa décomposition en produit de facteurs premiers. On admet le théorème suivant :

Théorème de Korselt

Un entier n est un nombre de Carmichael si, et seulement si, n est strictement positif, non premier, sans facteur carré, et tel que pour tout premier p divisant n, p − 1 divise n − 1.

a) Montrer que les nombres de Carmichael sont impairs.

b) Montrer qu’un nombre de Carmichael possède au moins trois facteurs pre-miers (distincts).

c) Vérifier que 561 est un nombre de Carmichael.

Exercice 14



5 SynthèseSynthèse de la séquence

1. Plus grand commun diviseur

Soit a et b deux entiers relatifs. On suppose que a et b ne sont pas tous les deux nuls.

Un entier qui divise a et b est appelé diviseur commun à a et b.

L’ensemble des diviseurs communs à a et b admet un plus grand élément appelé plus grand commun diviseur de a et b et noté PGCD (a, b).

Propriété et Définition

On note D( )n l’ensemble des diviseurs d’un entier relatif n.

L’ensemble D D( ) ( )a b∩ est alors l’ensemble des diviseurs communs à a et à b.

Soit a et b deux entiers naturels supérieurs ou égaux à 2.

Si, dans leur décomposition en produit de facteurs premiers, a et b n’ont pas de facteur premier commun, PGCD (a, b) = 1.

Sinon, le PGCD de a et de b est égal au produit des facteurs premiers communs de a et de b, chacun d’eux étant affecté du plus petit exposant figurant dans la décomposition de a et de b.

Propriété

Pour tous a, b de Z,non tous deux nuls :

PGCD (a, b) est un entier strictement positif ;

PGCD (a, a) = |a| ; PGCD (a, 1) = 1 ; PGCD (a, 0) = |a| ;

PGCD (a, b) = PGCD (b, a) = PGCD (|a|, |b|).

D D D( ) ( ) , ) .a b a b∩ = ( )PGCD(

A

Notation

Remarques



Si a divise b, alors PGCD (a, b) = |a |.

Propriété

Soit a un entier naturel et b un entier naturel non nul et a = bq + r la division eucli-dienne de a par b.

Alors :

D D D D( ) ( ) ( ) ( )a b b a bq∩( ) = ∩ −( ) et donc

PGCD (a ; b) = PGCD (b ; a – bq) et ainsi, PGCD (a ; b) = PGCD (b ; r).

Propriété

2. Entiers premiers entre eux

Entiers premiers entre eux


Les entiers a et b sont premiers entre eux lorsque PGCD (a, b) = 1.

Définition

Soit a et b deux entiers relatifs non tous les deux nuls.

Alors PGCD (a ; b) = PGCD (a – b ; b).

Propriété


Soit PGCD (a, b) = d et a’ et b’ les entiers définis par a = da’ et b = db’.

Alors on a PGCD (a’, b’ ) = 1.

Propriété

Théorème de Bézout


On a PGCD (a, b) = 1 si, et seulement si, il existe deux entiers relatifs u et v tels que au + bv = 1.

La relation au + bv = 1 est appelée relation de Bézout.

Théorème 1



Théorème de Gauss

Soit a, b et c des entiers.

Si a divise le produit bc et si a est premier avec b, alors a divise c.

Théorème 2

Si deux entiers a et b premiers entre eux divisent un entier c, alors ab divise c.

Si un nombre premier p divise un produit ab, alors p divise a ou p divise b.

Conséquences

Exercices de synthèse

Démonstration du petit théorème de Fermat

Le but de cet exercice est de démontrer le théorème suivant ainsi que son corollaire.

Soit n un entier.

Si p est un nombre premier ne divisant pas n, alors n pp− ≡1 1[ ].

Théorème

Si p est un entier naturel premier et n est un entier naturel, alors n n pp ≡ [ ].

Corollaire

Partie A Démonstration du théorème

Soit p un nombre premier. Soit n un entier non divisible par p. Soit E l’ensemble E = {n ; 2n ; 3n ; … ; (p – 1)n }.

� Montrer que p ne divise aucun élément de E.

� Montrer que deux éléments de E ont des restes distincts dans la division eucli-dienne par p.

� En déduire que la liste non ordonnée des restes possibles dans la division euclidienne par p des éléments de l’ensemble E est {1 ; 2 ; 3 ; … ; p – 1}.

� Soit M le produit des éléments de E : M n n n p n= × × × × −2 3 1... ( ) .

a) Montrer que M p np= − −( )! .1 1

b) Montrer que M p p≡ −( )![ ].1

c) En déduire que ( )!( ) [ ]p n pp− − ≡−1 1 01 puis que n pp− ≡1 1[ ].

B

Exercice I



Partie B

Déduire le corollaire de la partie A.

Chiffrement de Hill

Partie A « Inverse de 23 modulo 26 »

On considère l’équation (E) :

23 x − 26 y = 1, où x et y désignent deux entiers relatifs.

� Vérifier que le couple (−9 ; −8) est solution de l’équation (E).

� Résoudre alors l’équation (E).

� En déduire un entier a tel que 0 25≤ ≤a et 23 1 26a ≡ [ ].

Partie B

On veut coder un mot de deux lettres selon la procédure suivante.

Étape 1

Chaque lettre du mot est remplacée par un entier en utilisant le tableau ci- dessous :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

0 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

On obtient un couple d’entiers x x( ; )1 2 où x1 correspond à la première lettre du mot et x2 correspond à la deuxième lettre du mot.

Étape 2

Le couple d’entiers x x( ; )1 2 est transformé en un couple d’entiers y y( ; )1 2 de telle sorte que :

y y0 25 et 0 25 ;1 2≤ ≤ ≤ ≤

les coordonnées de

y

y1

2

sont respectivement congrues aux coordonnées

de

11 37 4

1

2

⋅

x

xmodulo 26.

On résume les deux conditions suivantes en écrivant :

«

y

y

x

x1

2

1

2

11 37 4

=

⋅

(mod 26) ».

Étape 3

Le couple d’entiers y y( ; )1 2 est transformé en un mot de deux lettres en utilisant le tableau de correspondance donné dans l’étape 1.

Exercice II



� Coder le mot ST.

� On veut maintenant déterminer la procédure de décodage.

a) Déterminer l’inverse de la matrice M =

11 37 4

.

b) À l’aide de la partie A, déterminer un « inverse de 23 modulo 26 ».

c) En déduire que « x

x

y

y1

2

1

2

16 111 5

26

=

⋅

(mod ) ».

d) Décoder le mot YJ.

Problèmes des restes chinois

Combien l’armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste deux soldats, rangés par 5 colonnes, il reste trois soldats et, rangés par 7 colonnes, il reste deux soldats ?

Ce problème est tiré du livre de Sun Zi, mathématicien et astronome chinois, le Sunzi suanjing, datant du IIIe siècle. Il est connu sous le nom de « Problèmes des restes chinois ».

Dans cet exercice, a et b désignent des entiers strictement positifs.

� a) Démontrer que s’il existe deux entiers relatifs u et v tels que au + bv =1, alors les nombres a et b sont premiers entre eux.

b) En déduire que si ( ) ,a ab b2 2 2 1+ − = alors a et b sont premiers entre eux.

� On se propose de déterminer les couples d’entiers strictement positifs (a ; b) tels que ( ) .a ab b2 2 2 1+ − = Un tel couple sera appelé solution.

a) Déterminer a lorsque a = b.

b) Vérifier que (1 ; 1), (2 ; 3) et (5 ; 8) sont trois solutions particulières.

c) Montrer que si (a ; b) est solution et si a b, alors a b( ) 0.2 2− <

� a) Montrer que si (x ; y) est une solution différente de (1 ; 1), alors (y − x ; x) et (y ; y + x) sont aussi des solutions.

b) Déduire de � b) trois nouvelles solutions.

� On considère la suite de nombres entiers strictement positifs ( )an définie par a a0 1 1= = et pour tout entier strictement positif n, a a an n n+ += +2 1 .

Démontrer que pour tout entier n > 0, a a( ; )n n 1+ est solution.

En déduire que les nombres an et an+1 sont premiers entre eux.

Théorème de Wilson

� Soit p > 5 un nombre premier et soit A = {2 ; ··· ; p −2}. Montrer que pour tout x dans A, x 2 1− n’est pas divisible par p.

� a) Soit x dans A. Prouver qu’il existe un entier u tel que xu p≡ 1mod( ).

Exercice III

Remarque

Exercice IV

Exercice V



b) En déduire l’existence d’un unique entier r de A, distinct de x, tel que xr p≡ 1mod( ).

c) Établir alors que 2 3 2 1× × × − ≡... ( ) mod( ),p p puis que ( )! mod( ).p p− ≡ −1 1

� La précédente congruence demeure-t-elle vérifiée pour les nombres premiers p = 2 et p = 3 ?

� Réciproquement, soit p > 2 tel que ( )! mod( ).p p− ≡ −1 1 Montrer, en utilisant le théorème de Bézout, que p est premier.

� En déduire le théorème de Wilson : un nombre p est premier si, et seulement si, ( )! mod( ).p p− + ≡1 1 0

Dans cet exercice, on pourra utiliser le résultat suivant :

« Étant donné deux entiers naturels a et b non nuls, si PGCD(a ; b) = 1, alors a bPGCD( ; ) 12 2 = . »

Une suite ( Sn ) est définie pour n > 0 par S pnp

n=

=∑ 3

1.

On se propose de calculer, pour tout entier naturel non nul n, le plus grand com-mun diviseur de Sn et Sn+1.

� Démontrer que pour tout n > 0, on a : Sn n

n = +

( ).

12

2

� Étude du cas où n est pair.

Soit k l’entier naturel non nul tel que n = 2k.

a) Démontrer que S S k PGCD k kPGCD( ; ) (2 1) ; ( 1)k k2 2 12 2(= + ++

b) Calculer PGCD (k ; k +1).

c) Calculer PGCD S S( ; ).k k2 2 1+

� Étude du cas où n est impair.

Soit k l’entier naturel non nul tel que n = 2k +1.

a) Démontrer que les entiers 2k +1 et 2k +3 sont premiers entre eux.

b) Calculer PGCD( ; ).S Sk k2 1 2 2+ +

� Déduire des questions précédentes qu’il existe une unique valeur de n, que l’on déterminera, pour laquelle Sn et Sn+1 sont premiers entre eux.

� On considère l’équation (E) :

17x −24y =9, où (x, y) est un couple d’entiers relatifs.

a) Vérifier que le couple (9 ; 6) est solution de l’équation (E).

b) Résoudre l’équation (E).

Exercice VI

Exercice VII



� Dans une fête foraine, Jean s’installe dans un manège circulaire représenté par le schéma ci-dessous :

A

C

F

BD

E

GH

Il peut s’installer sur l’un des huit points indiqués sur le cercle. Le manège com-porte un jeu qui consiste à attraper un pompon qui se déplace sur un câble formant un carré dans lequel est inscrit le cercle. Le manège tourne dans le sens des aiguilles d’une montre, à vitesse constante. Il fait un tour à vitesse constante. Il fait un tour en 24 secondes. Le pompon se déplace dans le même sens à vitesse constante. Il fait un tour en 17 secondes. Pour gagner, Jean doit attraper le pom-pon, et il ne peut le faire qu’aux points de contact qui sont notés A, B, C et D sur le dessin. À l’instant t = 0, Jean part du point H en même temps que le pompon part du point A.

a) On suppose qu’à un certain instant t, Jean attrape le pompon en A. Jean a déjà pu passer un certain nombre de fois en A sans y trouver le pompon. À l’instant t, on note y le nombre de tours effectués depuis son premier passage en A et x le nombre de tours effectués par le pompon. Montrer que (x, y) est solution de l’équation (E) de la question 1.

b) Jean a payé pour 2 minutes. Aura-t-il le temps d’attraper le pompon ?

c) Montrer qu’en fait il n’est possible d’attraper le pompon qu’au point A.

d) Jean part maintenant du point E. Aura-t-il le temps d’attraper le pompon en A avant les deux minutes ?

�


Documents

Séquence 3 - Académie en ligne : tous les cours de l… · 2018-03-25 · Séquence 3 – MA03 1 Séquence 3 Arithmétique et problèmes de codages (suite) Cette séquence fait