Mathématiques · Prépa concours post-bac — ENA Architecture

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 : Pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$ , il existe un unique couple $(q, r)$ tel que $a = bq + r$ avec $0 \leq r < b$ .
Congruence : $a \equiv b [n] \iff n | (a-b)$ . Propriétés : compatibilité avec l'addition, la multiplication et la puissance.
PGCD et PPCM : $d = \text{pgcd}(a, b)$ est le plus grand diviseur commun. $a \cdot b = \text{pgcd}(a, b) \cdot \text{ppcm}(a, b)$ .
Théorème de Bézout : $\text{pgcd}(a, b) = 1 \iff \exists (u, v) \in \mathbb{Z}^2, au + bv = 1$ .
Théorème de Gauss : Si $a | bc$ et $\text{pgcd}(a, b) = 1$ , alors $a | c$ .
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

Déterminer le PGCD par l'algorithme d'Euclide.
Résoudre une équation diophantienne $ax + by = c$ (utiliser Bézout).
Résoudre une congruence $ax \equiv b [n]$ (utiliser l'inverse modulaire).
Utiliser la décomposition en facteurs premiers pour trouver les diviseurs.

Exemples corrigés

PGCD : $\text{pgcd}(126, 45) : 126 = 2 \times 45 + 36 ; 45 = 1 \times 36 + 9 ; 36 = 4 \times 9 + 0$ . Donc $\text{pgcd} = 9$ .
Congruence : Calculer $3^{100} [7]$ . $3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6 \equiv -1 [7]$ . Donc $3^6 \equiv 1 [7]$ . $100 = 6 \times 16 + 4$ . $3^{100} \equiv (3^6)^{16} \times 3^4 \equiv 1^{16} \times 81 \equiv 4 [7]$ .

Erreurs fréquentes

Oublier la condition $0 \leq r < b$ dans la division euclidienne.
Croire que $a \equiv b [n] \implies a^k \equiv b^k [n]$ est vrai mais que la réciproque est fausse.
Confondre PGCD et PPCM.
Ne pas vérifier si $\text{pgcd}(a, n) = 1$ avant d'utiliser l'inverse modulaire.

L'essentiel du cours

Division euclidienne : Pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$, il existe un unique couple $(q, r)$ tel que $a = bq + r$ avec $0 \leq r < b$.
Congruence : $a \equiv b [n] \iff n | (a-b)$. Propriétés : compatibilité avec l'addition, la multiplication et la puissance.
PGCD et PPCM : $d = \text{pgcd}(a, b)$ est le plus grand diviseur commun. $a \cdot b = \text{pgcd}(a, b) \cdot \text{ppcm}(a, b)$.
Théorème de Bézout : $\text{pgcd}(a, b) = 1 \iff \exists (u, v) \in \mathbb{Z}^2, au + bv = 1$.
Théorème de Gauss : Si $a | bc$ et $\text{pgcd}(a, b) = 1$, alors $a | c$.
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

Déterminer le PGCD par l'algorithme d'Euclide.
Résoudre une équation diophantienne $ax + by = c$ (utiliser Bézout).
Résoudre une congruence $ax \equiv b [n]$ (utiliser l'inverse modulaire).
Utiliser la décomposition en facteurs premiers pour trouver les diviseurs.

Exemples corrigés

PGCD : $\text{pgcd}(126, 45) : 126 = 2 \times 45 + 36 ; 45 = 1 \times 36 + 9 ; 36 = 4 \times 9 + 0$. Donc $\text{pgcd} = 9$.
Congruence : Calculer $3^{100} [7]$. $3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6 \equiv -1 [7]$. Donc $3^6 \equiv 1 [7]$. $100 = 6 \times 16 + 4$. $3^{100} \equiv (3^6)^{16} \times 3^4 \equiv 1^{16} \times 81 \equiv 4 [7]$.

Erreurs fréquentes

Oublier la condition $0 \leq r < b$ dans la division euclidienne.
Croire que $a \equiv b [n] \implies a^k \equiv b^k [n]$ est vrai mais que la réciproque est fausse.
Confondre PGCD et PPCM.
Ne pas vérifier si $\text{pgcd}(a, n) = 1$ avant d'utiliser l'inverse modulaire.

🌉 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

Le reste de la division euclidienne de 100 par 7 est :

❓ Questions fréquentes

Qu'est-ce qu'un nombre premier ?

Un nombre premier est un entier naturel supérieur ou égal à 2 qui n'admet que deux diviseurs positifs : 1 et lui-même. Exemples : 2, 3, 5, 7, 11...

💡 À retenir : 1 n'est pas un nombre premier.

kifach n7seb pgcd dyal jwjouj a3dad kbar?

St3ml khwarizmiyat iqlidis (lqisma lmutatabi3a).
Qsm l kbir 3la sghir w lqa lbaqi.
3awd lqisma b lmaqsum 3lih lqdim w lbaqi jdid.
L'3amaliya li kaysali fiha lbaqi b 0, l'baqi li qbl mnha howa l-pgcd.

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

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

Oui, car la congruence est compatible avec la multiplication. Si $a \equiv b [n]$ , alors $a \times a \equiv b \times b [n]$ , soit $a^2 \equiv b^2 [n]$ .

💡 À retenir : La congruence préserve les puissances.

Oui, car la congruence est compatible avec la multiplication. Si $a \equiv b [n]$, alors $a \times a \equiv b \times b [n]$, soit $a^2 \equiv b^2 [n]$.

💡 À retenir : La congruence préserve les puissances.

chhal kayswa a^0 f l'arithmétique ?

$a^0 = 1$ pour tout entier $a$ non nul. C'est une convention mathématique standard utilisée dans tous les chapitres, y compris l'arithmétique.

💡 À retenir : $0^0$ est une forme indéterminée.

$a^0 = 1$ pour tout entier $a$ non nul. C'est une convention mathématique standard utilisée dans tous les chapitres, y compris l'arithmétique.

💡 À retenir : $0^0$ est une forme indéterminée.

Comment résoudre ax + by = c ?

Vérifie si $d = \text{pgcd}(a, b)$ divise $c$ . Si non, pas de solution.
Si oui, divise toute l'équation par $d$ .
Utilise l'algorithme d'Euclide étendu pour trouver une solution particulière $(x_0, y_0)$ .
La solution générale est $x = x_0 + k(b/d)$ et $y = y_0 - k(a/d)$ avec $k \in \mathbb{Z}$ .

💡 À retenir : Sans le PGCD, l'équation n'a pas de solution entière.

Vérifie si $d = \text{pgcd}(a, b)$ divise $c$. Si non, pas de solution.
Si oui, divise toute l'équation par $d$.
Utilise l'algorithme d'Euclide étendu pour trouver une solution particulière $(x_0, y_0)$.
La solution générale est $x = x_0 + k(b/d)$ et $y = y_0 - k(a/d)$ avec $k \in \mathbb{Z}$.

💡 À retenir : Sans le PGCD, l'équation n'a pas de solution entière.

wach l-ppcm dyal a w b howa a times b dima ?

La, machi dima. L-ppcm(a,b) = $(|a \times b|) / \text{pgcd}(a,b)$ . $a \times b$ kaysawi l-ppcm ghir ila kan pgcd(a,b) = 1.

💡 À retenir : Toujours diviser par le PGCD.

La, machi dima. L-ppcm(a,b) = $(|a \times b|) / \text{pgcd}(a,b)$. $a \times b$ kaysawi l-ppcm ghir ila kan pgcd(a,b) = 1.

💡 À retenir : Toujours diviser par le PGCD.

Le théorème de Fermat est-il toujours applicable ?

Il est applicable si le module $p$ est un nombre premier et que $p$ ne divise pas $a$ .

💡 À retenir : Vérifie toujours la primalité de $p$ .

Il est applicable si le module $p$ est un nombre premier et que $p$ ne divise pas $a$.

💡 À retenir : Vérifie toujours la primalité de $p$.

Comment trouver l'inverse de a modulo n ?

Il faut résoudre $ax \equiv 1 [n]$ . Cela revient à chercher $x$ tel que $ax + ny = 1$ . On utilise l'algorithme d'Euclide étendu.

💡 À retenir : L'inverse existe ssi $\text{pgcd}(a, n) = 1$ .

Il faut résoudre $ax \equiv 1 [n]$. Cela revient à chercher $x$ tel que $ax + ny = 1$. On utilise l'algorithme d'Euclide étendu.

💡 À retenir : L'inverse existe ssi $\text{pgcd}(a, n) = 1$.

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

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

💡 À retenir : Attention au signe dans $\mathbb{Z}$ .

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

💡 À retenir : Attention au signe dans $\mathbb{Z}$.

Pourquoi on utilise le modulo ?

Le modulo permet de travailler sur les restes de la division, ce qui simplifie énormément les calculs de grandes puissances ou de divisibilité.

💡 À retenir : Le modulo transforme des calculs complexes en manipulations simples.

Est-ce que tout nombre entier peut être décomposé en facteurs premiers ?

Oui, c'est le théorème fondamental de l'arithmétique : tout entier $n > 1$ se décompose de manière unique en produit de facteurs premiers.

💡 À retenir : La décomposition est unique à l'ordre près.

Oui, c'est le théorème fondamental de l'arithmétique : tout entier $n > 1$ se décompose de manière unique en produit de facteurs premiers.

💡 À retenir : La décomposition est unique à l'ordre près.

Comment savoir si un nombre est premier rapidement ?

Il faut tester la divisibilité par tous les nombres premiers $p$ tels que $p^2 \leq n$ . Si aucun ne divise $n$ , alors $n$ est premier.

💡 À retenir : Inutile de tester au-delà de $\sqrt{n}$ .

Il faut tester la divisibilité par tous les nombres premiers $p$ tels que $p^2 \leq n$. Si aucun ne divise $n$, alors $n$ est premier.

💡 À retenir : Inutile de tester au-delà de $\sqrt{n}$.

✍️ Exercices type examen national

Exercice 1

Déterminer le PGCD de 252 et 105.
Résoudre dans $\mathbb{Z}^2$ l'équation $252x + 105y = 21$ .

Exercice 1

Déterminer le PGCD de 252 et 105.
Résoudre dans $\mathbb{Z}^2$ l'équation $252x + 105y = 21$.

Voir la correction détaillée : inscription gratuite

Exercice 2

Soit $n \in \mathbb{N}$ . Montrer que $n^3 - n$ est divisible par 3.

Exercice 2

Soit $n \in \mathbb{N}$. Montrer que $n^3 - n$ est divisible par 3.

Voir la correction détaillée : inscription gratuite

Exercice 3

Déterminer l'ensemble des entiers $n$ tels que $n+3$ divise $2n+10$ .

Exercice 3

Déterminer l'ensemble des entiers $n$ tels que $n+3$ divise $2n+10$.

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 Limites et continuité Dérivabilité et étude de fonctions Fonctions logarithmes et exponentielles Primitives et calcul intégral Suites numériques Équations différentielles Géométrie dans l'espace Produit scalaire et applications Dénombrement et probabilités Transformations du plan