PGCD, théorèmes de Bézout et de Gauss
🔴 Expert📝 Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.
- 1
On dispose de pièces de 7 centimes et de 11 centimes.
a) Détermine un couple (x, y) d'entiers tel que 7x + 11y = 1.
b) En déduire toutes les solutions entières de 7x + 11y = 100.
c) Combien existe-t-il de façons d'obtenir exactement 100 centimes avec un nombre positif ou nul de chaque pièce ? Précise la (ou les) solution(s).✅ Voir le corrigéoffert
a) Algorithme d'Euclide sur 11 et 7 :
11 = 7×1 + 4 ; 7 = 4×1 + 3 ; 4 = 3×1 + 1.
1 = 4 − 3 = 4 − (7 − 4) = 2×4 − 7 = 2×(11 − 7) − 7 = 2×11 − 3×7.
Donc 7×(−3) + 11×2 = 1 : le couple (x, y) = (−3, 2) convient (−21 + 22 = 1).
b) En multipliant l'identité par 100 : 7×(−300) + 11×200 = 100. Une solution particulière est (x₀, y₀) = (−300, 200).
Soit (x, y) une solution : 7(x + 300) = −11(y − 200). Comme PGCD(7, 11) = 1, le théorème de Gauss donne 11 | (x + 300), donc x + 300 = 11k, soit x = −300 + 11k.
Alors 7×11k = −11(y − 200), d'où y − 200 = −7k, y = 200 − 7k.
Solutions : (x, y) = (−300 + 11k ; 200 − 7k), k ∈ ℤ.
c) On impose x ≥ 0 et y ≥ 0.
x ≥ 0 : −300 + 11k ≥ 0 ⇔ k ≥ ≈ 27,3, donc k ≥ 28.
y ≥ 0 : 200 − 7k ≥ 0 ⇔ k ≤ ≈ 28,6, donc k ≤ 28.
La seule valeur possible est k = 28 : x = −300 + 308 = 8 et y = 200 − 196 = 4.
Il existe donc une seule façon : 8 pièces de 7 centimes et 4 pièces de 11 centimes (vérification : 8×7 + 4×11 = 56 + 44 = 100). - 2
a) Détermine un couple (u, v) d'entiers tel que 26u + 15v = 1.
b) En déduire un inverse de 15 modulo 26, c'est-à-dire un entier k tel que 15k ≡ 1 (mod 26).
c) Résous alors la congruence 15x ≡ 4 (mod 26).✅ Voir le corrigéoffert
a) Algorithme d'Euclide :
26 = 15×1 + 11 ; 15 = 11×1 + 4 ; 11 = 4×2 + 3 ; 4 = 3×1 + 1.
1 = 4 − 3 = 4 − (11 − 4×2) = 3×4 − 11 = 3×(15 − 11) − 11 = 3×15 − 4×11 = 3×15 − 4×(26 − 15) = 7×15 − 4×26.
Donc 26×(−4) + 15×7 = 1 : (u, v) = (−4, 7) (vérification : −104 + 105 = 1).
b) L'égalité 15×7 = 1 + 26×4 donne 15×7 ≡ 1 (mod 26). Donc 7 est un inverse de 15 modulo 26.
c) On part de 15x ≡ 4 (mod 26). On multiplie les deux membres par 7 (inverse de 15) :
7×15×x ≡ 7×4 (mod 26), soit x ≡ 28 (mod 26).
Comme 28 = 26 + 2, on a x ≡ 2 (mod 26).
Vérification : 15×2 = 30 = 26 + 4 ≡ 4 (mod 26).
Les solutions sont tous les entiers x tels que x ≡ 2 (mod 26). - 3
Un libraire vend des livres à 13 € et des cahiers à 8 €. Un client dépense exactement 100 €.
a) Écris l'équation vérifiée par le nombre x de livres et le nombre y de cahiers, puis résous 13x + 8y = 1.
b) Donne toutes les solutions entières de 13x + 8y = 100.
c) Détermine tous les achats possibles (x ≥ 0, y ≥ 0).🔒 Corrigé réservé aux abonnésS'abonner → - 4
Soit n un entier relatif et d = PGCD(n + 2, 3n + 1).
a) Montre que d divise 5.
b) En déduire les valeurs possibles de d.
c) Détermine les entiers n pour lesquels d = 5.🔒 Corrigé réservé aux abonnésS'abonner → - 5
Soit n un entier relatif et d = PGCD(2n − 1, 3n + 2).
a) Montre que d divise 7.
b) Quelles sont les valeurs possibles de d ?
c) Pour quels entiers n a-t-on d = 7 ?🔒 Corrigé réservé aux abonnésS'abonner → - 6
a) Détermine un couple (u, v) tel que 15u + 11v = 1.
b) En déduire une solution particulière de 15x + 11y = 7.
c) Donne toutes les solutions entières de 15x + 11y = 7.🔒 Corrigé réservé aux abonnésS'abonner → - 7
Soit n un entier naturel.
a) Calcule 7×(5n + 3) − 5×(7n + 4).
b) En déduire que la fraction est irréductible pour tout n ∈ ℕ.
c) Donne, en fonction de n, un couple de Bézout (u, v) tel que (5n + 3)u + (7n + 4)v = 1.🔒 Corrigé réservé aux abonnésS'abonner → - 8
On cherche les entiers n vérifiant à la fois n ≡ 2 (mod 5) et n ≡ 1 (mod 7).
a) Détermine l'inverse de 5 modulo 7 à l'aide d'une identité de Bézout.
b) Résous le système et exprime n sous la forme n ≡ r (mod 35).
c) Donne le plus petit entier naturel n solution.🔒 Corrigé réservé aux abonnésS'abonner → - 9
On considère l'équation 8x + 5y = 120 avec x et y entiers naturels (x ≥ 0, y ≥ 0).
a) Donne une solution particulière évidente.
b) Détermine la forme générale de toutes les solutions entières.
c) Combien y a-t-il de couples (x, y) d'entiers naturels solutions ? Liste-les.🔒 Corrigé réservé aux abonnésS'abonner → - 10
Soient a et b deux entiers premiers entre eux.
a) Montre que PGCD(a, a + b) = 1.
b) Montre de même que PGCD(b, a + b) = 1.
c) À l'aide de deux identités de Bézout que l'on multipliera, montre que PGCD(ab, a + b) = 1.🔒 Corrigé réservé aux abonnésS'abonner →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.