Mathématiques · Prépa concours post-bac — ENSA & ENSAM

Arithmétique dans Z

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Division euclidienne : $\forall a \in \mathbb{Z}, \forall b \in \mathbb{Z}^*, \exists!(q, r) \in \mathbb{Z}^2$ tels que $a = bq + r$ avec $0 \le r < |b|$ .
PGCD et PPCM : $d = PGCD(a, b)$ est le plus grand diviseur commun. $a \wedge b = 1$ signifie que $a$ et $b$ sont premiers entre eux. $a \times b = PGCD(a, b) \times PPCM(a, b)$ .
Théorème de Bézout : $a \wedge b = d \iff \exists (u, v) \in \mathbb{Z}^2, au + bv = d$ .
Théorème de Gauss : Si $a|bc$ et $a \wedge b = 1$ , alors $a|c$ .
Congruences : $a \equiv b [n] \iff n | (a-b)$ . Propriétés : compatibilité avec l'addition, la multiplication et la puissance.
Petit théorème de Fermat : Si $p$ est premier et $p \nmid a$ , alors $a^{p-1} \equiv 1 [p]$ .

Méthodes à maîtriser

Utiliser l'algorithme d'Euclide pour trouver le PGCD.
Résoudre des équations diophantiennes de type $ax + by = c$ (nécessite $PGCD(a,b) | c$ ).
Utiliser les congruences pour démontrer des propriétés de divisibilité ou trouver le reste d'une puissance.
Décomposer un nombre en produit de facteurs premiers.

Exemples corrigés

Exemple 1 : Trouver le reste de $2^{2024} [7]$ . $2^3 = 8 \equiv 1 [7]$ . Donc $2^{2024} = (2^3)^{674} \times 2^2 \equiv 1^{674} \times 4 \equiv 4 [7]$ .
Exemple 2 : Résoudre $3x \equiv 1 [7]$ . On cherche $x$ tel que $3x = 7k + 1$ . Pour $k=1$ , $3x=8$ (non). Pour $k=2$ , $3x=15 \implies x=5$ .

Erreurs fréquentes

Oublier la condition $0 \le r < |b|$ dans la division euclidienne.
Appliquer le théorème de Gauss sans vérifier que $a \wedge b = 1$ .
Confondre $a \equiv b [n]$ avec $a = b \times n$ .
Oublier que $a^p \equiv a [p]$ est vrai pour tout $a$ (généralisation de Fermat).

L'essentiel du cours

Division euclidienne : $\forall a \in \mathbb{Z}, \forall b \in \mathbb{Z}^*, \exists!(q, r) \in \mathbb{Z}^2$ tels que $a = bq + r$ avec $0 \le r < |b|$.
PGCD et PPCM : $d = PGCD(a, b)$ est le plus grand diviseur commun. $a \wedge b = 1$ signifie que $a$ et $b$ sont premiers entre eux. $a \times b = PGCD(a, b) \times PPCM(a, b)$.
Théorème de Bézout : $a \wedge b = d \iff \exists (u, v) \in \mathbb{Z}^2, au + bv = d$.
Théorème de Gauss : Si $a|bc$ et $a \wedge b = 1$, alors $a|c$.
Congruences : $a \equiv b [n] \iff n | (a-b)$. Propriétés : compatibilité avec l'addition, la multiplication et la puissance.
Petit théorème de Fermat : Si $p$ est premier et $p \nmid a$, alors $a^{p-1} \equiv 1 [p]$.

Méthodes à maîtriser

Utiliser l'algorithme d'Euclide pour trouver le PGCD.
Résoudre des équations diophantiennes de type $ax + by = c$ (nécessite $PGCD(a,b) | c$).
Utiliser les congruences pour démontrer des propriétés de divisibilité ou trouver le reste d'une puissance.
Décomposer un nombre en produit de facteurs premiers.

Exemples corrigés

Exemple 1 : Trouver le reste de $2^{2024} [7]$. $2^3 = 8 \equiv 1 [7]$. Donc $2^{2024} = (2^3)^{674} \times 2^2 \equiv 1^{674} \times 4 \equiv 4 [7]$.
Exemple 2 : Résoudre $3x \equiv 1 [7]$. On cherche $x$ tel que $3x = 7k + 1$. Pour $k=1$, $3x=8$ (non). Pour $k=2$, $3x=15 \implies x=5$.

Erreurs fréquentes

Oublier la condition $0 \le r < |b|$ dans la division euclidienne.
Appliquer le théorème de Gauss sans vérifier que $a \wedge b = 1$.
Confondre $a \equiv b [n]$ avec $a = b \times n$.
Oublier que $a^p \equiv a [p]$ est vrai pour tout $a$ (généralisation de Fermat).

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Arithmétique dans Z

1/4

Quel est le reste de $10^{10} [7]$ ?

❓ Questions fréquentes

Comment savoir si un nombre est premier rapidement ?

Vérifie s'il est pair (sauf 2).
Vérifie la somme de ses chiffres (divisibilité par 3).
Teste la divisibilité par les nombres premiers successifs ( $2, 3, 5, 7, 11...$ ) jusqu'à la racine carrée du nombre. Si aucun ne divise le nombre, il est premier.

💡 À retenir : Il suffit de tester jusqu'à $\sqrt{n}$ .

Vérifie s'il est pair (sauf 2).
Vérifie la somme de ses chiffres (divisibilité par 3).
Teste la divisibilité par les nombres premiers successifs ($2, 3, 5, 7, 11...$) jusqu'à la racine carrée du nombre. Si aucun ne divise le nombre, il est premier.

💡 À retenir : Il suffit de tester jusqu'à $\sqrt{n}$.

Kifach n7seb PGCD dyal jouj a3dad kbar bzaf?

St3mel khawarizmiyat Euclide (lqisma l'euclidienne l'moutatabi3a).
Qsem l'adad lkbir 3la sghir, o khod lbaqi.
3awd lqisma 3la l'adad li qsemti bih o lbaqi li khrej lik.
Hta ykoun lbaqi howa 0, l'adad li qbelo howa l-PGCD.

💡 À retenir : L'algorithme d'Euclide est la méthode la plus rapide.

Est-ce que a equiv b [n] implique a^k equiv b^k [n] ?

Oui, c'est une propriété fondamentale des congruences. Si $a \equiv b [n]$ , alors pour tout entier naturel $k$ , $a^k \equiv b^k [n]$ . On peut élever les deux membres à une puissance entière sans changer le module.

💡 À retenir : La congruence est compatible avec la puissance.

Oui, c'est une propriété fondamentale des congruences. Si $a \equiv b [n]$, alors pour tout entier naturel $k$, $a^k \equiv b^k [n]$. On peut élever les deux membres à une puissance entière sans changer le module.

💡 À retenir : La congruence est compatible avec la puissance.

Chno hiya l'equation diophantienne?

Hiya equation 3la chkel $ax + by = c$ fin $x$ o $y$ khashom ykouno des entiers relatifs ( $\mathbb{Z}$ ). Bach tkon 3andha l7oloul, khass $PGCD(a,b)$ ykoun kayqsem $c$ .

💡 À retenir : Sans la condition de divisibilité du PGCD, il n'y a pas de solution dans $\mathbb{Z}$ .

Hiya equation 3la chkel $ax + by = c$ fin $x$ o $y$ khashom ykouno des entiers relatifs ($\mathbb{Z}$). Bach tkon 3andha l7oloul, khass $PGCD(a,b)$ ykoun kayqsem $c$.

💡 À retenir : Sans la condition de divisibilité du PGCD, il n'y a pas de solution dans $\mathbb{Z}$.

Pourquoi on utilise le petit théorème de Fermat ?

Il sert à simplifier le calcul des puissances élevées modulo un nombre premier $p$ . Au lieu de calculer $a^{100} [p]$ , on réduit l'exposant modulo $p-1$ .

💡 À retenir : $a^{p-1} \equiv 1 [p]$ permet de réduire drastiquement les exposants.

Il sert à simplifier le calcul des puissances élevées modulo un nombre premier $p$. Au lieu de calculer $a^{100} [p]$, on réduit l'exposant modulo $p-1$.

💡 À retenir : $a^{p-1} \equiv 1 [p]$ permet de réduire drastiquement les exposants.

Kifach n3ref wach l'inverse modulaire kayn?

L'inverse de $a$ modulo $n$ existe si et seulement si $a$ et $n$ sont premiers entre eux, c'est-à-dire $PGCD(a, n) = 1$ .

💡 À retenir : $PGCD(a, n) = 1 \iff \exists x, ax \equiv 1 [n]$ .

L'inverse de $a$ modulo $n$ existe si et seulement si $a$ et $n$ sont premiers entre eux, c'est-à-dire $PGCD(a, n) = 1$.

💡 À retenir : $PGCD(a, n) = 1 \iff \exists x, ax \equiv 1 [n]$.

Est-ce que a|b et b|a implique a=b ?

Non, cela implique $a = b$ ou $a = -b$ (donc $|a| = |b|$ ). Dans $\mathbb{Z}$ , les diviseurs peuvent être négatifs.

💡 À retenir : La divisibilité ne concerne que la valeur absolue.

Non, cela implique $a = b$ ou $a = -b$ (donc $|a| = |b|$). Dans $\mathbb{Z}$, les diviseurs peuvent être négatifs.

💡 À retenir : La divisibilité ne concerne que la valeur absolue.

Comment trouver tous les diviseurs d'un nombre ?

Décompose le nombre en facteurs premiers : $n = p_1^{\alpha_1} \times p_2^{\alpha_2} \dots$
Chaque diviseur est de la forme $p_1^{\beta_1} \times p_2^{\beta_2} \dots$ avec $0 \le \beta_i \le \alpha_i$ .
Liste toutes les combinaisons possibles.

💡 À retenir : Le nombre total de diviseurs est $(\alpha_1+1)(\alpha_2+1)\dots$ .

Décompose le nombre en facteurs premiers : $n = p_1^{\alpha_1} \times p_2^{\alpha_2} \dots$
Chaque diviseur est de la forme $p_1^{\beta_1} \times p_2^{\beta_2} \dots$ avec $0 \le \beta_i \le \alpha_i$.
Liste toutes les combinaisons possibles.

💡 À retenir : Le nombre total de diviseurs est $(\alpha_1+1)(\alpha_2+1)\dots$.

Est-ce que ac equiv bc [n] implies a equiv b [n] ?

Pas toujours ! C'est vrai seulement si $PGCD(c, n) = 1$ . Si $PGCD(c, n) = d > 1$ , alors $a \equiv b [n/d]$ .

💡 À retenir : On ne peut simplifier par $c$ que si $c$ est premier avec le module.

Pas toujours ! C'est vrai seulement si $PGCD(c, n) = 1$. Si $PGCD(c, n) = d > 1$, alors $a \equiv b [n/d]$.

💡 À retenir : On ne peut simplifier par $c$ que si $c$ est premier avec le module.

Chno lferq bin l'ensemble mathbb{N} o mathbb{Z} f l'arithmétique?

F $\mathbb{N}$ , l'qisma dima kat3ti lbaqi moujab. F $\mathbb{Z}$ , l'qisma l'euclidienne katkheli lbaqi dima moujab ( $0 \le r < |b|$ ) meme ila kan l'adad salib.

💡 À retenir : Le reste est toujours positif par définition.

F $\mathbb{N}$, l'qisma dima kat3ti lbaqi moujab. F $\mathbb{Z}$, l'qisma l'euclidienne katkheli lbaqi dima moujab ($0 \le r < |b|$) meme ila kan l'adad salib.

💡 À retenir : Le reste est toujours positif par définition.

Peut-on diviser dans les congruences ?

On ne "divise" pas, on multiplie par l'inverse modulaire. Si tu veux résoudre $ax \equiv b [n]$ , tu multiplies par $a^{-1}$ (si $a \wedge n = 1$ ).

💡 À retenir : La division n'existe pas, seul l'inverse existe.

On ne "divise" pas, on multiplie par l'inverse modulaire. Si tu veux résoudre $ax \equiv b [n]$, tu multiplies par $a^{-1}$ (si $a \wedge n = 1$).

💡 À retenir : La division n'existe pas, seul l'inverse existe.

Comment montrer qu'un nombre n'est pas premier ?

Il suffit de trouver un diviseur autre que 1 et lui-même. Par exemple, s'il est pair et supérieur à 2, ou si la somme de ses chiffres est un multiple de 3.

💡 À retenir : Un seul contre-exemple suffit.

✍️ Exercices type examen national

Exercice 1

Déterminer le PGCD de 126 et 45, puis trouver un couple $(u, v) \in \mathbb{Z}^2$ tel que $126u + 45v = PGCD(126, 45)$ .

Exercice 1

Déterminer le PGCD de 126 et 45, puis trouver un couple $(u, v) \in \mathbb{Z}^2$ tel que $126u + 45v = PGCD(126, 45)$.

Voir la correction détaillée : inscription gratuite

Exercice 2

Résoudre dans $\mathbb{Z}$ l'équation $7x \equiv 3 [11]$ .

Exercice 2

Résoudre dans $\mathbb{Z}$ l'équation $7x \equiv 3 [11]$.

Voir la correction détaillée : inscription gratuite

Exercice 3

Montrer que pour tout $n \in \mathbb{N}$ , $3^{2n+1} + 2^{n+2}$ est divisible par 7.

Exercice 3

Montrer que pour tout $n \in \mathbb{N}$, $3^{2n+1} + 2^{n+2}$ est divisible par 7.

Voir la correction détaillée : inscription gratuite

Un prof de Mathématiques pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Mathématiques

Logique et raisonnements Ensembles et applications Calcul algébrique et polynômes Nombres complexes Dérivabilité et étude de fonctions Suites numériques Calcul intégral et primitives Transformations du plan