Exercice 1★ Facile
Effectuer les divisions euclidiennes : a) 257 ÷ 11 b) 1000 ÷ 7 c) -43 ÷ 6
~4 lignes
Exercice 2★ Facile
Démontrer que si a | b et b | c, alors a | c.
~4 lignes · définition a|b
Exercice 3★ Facile
Montrer que pour tout entier n, n(n+1) est pair.
~3 lignes · parité
Exercice 4★★ Intermédiaire
Montrer que pour tout entier n, \(3 \mid n^3 - n\).
~4 lignes · factoriser n³-n
Exercice 5★★ Intermédiaire
Montrer que pour tout entier n, \(6 \mid n(n+1)(n+2)\).
~5 lignes · produit de 3 consécutifs
Exercice 6★★ Intermédiaire
Montrer que si a | b et a | c alors a | (ub + vc) pour tous u, v entiers.
~4 lignes
Exercice 7★★ Intermédiaire
Trouver tous les entiers n tels que n | (n² + 2).
~5 lignes · n|n², donc n|2
Exercice 8★★★ Difficile
Montrer que tout nombre premier > 3 est congru à 1 ou 5 modulo 6.
~5 lignes · cas modulo 6
Exercice 9★★★ Difficile
Montrer par récurrence que \(8 \mid 9^n - 1\) pour tout entier \(n \geq 1\).
~6 lignes · récurrence
Exercice 10★★★★ Expert
Démontrer qu'il existe une infinité de nombres premiers (preuve d'Euclide par l'absurde).
~7 lignes · considérer p₁p₂...pₙ+1
Exercice 1★ Facile
Calculer par l'algorithme d'Euclide : a) PGCD(48, 36) b) PGCD(252, 105) c) PGCD(1071, 462)
~6 lignes
Exercice 2★ Facile
Montrer que PGCD(n+1, n) = 1 pour tout entier n ≥ 1.
~3 lignes · Euclide en 1 étape
Exercice 3★★ Intermédiaire
Trouver les coefficients de Bézout (u,v) pour PGCD(48,30) et vérifier : 48u + 30v = PGCD(48,30).
~6 lignes · algorithme d'Euclide étendu
Exercice 4★★ Intermédiaire
Appliquer le théorème de Gauss : si 7 | 5n, que peut-on conclure ? Justifier.
~4 lignes · PGCD(7,5)=1
Exercice 5★★ Intermédiaire
Résoudre l'équation diophantienne \(7x + 5y = 1\). Donner toutes les solutions entières.
~6 lignes · une sol. particulière puis sol. générale
Exercice 6★★ Intermédiaire
Résoudre l'équation diophantienne \(6x + 9y = 12\). Donner les conditions d'existence et les solutions.
~5 lignes · PGCD(6,9)=3, 3|12
Exercice 7★★ Intermédiaire
Montrer que si PGCD(a,b)=1 et a | n et b | n, alors ab | n.
~5 lignes · Bézout + Gauss
Exercice 8★★★ Difficile
Démontrer le théorème de Bézout : pour tous a,b entiers non tous nuls, \(\exists\, u,v \in \mathbb{Z}\) tels que \(au + bv = \text{PGCD}(a,b)\).
~8 lignes · minimum du sous-ensemble
Exercice 9★★★ Difficile
Un marchand a des pommes par lots de 7 ou de 12. Peut-il préparer exactement 50 pommes ? 38 pommes ?
~5 lignes · équation diophantienne
Exercice 10★★★★ Expert
Calculer PGCD(F_n, F_{n+1}) pour les nombres de Fibonacci définis par F₁=F₂=1 et F_{n+2}=F_n+F_{n+1}. Montrer que ce PGCD vaut toujours 1.
~7 lignes · Euclide + récurrence
Exercice 1★ Facile
Calculer les restes : a) 2024 mod 7 b) 3¹⁰ mod 4 c) 100! mod 11
~4 lignes
Exercice 2★ Facile
Trouver le dernier chiffre (chiffre des unités) de 7¹⁰⁰. (Étudier les puissances de 7 modulo 10.)
~4 lignes · cycle de période 4
Exercice 3★★ Intermédiaire
Montrer que \(n^2 \equiv 0\) ou \(1 \pmod 4\) pour tout entier n.
~4 lignes · n pair/impair
Exercice 4★★ Intermédiaire
Résoudre l'équation \(3x \equiv 7 \pmod{11}\). (Trouver l'inverse de 3 modulo 11.)
~5 lignes · Bézout ou essai
Exercice 5★★ Intermédiaire
Appliquer le petit théorème de Fermat : calculer 2¹⁰⁰ mod 101. (101 est premier.)
~4 lignes
Exercice 6★★ Intermédiaire
Résoudre le système de congruences : x ≡ 2 (mod 3) et x ≡ 3 (mod 5). (Théorème chinois des restes.)
~5 lignes
Exercice 7★★ Intermédiaire
Montrer que 13 | (2³⁰ − 1). (Utiliser Fermat : p = 13.)
~4 lignes
Exercice 8★★★ Difficile
Calculer le reste de 3¹⁰⁰ divisé par 7. (p=7, Fermat donne 3⁶≡1 (mod 7).)
~5 lignes · 100 = 16×6 + 4
Exercice 9★★★ Difficile
Montrer que si p est premier, alors \((p-1)! \equiv -1 \pmod p\) (Théorème de Wilson).
~7 lignes · inverses mod p
Exercice 10★★★★ Expert
Démontrer le petit théorème de Fermat : si p premier et p ∤ a, alors a^(p-1) ≡ 1 (mod p). (Considérer l'ensemble {a, 2a, ..., (p-1)a} modulo p.)
~9 lignes · démonstration complète
Exercice 1 — BACNiveau BAC Expertes
(6 pts) Soit n un entier naturel.
1. Montrer que n² + n est toujours divisible par 2. (1 pt)
2. Montrer que n³ − n est divisible par 6. (2 pts)
3. En déduire que le cube de tout entier est congru à cet entier modulo 6. (2 pts)
4. Trouver tous les cubes parfaits modulo 9. (1 pt)
~10 lignes
Exercice 2 — BACNiveau BAC Expertes
(5 pts) Résoudre l'équation diophantienne \(12x + 8y = 20\).
1. Existence : vérifier que PGCD(12,8) | 20. (1 pt)
2. Trouver une solution particulière. (2 pts)
3. Donner l'ensemble de toutes les solutions. (2 pts)
~9 lignes
Exercice 3 — BACNiveau BAC Expertes
(5 pts) Cryptographie RSA simplifié : p=5, q=7 (n=35), e=5.
1. Calculer φ(n) = (p-1)(q-1). (1 pt)
2. Trouver d tel que ed ≡ 1 (mod φ(n)). (2 pts)
3. Chiffrer le message m=3 : calculer m^e mod n. (2 pts)
~9 lignes · Bézout pour d
Exercice 4 — BACNiveau BAC Expertes
(4 pts) Montrer que PGCD(a²,b²) = PGCD(a,b)² pour tous entiers a,b > 0.
Indice : utiliser la décomposition en facteurs premiers.
~8 lignes
Exercice 5 — BACNiveau BAC Expertes
(4 pts) Montrer que √2 est irrationnel en raisonnant par l'absurde et en utilisant le théorème de Gauss (ou la parité).
~7 lignes · p=q=2 irréductible
Exercice 6Niveau BAC Expertes
(4 pts) Trouver tous les entiers n ≥ 2 tels que n | 2ⁿ − 1.
~7 lignes · tester petites valeurs + Fermat
Exercice 7Niveau BAC Expertes
(3 pts) Combien y a-t-il d'entiers de 1 à 100 qui sont premiers avec 100 ? (Utiliser la formule d'Euler φ(100) = 100(1-1/2)(1-1/5).)
~5 lignes
Exercice 8★★★★
(5 pts) Montrer que pour p premier impair, \(1^{p-1} + 2^{p-1} + \cdots + (p-1)^{p-1} \equiv -1 \pmod p\) en utilisant le petit théorème de Fermat.
~8 lignes
Exercice 9★★★★
(5 pts) Démontrer le théorème de Gauss à partir du théorème de Bézout : si a|bc et PGCD(a,b)=1, alors a|c.
~6 lignes
Exercice 10 — Synthèse★★★★
(7 pts) Les nombres de Mersenne sont de la forme M_p = 2^p - 1 (p premier).
1. Montrer que si n n'est pas premier, alors 2^n - 1 ne l'est pas non plus. (3 pts)
2. Vérifier que M₅=31 est premier. (1 pt)
3. M₁₁ = 2047 = 23×89. Que peut-on conclure ? (1 pt)
4. Calculer M₅ mod 11 par Fermat. (2 pts)
~12 lignes