Petit théorème de Fermat : restes et divisibilité - Exercice 1

15 min
25
Question 1

Déterminer le reste de la division euclidienne de 320263^{2026} par 77.

Correction
    Petit theˊoreˋme de Fermat\red{\text{Petit théorème de Fermat}}
  • p\blue{p} désigne un nombre premier et a\pink{a} un nombre entier naturel non divisible par p\blue{p} .
    Alors ap−1−1\pink{a}^{\blue{p}-1}-1 est divisible par pp c'est-à-dire ap−1≡1[p]\pink{a}^{\blue{p}-1} \equiv 1\left[\blue{p}\right]
    • 7\blue{7} est un nombre premier.
    3\pink{3} est non divisible par 7\blue{7} .
    D'après le petit théorème de Fermat on a alors : 37−1≡1[7]\pink{3}^{\blue{7}-1} \equiv 1\left[\blue{7}\right]
    Autrement dit : 36≡1[7]3^{6} \equiv 1\left[7\right]
    Effectuons la division euclidienne de 2  0262\;026 par 66 : 2  026=6×337+42\;026=6\times 337+4
    Ainsi : 32026=36×337+4=(36)337×343^{2026}=3^{6\times 337+4}=\left(3^{6}\right)^{337}\times 3^{4}
  • Soient mm un entier naturel (m≥2)\left(m\geq 2\right), aa et bb des entiers relatifs vérifiant : a≡b[m]a \equiv b\left[m\right] .
    Pour tout k∈Nk\in \mathbb{N} on a : ak≡bk[m]a^{k} \equiv b^{k}\left[m\right]
    • Or 36≡1[7]3^{6}\equiv 1\left[7\right], donc (36)337≡1337[7]\left(3^{6}\right)^{337}\equiv 1^{337}\left[7\right], c'est-à-dire (36)337≡1[7]\left(3^{6}\right)^{337}\equiv 1\left[7\right].
    De plus 34=81=11×7+43^{4}=81=11\times 7+4, donc 34≡4[7]3^{4}\equiv 4\left[7\right].
    La congruence est compatible avec le produit\red{\text{avec le produit}} :
  • Soient mm un entier naturel (m≥2)\left(m\geq 2\right), aa,bb,cc et dd des entiers relatifs vérifiant : a≡b[m]\red{a} \equiv \red{b}\left[m\right] et c≡d[m]\blue{c} \equiv \blue{d}\left[m\right].
    Alors : a×c≡b×d[m]\red{a}\times\blue{c} \equiv \red{b}\times\blue{d}\left[m\right]
    • On a donc : (36)337×34≡1×4[7]\left(3^{6}\right)^{337}\times 3^{4}\equiv 1\times 4\left[7\right]
    32026≡4[7]3^{2026}\equiv 4\left[7\right]
    On peut le visualiser à l'aide d'un cycle : les restes de 3n3^{n} modulo 77 se répètent tous les 66 rangs, et 2  0262\;026 est de la forme 6k+46k+4 :
    Comme 0≤4<70\le 4\lt 7 :
    Le reste de la division euclidienne de 320263^{2026} par 77 est 44
    Question 2

    Déterminer le reste de la division euclidienne de 210002^{1000} par 1313.

    Correction
      Petit theˊoreˋme de Fermat\red{\text{Petit théorème de Fermat}}
  • p\blue{p} désigne un nombre premier et a\pink{a} un nombre entier naturel non divisible par p\blue{p} .
    Alors ap−1−1\pink{a}^{\blue{p}-1}-1 est divisible par pp c'est-à-dire ap−1≡1[p]\pink{a}^{\blue{p}-1} \equiv 1\left[\blue{p}\right]
    • 13\blue{13} est un nombre premier.
    2\pink{2} est non divisible par 13\blue{13} .
    D'après le petit théorème de Fermat on a alors : 213−1≡1[13]\pink{2}^{\blue{13}-1} \equiv 1\left[\blue{13}\right]
    Autrement dit : 212≡1[13]2^{12} \equiv 1\left[13\right]
    Effectuons la division euclidienne de 1  0001\;000 par 1212 : 1  000=12×83+41\;000=12\times 83+4
    Ainsi : 21000=(212)83×242^{1000}=\left(2^{12}\right)^{83}\times 2^{4}
    Or 212≡1[13]2^{12}\equiv 1\left[13\right], donc (212)83≡1[13]\left(2^{12}\right)^{83}\equiv 1\left[13\right].
    De plus 24=16=1×13+32^{4}=16=1\times 13+3, donc 24≡3[13]2^{4}\equiv 3\left[13\right].
    On a donc : 21000≡1×3[13]2^{1000}\equiv 1\times 3\left[13\right], c'est-à-dire 21000≡3[13]2^{1000}\equiv 3\left[13\right].
    Comme 0≤3<130\le 3\lt 13 :
    Le reste de la division euclidienne de 210002^{1000} par 1313 est 33

    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.