Mathématiques · Prépa concours post-bac — Écoles militaires & royales

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,b) \in \mathbb{Z} \times \mathbb{N}^*, \exists !(q,r) \in \mathbb{Z} \times \{0, \dots, b-1\}, a = bq + r$ .
Congruences : $a \equiv b [n] \iff n | (a-b)$ . Propriétés : compatibilité avec l'addition, la multiplication et la puissance.
PGCD et PPCM : $a \wedge b = d \iff d$ est le plus grand diviseur commun. $a \vee b = \frac{|ab|}{a \wedge b}$ .
Bézout : $a \wedge b = d \iff \exists (u,v) \in \mathbb{Z}^2, au + bv = d$ .
Gauss : Si $a|bc$ et $a \wedge b = 1$ , alors $a|c$ .
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 une équation diophantienne $ax + by = c$ (nécessite $d|c$ ).
Utiliser les congruences pour démontrer des propriétés de divisibilité ou trouver le dernier chiffre d'un nombre.
Décomposer un nombre en facteurs premiers pour trouver le PGCD/PPCM.

Exemples corrigés

Exemple 1 : Résoudre $3x \equiv 1 [7]$ . On cherche l'inverse de 3 modulo 7. $3 \times 5 = 15 \equiv 1 [7]$ . Donc $x \equiv 5 [7]$ .
Exemple 2 : Montrer que $7 | 2^{3n} - 1$ . $2^3 = 8 \equiv 1 [7]$ . Donc $(2^3)^n \equiv 1^n \equiv 1 [7]$ . D'où $2^{3n} - 1 \equiv 0 [7]$ .

Erreurs fréquentes

Oublier la condition $0 \leq r < |b|$ dans la division euclidienne.
Appliquer Gauss sans vérifier que $a \wedge b = 1$ .
Confondre $a \wedge b = 1$ (premiers entre eux) avec $a$ et $b$ premiers.
Oublier de vérifier si $d | c$ avant de résoudre $ax + by = c$ .

L'essentiel du cours

Divisibilité : $a|b \iff \exists k \in \mathbb{Z}, b = ak$.
Division euclidienne : $\forall (a,b) \in \mathbb{Z} \times \mathbb{N}^*, \exists !(q,r) \in \mathbb{Z} \times {0, \dots, b-1}, a = bq + r$.
Congruences : $a \equiv b [n] \iff n | (a-b)$. Propriétés : compatibilité avec l'addition, la multiplication et la puissance.
PGCD et PPCM : $a \wedge b = d \iff d$ est le plus grand diviseur commun. $a \vee b = \frac{|ab|}{a \wedge b}$.
Bézout : $a \wedge b = d \iff \exists (u,v) \in \mathbb{Z}^2, au + bv = d$.
Gauss : Si $a|bc$ et $a \wedge b = 1$, alors $a|c$.
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 une équation diophantienne $ax + by = c$ (nécessite $d|c$).
Utiliser les congruences pour démontrer des propriétés de divisibilité ou trouver le dernier chiffre d'un nombre.
Décomposer un nombre en facteurs premiers pour trouver le PGCD/PPCM.

Exemples corrigés

Exemple 1 : Résoudre $3x \equiv 1 [7]$. On cherche l'inverse de 3 modulo 7. $3 \times 5 = 15 \equiv 1 [7]$. Donc $x \equiv 5 [7]$.
Exemple 2 : Montrer que $7 | 2^{3n} - 1$. $2^3 = 8 \equiv 1 [7]$. Donc $(2^3)^n \equiv 1^n \equiv 1 [7]$. D'où $2^{3n} - 1 \equiv 0 [7]$.

Erreurs fréquentes

Oublier la condition $0 \leq r < |b|$ dans la division euclidienne.
Appliquer Gauss sans vérifier que $a \wedge b = 1$.
Confondre $a \wedge b = 1$ (premiers entre eux) avec $a$ et $b$ premiers.
Oublier de vérifier si $d | c$ avant de résoudre $ax + by = c$.

🌉 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 de $10^{10}$ par 7 ?

❓ Questions fréquentes

Qu'est-ce qu'une équation diophantienne ?

C'est une équation de la forme $ax + by = c$ où $a, b, c$ sont des entiers donnés et on cherche les couples $(x, y) \in \mathbb{Z}^2$ . Elle admet des solutions si et seulement si le PGCD de $a$ et $b$ divise $c$ .

💡 À retenir : Pas de PGCD qui divise $c$ , pas de solutions !

C'est une équation de la forme $ax + by = c$ où $a, b, c$ sont des entiers donnés et on cherche les couples $(x, y) \in \mathbb{Z}^2$. Elle admet des solutions si et seulement si le PGCD de $a$ et $b$ divise $c$.

💡 À retenir : Pas de PGCD qui divise $c$, pas de solutions !

Kifach n'lqa PGCD dial joj a3dad kbar bhal 1234 o 567 ?

Utilise l'algorithme d'Euclide : fais des divisions successives.
$1234 = 2 \times 567 + 100$ .
$567 = 5 \times 100 + 67$ .
$100 = 1 \times 67 + 33$ .
$67 = 2 \times 33 + 1$ .
$33 = 33 \times 1 + 0$ .
Le dernier reste non nul est 1. Donc $1234 \wedge 567 = 1$ .

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

Utilise l'algorithme d'Euclide : fais des divisions successives.
$1234 = 2 \times 567 + 100$.
$567 = 5 \times 100 + 67$.
$100 = 1 \times 67 + 33$.
$67 = 2 \times 33 + 1$.
$33 = 33 \times 1 + 0$.
Le dernier reste non nul est 1. Donc $1234 \wedge 567 = 1$.

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

Est-ce que si a|bc alors a|b ou a|c ?

Non, c'est faux. Exemple : $6 | (2 \times 3)$ , mais $6 \nmid 2$ et $6 \nmid 3$ . C'est vrai seulement si $a$ est premier ou si $a \wedge b = 1$ (Théorème de Gauss).

💡 À retenir : La condition $a \wedge b = 1$ est indispensable pour conclure.

Non, c'est faux. Exemple : $6 | (2 \times 3)$, mais $6 \nmid 2$ et $6 \nmid 3$. C'est vrai seulement si $a$ est premier ou si $a \wedge b = 1$ (Théorème de Gauss).

💡 À retenir : La condition $a \wedge b = 1$ est indispensable pour conclure.

Kifach n'3ref wach l'adad awwali wla la ?

Pour savoir si $n$ est premier, teste la divisibilité par tous les nombres premiers $p$ tels que $p^2 \leq n$ .
Si aucun ne divise $n$ , alors $n$ est premier.

💡 À retenir : Il suffit de tester jusqu'à la racine carrée de $n$ .

Pour savoir si $n$ est premier, teste la divisibilité par tous les nombres premiers $p$ tels que $p^2 \leq n$.
Si aucun ne divise $n$, alors $n$ est premier.

💡 À retenir : Il suffit de tester jusqu'à la racine carrée de $n$.

Comment trouver l'inverse de a modulo n ?

On cherche $x$ tel que $ax \equiv 1 [n]$ .
Cela revient à résoudre $ax + ny = 1$ .
On utilise l'algorithme d'Euclide étendu pour trouver $x$ et $y$ .

💡 À retenir : L'inverse existe si et seulement si $a \wedge n = 1$ .

On cherche $x$ tel que $ax \equiv 1 [n]$.
Cela revient à résoudre $ax + ny = 1$.
On utilise l'algorithme d'Euclide étendu pour trouver $x$ et $y$.

💡 À retenir : L'inverse existe si et seulement si $a \wedge n = 1$.

Chno hiya l'farqa bin a wedge b = 1 o a, b awwaliyan ?

$a \wedge b = 1$ signifie qu'ils n'ont aucun diviseur commun autre que 1 (ils sont premiers entre eux). $a$ et $b$ premiers signifie que chacun d'eux n'a que 1 et lui-même comme diviseurs.

💡 À retenir : Deux nombres peuvent être premiers entre eux sans être premiers (ex: 8 et 9).

$a \wedge b = 1$ signifie qu'ils n'ont aucun diviseur commun autre que 1 (ils sont premiers entre eux). $a$ et $b$ premiers signifie que chacun d'eux n'a que 1 et lui-même comme diviseurs.

💡 À retenir : Deux nombres peuvent être premiers entre eux sans être premiers (ex: 8 et 9).

Peut-on diviser dans une congruence ?

On ne peut pas diviser directement. Si $ac \equiv bc [n]$ , on peut simplifier par $c$ seulement si $c \wedge n = 1$ . Dans ce cas, $a \equiv b [n]$ .

💡 À retenir : Si $c \wedge n = d \neq 1$ , on divise tout par $d$ : $a \equiv b [n/d]$ .

On ne peut pas diviser directement. Si $ac \equiv bc [n]$, on peut simplifier par $c$ seulement si $c \wedge n = 1$. Dans ce cas, $a \equiv b [n]$.

💡 À retenir : Si $c \wedge n = d \neq 1$, on divise tout par $d$ : $a \equiv b [n/d]$.

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

Utilise les propriétés des puissances et les congruences successives.
Cherche une période ou utilise le petit théorème de Fermat si $m$ est premier.
Décompose $n$ en puissances de 2 (exponentiation rapide).

💡 À retenir : Réduis la base modulo $m$ à chaque étape.

Utilise les propriétés des puissances et les congruences successives.
Cherche une période ou utilise le petit théorème de Fermat si $m$ est premier.
Décompose $n$ en puissances de 2 (exponentiation rapide).

💡 À retenir : Réduis la base modulo $m$ à chaque étape.

Est-ce que le PGCD peut être négatif ?

Par définition dans le programme, le PGCD est le plus grand diviseur commun positif. Donc $a \wedge b \geq 0$ .

💡 À retenir : Le PGCD est toujours un entier naturel.

Par définition dans le programme, le PGCD est le plus grand diviseur commun positif. Donc $a \wedge b \geq 0$.

💡 À retenir : Le PGCD est toujours un entier naturel.

Kifach n'biyen bli n kayqsem a-b ?

Il faut montrer que $a \equiv b [n]$ . Tu peux utiliser les propriétés de congruence ou montrer que $a-b = k \times n$ avec $k \in \mathbb{Z}$ .

💡 À retenir : $a \equiv b [n] \iff a - b$ est un multiple de $n$ .

Il faut montrer que $a \equiv b [n]$. Tu peux utiliser les propriétés de congruence ou montrer que $a-b = k \times n$ avec $k \in \mathbb{Z}$.

💡 À retenir : $a \equiv b [n] \iff a - b$ est un multiple de $n$.

Comment résoudre x^2 equiv a [p] ?

C'est une équation de congruence quadratique. Pour $p$ petit, on teste toutes les valeurs de $0$ à $p-1$ . Pour $p$ grand, on utilise le symbole de Legendre (à vérifier par le professeur si au programme, sinon méthode par tâtonnement).

💡 À retenir : Tester les valeurs est souvent suffisant pour les exercices de concours.

C'est une équation de congruence quadratique. Pour $p$ petit, on teste toutes les valeurs de $0$ à $p-1$. Pour $p$ grand, on utilise le symbole de Legendre (à vérifier par le professeur si au programme, sinon méthode par tâtonnement).

💡 À retenir : Tester les valeurs est souvent suffisant pour les exercices de concours.

Le théorème de Fermat marche-t-il si p ne divise pas a ?

Oui, le petit théorème de Fermat dit que si $p$ est premier et $p \nmid a$ , alors $a^{p-1} \equiv 1 [p]$ . Si $p | a$ , alors $a^p \equiv a [p]$ est toujours vrai.

💡 À retenir : $a^p \equiv a [p]$ est la forme générale pour tout $a$ .

Oui, le petit théorème de Fermat dit que si $p$ est premier et $p \nmid a$, alors $a^{p-1} \equiv 1 [p]$. Si $p | a$, alors $a^p \equiv a [p]$ est toujours vrai.