Mathématiques · Prépa concours post-bac — IAV & ENA Meknès

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

Divisibilité : $a|b \iff \exists k \in \mathbb{Z}, b=ak$ .
Division euclidienne : $\forall a \in \mathbb{Z}, \forall b \in \mathbb{N}^*, \exists!(q, r) \in \mathbb{Z} \times \{0, \dots, b-1\}, a = bq + r$ .
PGCD et PPCM : $d = a \wedge b$ . On a $ab = (a \wedge b)(a \vee 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 $+$ et $\times$ .
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.
Utiliser Bézout pour trouver une solution particulière d'une équation $ax + by = c$ .
Passer aux congruences pour résoudre des équations diophantiennes ou des problèmes de divisibilité.
Décomposer un nombre en facteurs premiers pour trouver le nombre de diviseurs.

Exemples corrigés

PGCD : $126 \wedge 42 = 42$ car $126 = 3 \times 42$ .
Congruence : Calculer $2^{10} [7]$ . $2^3 = 8 \equiv 1 [7]$ , donc $(2^3)^3 \times 2 \equiv 1^3 \times 2 \equiv 2 [7]$ .

Erreurs fréquentes

Oublier que le reste $r$ doit vérifier $0 \leq r < |b|$ .
Appliquer Gauss sans vérifier que $a \wedge b = 1$ .
Confondre $a \equiv b [n]$ avec $a = b \times n$ .
Oublier le cas $a \wedge b = 1$ dans le théorème de Fermat.

L'essentiel du cours

Divisibilité : $a|b \iff \exists k \in \mathbb{Z}, b=ak$.
Division euclidienne : $\forall a \in \mathbb{Z}, \forall b \in \mathbb{N}^*, \exists!(q, r) \in \mathbb{Z} \times {0, \dots, b-1}, a = bq + r$.
PGCD et PPCM : $d = a \wedge b$. On a $ab = (a \wedge b)(a \vee 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 $+$ et $\times$.
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.
Utiliser Bézout pour trouver une solution particulière d'une équation $ax + by = c$.
Passer aux congruences pour résoudre des équations diophantiennes ou des problèmes de divisibilité.
Décomposer un nombre en facteurs premiers pour trouver le nombre de diviseurs.

Exemples corrigés

PGCD : $126 \wedge 42 = 42$ car $126 = 3 \times 42$.
Congruence : Calculer $2^{10} [7]$. $2^3 = 8 \equiv 1 [7]$, donc $(2^3)^3 \times 2 \equiv 1^3 \times 2 \equiv 2 [7]$.

Erreurs fréquentes

Oublier que le reste $r$ doit vérifier $0 \leq r < |b|$.
Appliquer Gauss sans vérifier que $a \wedge b = 1$.
Confondre $a \equiv b [n]$ avec $a = b \times n$.
Oublier le cas $a \wedge b = 1$ dans le théorème 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 la division euclidienne de 25 par 7 ?

❓ Questions fréquentes

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

Non, cela implique $a = b$ ou $a = -b$ car $a$ et $b$ sont des entiers relatifs.

💡 À retenir : La relation de divisibilité n'est pas une relation d'ordre total sur $\mathbb{Z}$ .

Non, cela implique $a = b$ ou $a = -b$ car $a$ et $b$ sont des entiers relatifs.

💡 À retenir : La relation de divisibilité n'est pas une relation d'ordre total sur $\mathbb{Z}$.

Kifach n7seb PGCD dyal joj a3dad kbar bhal 1050 o 350?

Utilise l'algorithme d'Euclide : effectue des divisions successives.
$1050 = 3 \times 350 + 0$ .
Le dernier reste non nul est le PGCD. Ici, c'est 350.

💡 À retenir : Le PGCD est le dernier reste non nul dans l'algorithme d'Euclide.

Utilise l'algorithme d'Euclide : effectue des divisions successives.
$1050 = 3 \times 350 + 0$.
Le dernier reste non nul est le PGCD. Ici, c'est 350.

💡 À retenir : Le PGCD est le dernier reste non nul dans l'algorithme d'Euclide.

Chno hiya l'far9 bin l'qisma l'iqlidiya o l'qisma l'3adiya?

La division classique donne un résultat décimal.
La division euclidienne travaille uniquement dans $\mathbb{Z}$ et impose un reste $r$ tel que $0 \leq r < |b|$ .

💡 À retenir : En arithmétique, on ne travaille qu'avec des entiers.

La division classique donne un résultat décimal.
La division euclidienne travaille uniquement dans $\mathbb{Z}$ et impose un reste $r$ tel que $0 \leq r < |b|$.

💡 À retenir : En arithmétique, on ne travaille qu'avec des entiers.

Kifach n3ref wach l'adad awali wla la?

Teste la divisibilité par les nombres premiers successifs ( $2, 3, 5, 7, 11, \dots$ ).
Arrête-toi dès que le carré du nombre premier testé dépasse ton nombre.

💡 À retenir : Si aucun nombre premier $p \leq \sqrt{n}$ ne divise $n$ , alors $n$ est premier.

Teste la divisibilité par les nombres premiers successifs ($2, 3, 5, 7, 11, \dots$).
Arrête-toi dès que le carré du nombre premier testé dépasse ton nombre.

💡 À retenir : Si aucun nombre premier $p \leq \sqrt{n}$ ne divise $n$, alors $n$ est premier.

Comment utiliser le théorème de Bézout pour résoudre ax + by = c ?

Vérifie que $d = a \wedge b$ divise $c$ . Sinon, pas de solution.
Trouve une solution particulière $(u_0, v_0)$ telle que $au_0 + bv_0 = d$ (via Euclide).
Multiplie par $c/d$ pour obtenir une solution $(x_0, y_0)$ .

💡 À retenir : L'existence de solutions dépend uniquement de la divisibilité de $c$ par le PGCD.

Vérifie que $d = a \wedge b$ divise $c$. Sinon, pas de solution.
Trouve une solution particulière $(u_0, v_0)$ telle que $au_0 + bv_0 = d$ (via Euclide).
Multiplie par $c/d$ pour obtenir une solution $(x_0, y_0)$.

💡 À retenir : L'existence de solutions dépend uniquement de la divisibilité de $c$ par le PGCD.

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

Oui, la congruence est compatible avec la puissance entière. Si $a \equiv b [n]$ , alors pour tout $k \in \mathbb{N}$ , $a^k \equiv b^k [n]$ .

💡 À retenir : La puissance conserve la relation de congruence.

Oui, la congruence est compatible avec la puissance entière. Si $a \equiv b [n]$, alors pour tout $k \in \mathbb{N}$, $a^k \equiv b^k [n]$.

💡 À retenir : La puissance conserve la relation de congruence.

Comment trouver l'inverse de a modulo n ?

Il faut que $a \wedge n = 1$ .
Utilise Bézout : $au + nv = 1$ .
Alors $au \equiv 1 [n]$ , donc $u$ est l'inverse de $a$ .

💡 À retenir : L'inverse existe si et seulement si $a$ et $n$ sont premiers entre eux.

Il faut que $a \wedge n = 1$.
Utilise Bézout : $au + nv = 1$.
Alors $au \equiv 1 [n]$, donc $u$ est l'inverse de $a$.

💡 À retenir : L'inverse existe si et seulement si $a$ et $n$ sont premiers entre eux.

Pourquoi le théorème de Gauss est-il si important ?

Il permet de simplifier des expressions dans les congruences ou de prouver la divisibilité quand on a des facteurs premiers entre eux.

💡 À retenir : Gauss transforme une divisibilité de produit en divisibilité d'un facteur.

Comment déterminer le nombre de diviseurs d'un entier n ?

Décompose $n$ en facteurs premiers : $n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots$ .
Le nombre de diviseurs est le produit $(\alpha_1 + 1)(\alpha_2 + 1) \dots$ .

💡 À retenir : Le nombre de diviseurs dépend uniquement des exposants de la décomposition.

Décompose $n$ en facteurs premiers : $n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots$.
Le nombre de diviseurs est le produit $(\alpha_1 + 1)(\alpha_2 + 1) \dots$.

💡 À retenir : Le nombre de diviseurs dépend uniquement des exposants de la décomposition.

Comment calculer a^n [m] quand n est très grand ?

Utilise les propriétés des puissances et les congruences successives.
Cherche une puissance $k$ telle que $a^k \equiv 1 [m]$ ou $a^k \equiv -1 [m]$ .

💡 À retenir : La périodicité des puissances modulo $m$ simplifie les grands exposants.

Utilise les propriétés des puissances et les congruences successives.
Cherche une puissance $k$ telle que $a^k \equiv 1 [m]$ ou $a^k \equiv -1 [m]$.

💡 À retenir : La périodicité des puissances modulo $m$ simplifie les grands exposants.

Le théorème de Fermat s'applique-t-il si p divise a ?

Non, si $p|a$ , alors $a \equiv 0 [p]$ , donc $a^{p-1} \equiv 0 [p]$ , ce qui est différent de $1 [p]$ .

💡 À retenir : La condition $p \nmid a$ est indispensable pour obtenir $1$ .

Non, si $p|a$, alors $a \equiv 0 [p]$, donc $a^{p-1} \equiv 0 [p]$, ce qui est différent de $1 [p]$.

💡 À retenir : La condition $p \nmid a$ est indispensable pour obtenir $1$.

Peut-on diviser par un nombre dans une congruence ?

Seulement si le nombre est premier avec le module. Si $ac \equiv bc [n]$ et $c \wedge n = 1$ , alors $a \equiv b [n]$ .

💡 À retenir : La simplification nécessite la condition de primalité avec le module.

Seulement si le nombre est premier avec le module. Si $ac \equiv bc [n]$ et $c \wedge n = 1$, alors $a \equiv b [n]$.

💡 À retenir : La simplification nécessite la condition de primalité avec le module.

✍️ Exercices type examen national

Exercice 1

Déterminer le couple $(x, y) \in \mathbb{Z}^2$ tel que $17x + 13y = 1$ .

Exercice 1

Déterminer le couple $(x, y) \in \mathbb{Z}^2$ tel que $17x + 13y = 1$.

Voir la correction détaillée : inscription gratuite

Exercice 2

Montrer que pour tout entier $n$ , $n^3 - n$ est divisible par 6.

Exercice 2

Montrer que pour tout entier $n$, $n^3 - n$ est divisible par 6.

Voir la correction détaillée : inscription gratuite

Exercice 3

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

Exercice 3

Résoudre dans $\mathbb{Z}$ l'équation $3x \equiv 2 [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 Nombres complexes Polynômes et fractions rationnelles Espaces vectoriels Applications linéaires et matrices Déterminants et systèmes linéaires Suites numériques Limites et continuité Dérivabilité et étude de fonctions Fonctions usuelles (logarithmes, exponentielles, puissances)Intégration sur un segment Équations différentielles linéaires Dénombrement et probabilités Variables aléatoires discrètes