I) LA DIVISIBILITÉ DANS \(\mathbb{Z}\)
1) Définition et conséquences
Soient \(a\) et \(b\) deux entiers relatifs tels que \(b \neq 0\). On dit que l’entier relatif \(b\) divise \(a\) s’il existe un entier relatif \(k\) tel que :
On écrit : \(b \mid a\). On dit aussi que \(a\) est divisible par \(b\) ou que \(a\) est un multiple de \(b\).
- Si \(b \mid a\), alors \(-b \mid a\) également.
- 1 divise tous les entiers relatifs.
- 0 est divisible par tous les entiers non nuls (car \(0 = 0 \times b\)).
- Si \(a\) est un entier, l’ensemble de ses diviseurs dans \(\mathbb{Z}\) est noté \(D_a\). C’est un ensemble fini.
- Si \(b\) est un entier non nul, l’ensemble de ses multiples est noté \(b\mathbb{Z}\). C’est un ensemble infini.
Soient \(a, b, c\) des entiers relatifs :
- Transitivité : Si \(a \mid b\) et \(b \mid c\), alors \(a \mid c\).
- Linéarité : Si \(a \mid b\) et \(a \mid c\), alors pour tous entiers \(\alpha\) et \(\beta\), \(a \mid (\alpha b + \beta c)\).
- Valeur absolue : Si \(a \mid b\) et \(b \neq 0\), alors \(|a| \le |b|\).
- Inversibilité : Si \(a \mid b\) et \(b \mid a\), alors \(|a| = |b|\) (donc \(a = b\) ou \(a = -b\)).
Trouver tous les entiers relatifs \(n\) tels que \((n – 3) \mid (n + 5)\).
On a \((n-3) \mid (n-3)\). Si \((n-3) \mid (n+5)\), alors par linéarité, \((n-3)\) divise la différence :
\((n+5) – (n-3) = 8\).
Donc \((n-3) \in D_8 = \{-8, -4, -2, -1, 1, 2, 4, 8\}\).
En ajoutant 3 à chaque valeur, on trouve :
\(n \in \{-5, -1, 1, 2, 4, 5, 7, 11\}\).
II) LA DIVISION EUCLIDIENNE
Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^*\). Il existe un unique couple d’entiers relatifs \((q, r)\) tels que :
- \(a\) est le dividende.
- \(b\) est le diviseur.
- \(q\) est le quotient.
- \(r\) est le reste.
Le reste \(r\) doit impérativement être positif et strictement inférieur au diviseur \(b\).
Si \(r = 0\), alors \(a\) est un multiple de \(b\) (\(b \mid a\)).
III) LES CONGRUENCES MODULO N
Soit \(n\) un entier naturel non nul. On dit que deux entiers \(a\) et \(b\) sont congrus modulo n si \(n\) divise la différence \(a – b\). On note :
- \(a \equiv b \pmod{n} \iff\) \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
- \(a \equiv b \pmod{n} \iff \exists k \in \mathbb{Z} \mid a = b + kn\).
- \(a \equiv r \pmod{n}\) où \(r\) est le reste de la division de \(a\) par \(n\).
Si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors :
- Addition : \(a + c \equiv b + d \pmod{n}\).
- Multiplication : \(ac \equiv bd \pmod{n}\).
- Puissance : pour tout \(k \in \mathbb{N}\), \(a^k \equiv b^k \pmod{n}\).
Déterminer le reste de la division de \(3^{2024}\) par 7.
On cherche les puissances de 3 modulo 7 :
\(3^1 \equiv 3 \pmod{7}\)
\(3^2 \equiv 9 \equiv 2 \pmod{7}\)
\(3^3 \equiv 3 \times 2 \equiv 6 \equiv -1 \pmod{7}\)
On en déduit : \(3^6 \equiv (-1)^2 \equiv 1 \pmod{7}\).
Or \(2024 = 6 \times 337 + 2\).
Donc \(3^{2024} = (3^6)^{337} \times 3^2 \equiv 1^{337} \times 9 \equiv 2 \pmod{7}\).
Le reste est 2.
IV) PGCD ET PPCM
1) Plus Grand Commun Diviseur (PGCD)
Le PGCD de deux entiers \(a\) et \(b\) (non tous deux nuls) est le plus grand entier naturel qui divise à la fois \(a\) et \(b\). On le note \(PGCD(a, b)\) ou \(a \wedge b\).
On dit que \(a\) et \(b\) sont premiers entre eux si leur PGCD est égal à 1.
2) Plus Petit Commun Multiple (PPCM)
Le PPCM de deux entiers non nuls \(a\) et \(b\) est le plus petit entier naturel strictement positif qui est multiple de \(a\) et de \(b\). On le note \(PPCM(a, b)\) ou \(a \vee b\).
V. ALGORITHME D’EUCLIDE ET IDENTITÉ DE BÉZOUT
Pour trouver le PGCD de deux nombres, on effectue des divisions euclidiennes successives :
\(a = bq_1 + r_1\)
\(b = r_1q_2 + r_2\)
\(r_1 = r_2q_3 + r_3\)
…
Le PGCD est le dernier reste non nul.
Soient \(a\) et \(b\) deux entiers. Il existe deux entiers relatifs \(u\) et \(v\) tels que :
En particulier, \(a \wedge b = 1 \iff \exists u, v \in \mathbb{Z} \mid au + bv = 1\).
Si \(a\) divise le produit \(bc\) et si \(a\) et \(b\) sont premiers entre eux, alors \(a\) divise \(c\).
VI. NOMBRES PREMIERS ET DÉCOMPOSITION
Un entier naturel \(p \ge 2\) est dit premier s’il possède exactement deux diviseurs positifs : 1 et lui-même.
Exemples : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29…
Tout entier \(n \ge 2\) admet une décomposition unique (à l’ordre des facteurs près) en produit de facteurs premiers :
Si \(n = p_1^{\alpha_1} \times \dots \times p_k^{\alpha_k}\), alors le nombre de diviseurs positifs de \(n\) est :
VII. CRITÈRES DE DIVISIBILITÉ
Un nombre entier est divisible par :
- 2 : si son chiffre des unités est pair (0, 2, 4, 6, 8).
- 3 : si la somme de ses chiffres est divisible par 3.
- 4 : si le nombre formé par ses deux derniers chiffres est divisible par 4.
- 5 : si son chiffre des unités est 0 ou 5.
- 9 : si la somme de ses chiffres est divisible par 9.
- 11 : si la somme alternée de ses chiffres est divisible par 11 (\(a-b+c-d… \equiv 0 [11]\)).
Soit \(N = \overline{13x5y}\) un nombre en base 10. Déterminer les chiffres \(x\) et \(y\) pour que \(N\) soit divisible par 4 et 9.
- Divisibilité par 4 : Le nombre \(\overline{5y}\) doit être divisible par 4. Les multiples de 4 dans la cinquantaine sont 52 et 56. Donc \(y \in \{2, 6\}\).
- Divisibilité par 9 : La somme \(1+3+x+5+y = 9+x+y\) doit être divisible par 9.
- Si \(y=2\) : \(9+x+2 = 11+x\). Pour que ce soit divisible par 9, \(11+x=18 \implies x=7\).
- Si \(y=6\) : \(9+x+6 = 15+x\). Pour que ce soit divisible par 9, \(15+x=18 \implies x=3\).
Les solutions sont \(13752\) et \(13356\).