Feuille d'exercicesMaths expertes, chapitre 7

PGCD

42 exercices corrigés · 14 17 7 4

Énoncés (PDF)Corrigés (PDF)Le cours

PGCD et algorithme d'Euclide

Exercice 1 1. Déterminer à l'aide des règles de divisibilité: a) PGCD(12,42) b) PGCD(45,105) c) PGCD(92,69) d) PGCD(72,108) 2. Déterminer les entiers naturels…
Exercice 2 Trouver tous les couples d’entiers naturels (a, b) avec a < b tels que: 1. {begin array{ll} ab=432 PGCD(a,b)= 6end array. 2. {begin array{ll}…
Exercice 3 1. Utiliser l'algorithme d'Euclide pour déterminer les PGCD suivants: a) PGCD(144,840) b) PGCD(202,138) c) PGCD(441,777) d) PGCD(2004,9185) 2. À…
Exercice 4 1. À l'aide de l'algorithme d'Euclide, rendre irréductibles les fractions 3528/3780 et 1071/462. 2. Un carreleur doit recouvrir le sol d'une pièce…
Exercice 5 Si on divise 4294 et 3521 par un même entier positif, on obtient respectivement 10 et 11 comme reste. Quel est cet entier ?
Exercice 6 Soit n∈ℕ^(). On note d= PGCD(n,n+6). 1. Montrer que d divise 6. Quelles sont les valeurs possibles de d ? 2. Déterminer d selon le reste de la…
Exercice 7 1. Soient a et b deux entiers naturels non nuls et k un entier relatif tel que b-ka soit non nul. Montrer que a et b ont les mêmes diviseurs communs…
Exercice 8 Soit n∈ℕ^(), on pose a=5n+1 et b=2n-1. On note D= PGCD(a,b). 1. Démontrer que les valeurs possibles de D sont 1 ou 7. 2. Déterminer les valeurs de n…
Exercice 9 1. Soit n un entier naturel, on pose a = 7n + 4 et b = 5n + 3. Montrer, pour tout n, que a et b sont premiers entre eux. 2. Montrer que deux entiers…
Exercice 10 Montrer que les fractions suivantes sont irréductibles pour tout entier naturel n: a) n/(2n+1) b) (9n+1)/(6n+1) c) (14n+3)/(5n+1)
Exercice 11 Soit n > 5, on pose: a = n^3- n^2- 12n et b = 2n^2 - 7n - 4. 1. Démontrer que a et b sont des entiers naturels divisibles par n - 4. 2. On pose α =…

Théorème de Bézout et algorithme d'Euclide étendu

Exercice 12 1. Montrer que 87 et 31 sont premiers entre eux à l’aide de l’algorithme d’Euclide, puis, en remontant cet algorithme, déterminer un couple…
Exercice 13 · Inverse modulaire et chiffrement affine 1. À l'aide de l'algorithme d'Euclide étendu, déterminer un couple d'entiers (u,v) tel que 11u+26v=1. En déduire un entier x_0∈0,…,25 tel que…
Exercice 14 1. Déterminer les couples d’entiers relatifs (x, y) tels que: 33x - 45y = 0. 2. En déduire les couples d’entiers relatifs (x, y) tels que: 33x + 45y…
Exercice 15 1. Déterminer les couples d’entiers relatifs (x, y) tels que: 7(x - 3) = 5(y - 2). 2. En déduire les couples d’entiers relatifs (x, y) tels que: 7x…

Équations diophantiennes

Exercice 16 Soit l’équation 4x - 3y = 2. 1. Sans calcul, dire pourquoi cette équation admet des solutions entières. 2. Déterminer un couple d’entiers solution…
Exercice 17 Soit l'équation 3x - 4y = 6. 1. Déterminer un couple d’entiers solution de cette équation. 2. Déterminer l’ensemble des couples d’entiers solutions…
Exercice 18 Soit l’équation 5x + 8y = 2. 1. Déterminer un couple d’entiers solution de cette équation. 2. Déterminer l’ensemble des couples d’entiers solutions…
Exercice 19 1. L'équation 6x+9y=20 admet-elle des solutions entières ? Et l'équation 6x+9y=21 ? 2. Résoudre dans ℤ^2 l'équation 6x+9y=21. On commencera par…
Exercice 20 Soit l’équation 13x - 23y = 1. 1. Déterminer un couple d’entiers solution de cette équation par l’algorithme d’Euclide. 2. Déterminer l’ensemble des…
Exercice 21 · Points entiers d'une droite Dans un repère orthonormé, on considère la droite D d'équation 7x-4y=3. 1. Le point A(1;1) appartient-il à D ? 2. Déterminer tous les points de D…
Exercice 22 1. Démontrer que: ∀ n ∈ℤ, PGCD(14n + 3, 5n + 1) = 1. 2. On considère l’équation diophantienne suivante: (E) 87x + 31y = 2. (a) Vérifier, à l’aide de…
Exercice 23 1. On considère l’équation (E): 8x + 5y = 1, où (x, y) est un couple d'entiers. (a) Donner une solution particulière de l’équation (E). (b) Résoudre…
Exercice 24 · À la ferme Un éleveur dépense exactement 200 € pour acheter des poules à 7 € pièce et des lapins à 11 € pièce. Il achète au moins un animal de chaque sorte. 1.…
Exercice 25 28 personnes participent à un repas gastronomique. Le prix normal est de 26 € sauf pour les étudiants et les enfants qui paient respectivement 17 et…

Approfondissements

Exercice 26 · Théorème des restes chinois On veut déterminer l’ensemble S des entiers n∈ℤ vérifiant: { begin array{ll} n equiv 9 [17] n equiv 3 [5] end array. 1. Recherche d’un élément de S.…
Exercice 27 · Restes chinois avec des modules non premiers entre eux 1. Montrer qu'aucun entier n ne vérifie à la fois nequiv 1 [6] et nequiv 4 [8]. 2. On cherche les entiers n tels que nequiv 3 [6] et nequiv 5 [8].…
Exercice 28 Soit (u_n) la suite définie sur ℕ par: { begin array{ll} u_0 = 0 u_(n+1) = 4u_n + 1 end array. 1. (a) Calculer u_1, u_2 et u_3. (b) Montrer que pour…
Exercice 29 · PGCD et PPCM Soient a et b deux entiers naturels non nuls. On appelle plus petit commun multiple de a et b, noté PPCM(a,b), le plus petit entier naturel non nul…
Exercice 30 · Nombres de Fermat 1. (a) Montrer que pour tout x∈ℕ et k∈ℕ^(): x^(2k+1) + 1 = (x + 1)(x^2k - x^(2k-1) + … + x^2 - x + 1) (b) Montrer que si m est impair alors, 2^m + 1…
Exercice 31 · Cryptage RSA, tiré du BAC 2018 Le but de cet exercice est d’envisager une méthode de cryptage à clé publique d’une information numérique, appelée système RSA, en l’honneur des…

Pour aller plus loin

Exercice 32 Pour n∈ℕ, montrer que les nombres entiers 14n+3 et 21n+4 sont premiers entre eux. On explicitera une relation de Bézout.
Exercice 33 La suite de Fibonacci (F_n)_(n≥ 0) est définie par F_0=0, F_1=1 et, pour tout n∈ℕ, F_(n+2)=F_(n+1)+F_n. Pour n∈ℕ, calculer PGCD(F_n,F_(n+1)).
Exercice 34 Soit n≥ 2 un entier. On dit qu'un entier a admet un inverse modulo n s'il existe un entier x tel que axequiv 1 [n]. Montrer que n est premier si et…
Exercice 35 Soient a et b deux éléments de ℕ^(). Montrer que a et b sont premiers entre eux si et seulement si a+b et ab sont premiers entre eux.
Exercice 36 Soient a et b deux entiers relatifs premiers entre eux, (k,ell)∈ℕ^(2). a) Montrer que a^k et b sont premiers entre eux. On déduira d'une relation de…
Exercice 37 Soient u et v deux entiers supérieurs ou égaux à 2 et premiers entre eux. Montrer que le nombre (ln (v))/(ln (u)) est irrationnel.
Exercice 38 · Racines rationnelles d'un polynôme Soient n∈ℕ^(), a_0,…,a_n des entiers relatifs avec a_0a_n≠ 0, et P la fonction polynomiale définie par P(x)= Σ_(k=0)^na_kx^k. a) Soit r une racine…
Exercice 39 · L'équation diophantienne $ax+by=c$ Soient a et b deux éléments de ℕ^() et c∈ℤ. On note δ le PGCD de a et b. On se propose de déterminer l'ensemble E des couples (x,y)∈ℤ^2 tels que…
Exercice 40 Selon la valeur de n∈ℤ, déterminer le PGCD de n^3+n et 2n+1.
Exercice 41 En utilisant l'exercice 31 du chapitre 1, montrer que, si a≥ 2 est un entier, m et n deux éléments de ℕ^(), alors a^m-1 et a^n-1 ont pour PGCD…
Exercice 42 · Relation de Bézout à coefficients dans $\mathbb{N}$ Soient a et b deux éléments de ℕ^() premiers entre eux. a) Montrer que ab-a-b n'est pas de la forme au+bv avec u et v dans ℕ. b) Montrer que si n…