Systèmes de congruences : le lemme chinois - Exercice 1

30 min
50
On cherche tous les entiers relatifs nn tels que : n≡2[7]n\equiv 2\left[7\right] et n≡3[5]n\equiv 3\left[5\right].
Question 1

Justifier qu'il existe deux entiers relatifs aa et bb tels que n=2+7an=2+7a et n=3+5bn=3+5b, puis que 7a−5b=17a-5b=1.

Correction
Soit nn un entier naturel (n≥2)\left(n\geq 2\right).
  • a≡b[n]a\equiv b\left[n\right] si et seulement si nn divise a−ba-b, c'est-à-dire s'il existe un entier relatif kk tel que a=b+kna=b+kn.
    • n≡2[7]n\equiv 2\left[7\right] : il existe un entier relatif aa tel que n=2+7an=2+7a.
    n≡3[5]n\equiv 3\left[5\right] : il existe un entier relatif bb tel que n=3+5bn=3+5b.
    Ainsi 2+7a=3+5b2+7a=3+5b, c'est-à-dire :
    7a−5b=17a-5b=1
    Question 2

    Résoudre l'équation 7a−5b=17a-5b=1, d'inconnues entières aa et bb (on remarquera que le couple (3;4)\left(3;4\right) est une solution).

    Correction
    Theˊoreˋme de Gauss\text{Théorème de Gauss} : soient aa, bb et cc trois entiers relatifs non nuls.
  • Si aa divise le produit bcbc et si aa et bb sont premiers entre eux, alors aa divise cc.
    • Vérification : 7×3−5×4=21−20=17\times 3-5\times 4=21-20=1.
    D’une part :\text{D'une part :} 7a−5b=17a-5b=1 ; D’autre part :\text{D'autre part :} 7×3−5×4=17\times 3-5\times 4=1.
    En soustrayant : 7(a−3)=5(b−4)\pink{7\left(a-3\right)=5\left(b-4\right)}.
    55 divise 7(a−3)7\left(a-3\right) et PGCD(5;7)=1\text{PGCD}\left(5;7\right)=1 : d'après le théorème de Gauss, 55 divise a−3a-3, donc a=3+5ka=3+5k où k∈Zk\in \mathbb{Z}.
    En remplaçant : 7×5k=5(b−4)7\times 5k=5\left(b-4\right), donc b−4=7kb-4=7k et b=4+7kb=4+7k.
    Réciproquement : 7(3+5k)−5(4+7k)=21+35k−20−35k=17\left(3+5k\right)-5\left(4+7k\right)=21+35k-20-35k=1.
    a=3+5ka=3+5k et b=4+7kb=4+7k où k∈Zk\in \mathbb{Z}
    Question 3

    En déduire les entiers nn cherchés.

    Correction
    D'après les questions 11 et 22 : n=2+7a=2+7(3+5k)=23+35kn=2+7a=2+7\left(3+5k\right)=23+35k où k∈Zk\in \mathbb{Z}.
    Réciproquement, si n=23+35kn=23+35k : n=2+7(3+5k)n=2+7\left(3+5k\right) donc n≡2[7]n\equiv 2\left[7\right], et n=3+5(4+7k)n=3+5\left(4+7k\right) donc n≡3[5]n\equiv 3\left[5\right].
    Vérification avec n=23n=23 : 23=7×3+223=7\times 3+2 et 23=5×4+323=5\times 4+3.
    n≡2[7]n\equiv 2\left[7\right] et n≡3[5]n\equiv 3\left[5\right]   ⟺  \iff n≡23[35]n\equiv 23\left[35\right]

    Les deux congruences se résument en une seule, modulo 7×5=357\times 5=35 : c'est le lemme chinois (il s'applique car 77 et 55 sont premiers entre eux).

    Signaler une erreur

    Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

    Connecte-toi ou crée un compte pour signaler une erreur.