Arithmétique dans ℕ
Mathématiques – Tronc Commun Science
Introduction
L’arithmétique est la branche des mathématiques qui étudie les propriétés des nombres entiers naturels (ℕ). C’est la base de nombreuses théories mathématiques et applications cryptographiques modernes.
ℕ
Nombres naturels
0, 1, 2, 3…
Outils
Division euclidienne
PGCD, PPCM
Applications
Cryptographie
Algorithmique
1. Division Euclidienne
\[ a = b \times q + r \quad \text{avec} \quad 0 \leq r < b \]
Théorème fondamental
Pour tout entier naturel a et tout entier naturel non nul b, il existe un unique couple (q,r) tel que :
Avec :
- q : quotient
- r : reste
Exemple interactif
Calculer la division de par
2. PGCD et Algorithme d’Euclide
PGCD : Définition
Le Plus Grand Commun Diviseur de deux entiers a et b est le plus grand entier qui divise simultanément a et b.
Propriétés :
- PGCD(a,b) = PGCD(b,a)
- PGCD(a,0) = a
- Si a|b, PGCD(a,b) = a
Algorithme d’Euclide
Basé sur la propriété :
\[ PGCD(a,b) = PGCD(b, r) \]où r est le reste de la division de a par b
Exemple pratique
Calculons PGCD(56, 20) :
Donc PGCD(56,20) = 4
Calculateur interactif :
PGCD(, )
= 4
3. Théorèmes Fondamentaux
Théorème de Bézout
Deux nombres sont premiers entre eux si et seulement si on peut trouver une combinaison linéaire de ces nombres égale à 1.
Exemple :
8 et 5 sont premiers entre eux car :
\[ 8 \times 2 + 5 \times (-3) = 1 \]Théorème de Gauss
Si un nombre divise un produit et est premier avec l’un des facteurs, alors il divise l’autre facteur.
Exemple :
3 | 5×6 et PGCD(3,5)=1 ⇒ 3 | 6
4. Nombres Premiers
Définition
Un nombre premier est un entier naturel ≥2 qui n’a que deux diviseurs distincts : 1 et lui-même.
Exemples :
2, 3, 5, 7, 11, 13, 17, 19, 23…
1 n’est pas premier !
Théorème fondamental
Tout entier n ≥ 2 se décompose de manière unique (à l’ordre près) en produit de facteurs premiers :
\[ n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k} \]
Crible d’Ératosthène
Méthode pour trouver tous les nombres premiers jusqu’à une limite donnée :
5. Applications et Exercices
Exercice 1
Montrer que la somme de trois entiers consécutifs est divisible par 3.
Exercice 2
Trouver tous les entiers n tels que n+2 divise n² + 4.
Applications modernes
- Cryptographie RSA : Basée sur la difficulté de factoriser de grands nombres
- Algorithmes : Calcul du PGCD, simplification de fractions
- Théorie des codes : Codes correcteurs d’erreurs
