MATHEMATICS · 2ème Bac Sciences Mathématiques · 2ème Bac

Arithmétique dans ℤ

Bézout, Gauss, congruences, équations diophantiennes, petit théorème de Fermat.

الحسابيات في ℤ : مبرهنة بوزو، مبرهنة غوص، الموافقات بترديد n، المعادلات الديوفنتية ومبرهنة فيرما الصغرى.

Le cours

Le cours complet, tel qu'il est dans le PDF : définitions, théorèmes, propriétés, exemples et démonstrations (repliées, clique pour les lire).

Rappels et identité de Bézout

En 2 $e$ Bac SM on reprend l'arithmétique de 1BAC SM avec plus de rigueur.

Théorème : Identité de Bézout

Soient $a, b \in Z$ non tous deux nuls et $d = PGCD (a, b)$ . Il existe $u, v \in Z$ tels que $a u + b v = d$ . En particulier : $a, b$ premiers entre eux ssi il existe $u, v$ tels que $a u + b v = 1$ .

L'algorithme d'Euclide étendu fournit une méthode algorithmique pour trouver $u, v$ .

Théorèmes de Gauss et applications

Théorème : Gauss

Soient $a, b, c \in Z$ . Si $a ∣ b c$ et $PGCD (a, b) = 1$ , alors $a ∣ c$ .

Démonstration

Par Bézout, $a u + b v = 1$ . Multiplier par $c$ : $a u c + b v c = c$ . $a ∣ a u c$ et $a ∣ b c$ donc $a ∣ b v c$ , donc $a ∣ c$ .

Propriété

Si $a ∣ c$ , $b ∣ c$ et $PGCD (a, b) = 1$ , alors $ab ∣ c$ .

Équations diophantiennes linéaires

Théorème : Équations

a x + b y = c

Soient $a, b, c \in Z$ avec $(a, b) \neq = (0, 0)$ et $d = PGCD (a, b)$ .

L'équation $a x + b y = c$ admet des solutions entières ssi $d ∣ c$ .
Si $(x_{0}, y_{0})$ est une solution particulière, l'ensemble des solutions est : $x = x_{0} + (\frac{b}{d}) k$ , $y = y_{0} - (\frac{a}{d}) k$ , $k \in Z$ .

Exemple

Résoudre $15 x + 6 y = 9$ . $d = 3$ divise $9$ . Solution particulière : $15 \times 1 + 6 \times (- 1) = 9$ . Général : $x = 1 + 2 k, y = - 1 - 5 k$ .

Congruences

Définition

$a \equiv bm o d n$ si $n ∣ (a - b)$ . Relation d'équivalence.

Propriété : Opérations

Si $a \equiv a^{'}$ et $b \equiv b^{'}$ (tous modulo $n$ ) : $a + b \equiv a^{'} + b^{'}$ , $ab \equiv a^{'} b^{'}$ , $a^{k} \equiv a^{' k}$ .

Théorème : Petit théorème de Fermat

Si $p$ est premier et $a \in Z$ non multiple de $p$ , alors :

a^{p - 1} \equiv 1 m o d p .

Plus généralement, $a^{p} \equiv am o d p$ pour tout $a \in Z$ .

Résolution d'équations modulo n

Pour résoudre $a x \equiv bm o d n$ :

Si $d = PGCD (a, n)$ ne divise pas $b$ , pas de solution.
Sinon, simplifier par $d$ pour obtenir $a^{'} x \equiv b^{'} m o d n^{'}$ avec $PGCD (a^{'}, n^{'}) = 1$ , puis utiliser l'inverse de $a^{'}$ modulo $n^{'}$ (fourni par Bézout).

Exemple

Résoudre $5 x \equiv 3 m o d 11$ . Inverse de $5$ modulo $11$ : par Bézout, $5 \times 9 = 45 = 4 \times 11 + 1$ , donc $9$ est l'inverse. $x \equiv 27 \equiv 5 m o d 11$ .

Applications en cryptographie

Les congruences et le petit théorème de Fermat sont les fondations de la cryptographie moderne (RSA en particulier). À ce niveau, on se limite à des exercices de manipulation.

Documents

Lis le cours directement dans l'application, ou télécharge le PDF pour le consulter hors ligne.

Teste-toi : 10 questions sur ce chapitre

Une seule bonne réponse par question. Réponds sans regarder le cours, puis lis l'explication : c'est là que tu apprends. Ton meilleur score est gardé dans ce navigateur.

0/10 répondues

1.
Deux entiers $a$ et $b$ sont premiers entre eux si et seulement si :
2.
Un couple $(u; v)$ d'entiers vérifiant $35 u + 8 v = 1$ est :
3.
Si $a ∣ c$ et $b ∣ c$ , peut-on conclure que $ab ∣ c$ ?
4.
Quel exemple montre que l'hypothèse $PGCD (a, b) = 1$ est nécessaire dans le théorème de Gauss ( $a ∣ b c \Rightarrow a ∣ c$ ) ?
5.
Pour tout entier naturel $n$ , le nombre $n^{3} - n$ est divisible par :
6.
Sachant que $(4; - 1)$ est une solution de $3 x + 5 y = 7$ , l'ensemble des solutions dans $Z^{2}$ est donné par :
7.
Le reste de la division euclidienne de $3^{100}$ par $7$ est :
8.
Le petit théorème de Fermat garantit $a^{p - 1} \equiv 1 [p]$ dès que :
9.
La solution de $3 x \equiv 5 [7]$ est :
10.
L'équation $6 x \equiv 3 [9]$ :

Encore 10 questions.