Exercices types : 3ᵉ partie - Exercice 4

20 min
35
On considère la fonction Python ci-dessous, où a ** k désigne aka^{k} et a ** k % m le reste de la division euclidienne de aka^{k} par mm.
Question 1

Que renvoie l'instruction restes(2, 7, 7) ?

Correction
La boucle calcule, pour kk allant de 00 à 77, le reste de la division euclidienne de 2k2^{k} par 77 :
20=12^{0}=1 ; 21=22^{1}=2 ; 22=42^{2}=4 ; 23=8≡12^{3}=8\equiv 1 ; 24=16≡22^{4}=16\equiv 2 ; 25=32≡42^{5}=32\equiv 4 ; 26=64≡12^{6}=64\equiv 1 ; 27=128≡2[7]2^{7}=128\equiv 2\left[7\right]
L'instruction renvoie la liste
[1, 2, 4, 1, 2, 4, 1, 2]
Question 2

Quelle conjecture peut-on faire ? La démontrer.

Correction
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].
  • a+c≡b+d[m]\red{a}+\blue{c} \equiv \red{b}+\blue{d}\left[m\right]
  • a×c≡b×d[m]\red{a}\times\blue{c} \equiv \red{b}\times\blue{d}\left[m\right]
  • Pour tout entier naturel kk : ak≡bk[m]\red{a}^{k} \equiv \red{b}^{k}\left[m\right]
    • Conjecture :\red{\text{Conjecture :}} les restes se répètent dans l'ordre 11, 22, 44 : la suite des restes est périodique, de période 33.
    Deˊmonstration :\red{\text{Démonstration :}} 23=8≡1[7]2^{3}=8\equiv 1\left[7\right]. Pour tout entier naturel kk : 2k+3=2k×23≡2k×1≡2k[7]2^{k+3}=2^{k}\times 2^{3}\equiv 2^{k}\times 1\equiv 2^{k}\left[7\right].
    Les nombres 2k+32^{k+3} et 2k2^{k} ont donc le même reste :
    la suite des restes est périodique de période 33
    Question 3

    Le calcul de a ** k devient très long lorsque kk est grand. Compléter la ligne 6 de la fonction ci-dessous pour qu'elle calcule chaque reste à partir du précédent.

    Correction
    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].
  • a+c≡b+d[m]\red{a}+\blue{c} \equiv \red{b}+\blue{d}\left[m\right]
  • a×c≡b×d[m]\red{a}\times\blue{c} \equiv \red{b}\times\blue{d}\left[m\right]
  • Pour tout entier naturel kk : ak≡bk[m]\red{a}^{k} \equiv \red{b}^{k}\left[m\right]
    • Si rr est le reste de aka^{k}, alors ak≡r[m]a^{k}\equiv r\left[m\right], donc ak+1=ak×a≡r×a[m]a^{k+1}=a^{k}\times a\equiv r\times a\left[m\right] : le reste suivant est le reste de la division euclidienne de r×ar\times a par mm.
    Les nombres manipulés restent ainsi inférieurs à m×am\times a : le calcul est rapide même pour de grandes valeurs de NN.

    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.