Séquence 3
Arithmétique
et problèmes de codages
(suite)



Sommaire
Cette séquence fait suite à la
séquence  1. En utilisant à nouveau
1. Prérequis des problèmes de codages, nous
2. Plus grand commun diviseur (PGCD) allons introduire ou approfondir des
éléments d’arithmétique.
3. Entiers premiers entre eux
4. Retour sur les nombres premiers
et application au chiffrement RSA
5. Synthèse




Séquence 3 – MA03 1


© Cned - Académie en ligne
1 Prérequis
A Congruence

Définition

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 mod n ou encore x ≡ y [n ] ou encore x ≡ y (n )
et on lit «  x congru à y modulo n  ».


Conséquences

t Un nombre est congru à 0 modulo n si, et seulement si, c’est un multiple de n.
t Tout nombre pair est congru à 0 modulo 2 ; tout nombre impair est congru à 1
modulo 2.
t Tout nombre est congru à son chiffre des unités modulo 10.
t Tout nombre est congru modulo n au reste de sa division euclidienne par n.



Propriété

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
n n
Si x ≡ y [ p ] alors, pour tout entier naturel n, on a : x ≡ y [ p ].




Séquence 3 – MA03 3


© Cned - Académie en ligne
 B Calcul matriciel

Définitions

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

 a11 a12
a1p 
 
 a a a 2p 
A =  21 22 
    
 an 1 an 2
anp 
 

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.
 1 0 0 
 1 0   
I2 =   , I3 =  0 1 0  .
 0 1 
 0 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.


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 0 = I p et An = A
⋅
A⋅ ...⋅
A si n ≥ 1.
n fois
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.




4 Séquence 3 – MA03



© Cned - Académie en ligne
 Propriétés

Matrices 2 × 2
 a b 
Si A =   et det( A ) = ad − bc ≠ 0 alors A est inversible et
 c d 

1  d −b 
A −1 = .
det( A )  −c a 




C Décomposition en produit
de facteurs premiers

Théorème

Soit n un entier naturel strictement supérieur à 1 dont la décomposition en produit
de facteurs premiers est :
n = p1α1 × p2α 2 × ... × pkα k .
Alors les diviseurs de n dans N sont les entiers naturels p1β1 × p2β2 × ... × pkβk où
pour tout 1≤ i ≤ k , 0 ≤ βi ≤ α i .




Corollaire

Soit n un entier naturel strictement supérieur à 1 dont la décomposition en produit
de facteurs premiers est :
n = p1α1 × p2α 2 × ... × pkα k .
Alors le nombre de diviseurs positifs de n est (α 1 + 1) × (α 2 + 1) × ... × (α k + 1).




Séquence 3 – MA03 5


© Cned - Académie en ligne
 2 Plus grand commun
diviseur (PGCD)

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



B Pour débuter

Activité 1 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 ?




6 Séquence 3 – MA03



© Cned - Académie en ligne
Activité 2 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 :
...