Avancer

Section 11.3 Exercices

Effectuez les divisions euclidiennes suivantes, puis identifiez le quotient et le reste.

  1. \(14\) divisé par \(3\text{.}\)

  2. \(55\) divisé par \(27\text{.}\)

  3. \(257\) divisé par \(21\text{.}\)

  4. \(2031\) divisé par \(142\text{.}\)

  5. \(-347\) divisé par \(22\text{.}\)

Réponse

  1. \(14=3\cdot 4+2\) où quotient \(=4\) et reste \(=2\text{.}\)

  2. \(55=27\cdot 2+1\) où quotient \(=2\) et reste \(=1\text{.}\)

  3. \(257=21\cdot 12+5\) où quotient \(=12\) et reste \(=5\text{.}\)

  4. \(2031=142\cdot 14+43\) où quotient \(=14\) et reste \(=43\text{.}\)

  5. \(-347=22\cdot (-16)+5\) où quotient \(=-16\) et reste \(=5\text{.}\)

Parmi les nombres suivants, lesquels sont-ils premiers?

\begin{equation*} 2,\; 8,\; 11,\; 15,\; 19,\; 23,\; 24,\; 35,\; 57,\; 67,\; 69,\; 84,\; 89,\; 257,\; 65\,537. \end{equation*}
Réponse
\begin{equation*} 2,\;11,\; 19,\; 23,\; 67,\; 89,\; 257,\;65\,537. \end{equation*}

Remarque : Voir \(65\,537\) pour le dernier.

Décomposez les nombres suivants en produits de facteurs premiers.

  1. \(19\text{.}\)

  2. \(36\text{.}\)

  3. \(38\text{.}\)

  4. \(39\text{.}\)

  5. \(54\text{.}\)

  6. \(2\,178\,309\text{.}\)

Réponse

  1. \(19=19\text{.}\)

  2. \(36=2^2\cdot 3^2\text{.}\)

  3. \(38=2\cdot 19\text{.}\)

  4. \(39=3\cdot 13\text{.}\)

  5. \(54=2\cdot 3^3\text{.}\)

  6. \(2\,178\,309=3\cdot 7\cdot 47\cdot 2207\).

Dressez la liste de tous les diviseurs positifs des nombres suivants.

  1. \(19\text{.}\)

  2. \(36\text{.}\)

  3. \(38\text{.}\)

  4. \(39\text{.}\)

  5. \(54\text{.}\)

  6. \(2\,178\,309\text{.}\)

Réponse

  1. \(1, 19\text{.}\)

  2. \(1, 2, 3, 4, 6, 9, 12, 18, 36\text{.}\)

  3. \(1, 2, 19, 38\text{.}\)

  4. \(1, 3, 13, 39\text{.}\)

  5. \(1, 2, 3, 6, 9, 18, 27, 54\text{.}\)

  6. \(1, 3, 7, 21, 47, 141, 329, 987, 2\,207, 6\,621, 15\,449, 46\,347, 103\,729, 311\,187, 726\,103, 2\,178\,309\text{.}\)

    Cliquez ici pour voir comment j'ai obtenu cette liste.

Dressez la liste de tous les diviseurs positifs communs à \(a\) et à \(b\text{,}\) puis déduisez-en la valeur de \(\text{PGCD}(a;b)\text{.}\)

  1. Pour \(a=36\) et \(b=54\text{.}\)

  2. Pour \(a=57\) et \(b=42\text{.}\)

Solution

    • Diviseurs positifs de \(36\) : \(1, 2, 3, 4, 6, 9, 12, 18, 36\text{.}\)

    • Diviseurs positifs de \(54\) : \(1, 2, 3, 6, 9, 18, 27, 54\text{.}\)

    • Donc les diviseurs positifs communs sont \(1, 2, 3, 6, 9, 18\) et

      \begin{equation*} \text{PGCD}(36;54)=18. \end{equation*}

    • Diviseurs positifs de \(57\) : \(1, 3, 19, 57\text{.}\)

    • Diviseurs positifs de \(42\) : \(1, 2, 3, 6, 7, 14, 21, 42\text{.}\)

    • Donc les diviseurs positifs communs sont \(1, 3\) et

      \begin{equation*} \text{PGCD}(57;42)=3. \end{equation*}

Calculez \(\text{PGCD}(a;b)\) à l'aide de l'algorithme d'Euclide.

  1. Pour \(a=363\) et \(b=198\text{.}\)

  2. Pour \(a=2784\) et \(b=3410\text{.}\)

  3. Pour \(a=2784\) et \(b=1180\text{.}\)

Solution

  1. On a

    \begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 363&198&363=198\cdot 1+165&165\\ 198&165&198=165\cdot 1+33&33\\ 165&33&165=33\cdot 5+0&0\\ \hline \end{array} \end{equation*}

    Donc \(\text{PGCD}(363;198)=33\text{.}\)

  2. On a

    \begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 3410&2784&3410=2784\cdot 1+626&626\\ 2784&626&2784=626\cdot 4+280&280\\ 626&280&626=280\cdot 2+66&66\\ 280&66&280=66\cdot 4+16&16\\ 66&16&66=16\cdot 4+2&2\\ 16&2&16=2\cdot 8+0&0\\ \hline \end{array} \end{equation*}

    Donc \(\text{PGCD}(2784;3410)=2\text{.}\)

  3. On a

    \begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 2784&1180&2784=1180\cdot 2+424&424\\ 1180&424&1180=424\cdot 2+332&332\\ 424&332&424=332\cdot 1+92&92\\ 332&92&332=92\cdot 3+56&56\\ 92&56&92=56\cdot 1+36&36\\ 56&36&56=36\cdot 1+20&20\\ 36&20&36=20\cdot 1+16&16\\ 20&16&20=16\cdot 1+4&4\\ 16&4&16=4\cdot 4+0&0\\ \hline \end{array} \end{equation*}

    Donc \(\text{PGCD}(2784;1180)=4\text{.}\)

Créez une fonction récursive pgcd(a, b) qui renvoie le PGCD de deux entiers naturels \(\text{a}\geq\text{b}\text{.}\)

Testez votre code avec \(\text{PGCD}(43\,569;28\,476)=9\text{.}\)

Solution
# fonction :
def pgcd(a, b):
    if b == 0:
        return a
    else:
        return pgcd(b, a % b)

# test :
print(pgcd(43569, 28476))

Vérifiez le théorème de Lamé dans chacun des cas suivants.

  1. \(a=120\) et \(b=77\text{.}\)

  2. \(a=144\) et \(b=89\text{.}\)

  3. \(a=2584\) et \(b=1597\text{.}\)

  4. \(a=10946\) et \(b=6765\text{.}\)

Solution

  1. L'algorithme d'Euclide nécessite \(7\) divisions, nombre qui est bien majoré par \(5\times 2=10\text{.}\)

  2. L'algorithme d'Euclide nécessite \(10\) divisions, nombre qui est bien majoré par \(5\times 2=10\text{.}\)

  3. L'algorithme d'Euclide nécessite \(16\) divisions, nombre qui est bien majoré par \(5\times 4=20\text{.}\)

  4. L'algorithme d'Euclide nécessite \(19\) divisions, nombre qui est bien majoré par \(5\times 4=20\text{.}\)

Remarque : Dans les trois derniers cas, il s'agit de nombres de Fibonacci consécutifs, lesquels sont connus pour fournir les cas limites du théorème de Lamé.

On désire paver une pièce rectangulaire de \(3{,}52\) mètres de largeur et de \(9{,}28\) mètres de longueur par des carrés dont le côté est un nombre entier de centimètres.

Quelle doit être, en centimètres, la mesure du côté pour que le nombre de carrés utilisés soit le plus petit possible?

Remarque : Cet exercice est tiré des excellentes notes de cours de Laurent Godefroy, avec l'accord de leur auteur.

Réponse

\(\text{PGCD}(325;928)=32\)

Solution

Pour que le pavage soit possible, il faut que la mesure du côté soit un diviseur commun à \(352\) et \(928\text{.}\)

Pour minimiser le nombre de carrés utilisés, il faut choisir le plus grand diviseur commun, c'est-à-dire \(\text{PGCD}(325;928)=32\text{.}\)

Le but de cet exercice est d'apprendre à appliquer l'algorithme d'Euclide de façon matricielle, et de découvrir au passage l'objet du chapitre suivant qui est consacré à l'algorithme d'Euclide étendu.

  1. Soit \(a,b,q,r\) quatre nombres tels que

    \begin{equation*} a=b\cdot q+r. \end{equation*}

    Vérifiez qu'on a

    \begin{equation*} \begin{bmatrix}0&1\\1&-q\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}=\begin{bmatrix}b\\r\end{bmatrix}. \end{equation*}

  2. La première étape de l'algorithme d'Euclide menant au calcul de \(\text{PGCD}(2589;234)\) consiste en la division euclidienne

    \begin{equation*} 2589=234\cdot 11+15. \end{equation*}

    Donnez une matrice \(2\times 2\) \(M_1\) telle que

    \begin{equation*} M_1\begin{bmatrix}2589\\234\end{bmatrix}=\begin{bmatrix}234\\15\end{bmatrix}. \end{equation*}

  3. La deuxième étape de l'algorithme d'Euclide menant au calcul de \(\text{PGCD}(2589;234)\) consiste en la division euclidienne

    \begin{equation*} 234=15\cdot 15+9. \end{equation*}

    Donnez une matrice \(2\times 2\) \(M_2\) telle que

    \begin{equation*} M_2\begin{bmatrix}234\\15\end{bmatrix}=\begin{bmatrix}15\\9\end{bmatrix}. \end{equation*}

  4. Vérifiez qu'on a

    \begin{equation*} M_2M_1\begin{bmatrix}2589\\234\end{bmatrix}=\begin{bmatrix}15\\9\end{bmatrix}. \end{equation*}

  5. Continuez ainsi afin d'obtenir des matrices \(2\times 2\) \(M_3,M_4,M_5\) telles que

    \begin{equation*} M_5M_4M_3M_2M_1\begin{bmatrix}2589\\234\end{bmatrix}=\begin{bmatrix}3\\0\end{bmatrix}. \end{equation*}

  6. Déterminez la matrice \(M=M_5M_4M_3M_2M_1\text{.}\)

  7. En déduire un couple d'entiers relatifs \((u;v)\in\mathbb{Z}^2\) tels que

    \begin{equation*} 2589u+234v=3. \end{equation*}
Solution

  1. Par définition du produit matriciel, on a

    \begin{align*} \begin{bmatrix}0&1\\1&-q\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}&=\begin{bmatrix}0\cdot a+1\cdot b\\1\cdot a-q\cdot b\end{bmatrix}\\ &=\begin{bmatrix}b\\r\end{bmatrix}. \end{align*}

  2. D'après ce qui précède, il suffit de prendre

    \begin{equation*} M_1=\begin{bmatrix}0&1\\1&-11\end{bmatrix}. \end{equation*}

  3. Il suffit de prendre

    \begin{equation*} M_2=\begin{bmatrix}0&1\\1&-15\end{bmatrix}. \end{equation*}

  4. Par associativité, on a

    \begin{equation*} (M_2M_1)\begin{bmatrix}2589\\234\end{bmatrix}=M_2\left(M_1\begin{bmatrix}2589\\234\end{bmatrix}\right)=M_2\begin{bmatrix}234\\15\end{bmatrix}=\begin{bmatrix}15\\9\end{bmatrix}. \end{equation*}

  5. En observant les quotients des trois dernières étapes de l'algorithme d'Euclide menant au calcul de \(\text{PGCD}(2589;234)\text{,}\) on voit qu'il suffit de prendre

    \begin{equation*} M_3=\begin{bmatrix}0&1\\1&-1\end{bmatrix}, M_4=\begin{bmatrix}0&1\\1&-1\end{bmatrix}\text{ et }M_5=\begin{bmatrix}0&1\\1&-2\end{bmatrix}. \end{equation*}

  6. Un peu de calcul matriciel montre que \(M_5M_4M_3M_2M_1\) donne la matrice

    \begin{align*} &\begin{bmatrix}0&1\\1&-2\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}\begin{bmatrix}0&1\\1&-15\end{bmatrix}\begin{bmatrix}0&1\\1&-11\end{bmatrix}\\ =&\begin{bmatrix}0&1\\1&-2\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}\begin{bmatrix}1&-11\\-15&166\end{bmatrix}\\ =&\begin{bmatrix}0&1\\1&-2\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}\begin{bmatrix}-15&166\\16&-177\end{bmatrix}\\ =&\begin{bmatrix}0&1\\1&-2\end{bmatrix}\begin{bmatrix}16&-177\\-31&343\end{bmatrix}\\ =&\begin{bmatrix}-31&343\\78&-863\end{bmatrix}. \end{align*}

  7. D'après ce qui précède, on sait que

    \begin{equation*} M_5M_4M_3M_2M_1\begin{bmatrix}2589\\234\end{bmatrix}=\begin{bmatrix}3\\0\end{bmatrix}, \end{equation*}

    c'est-à-dire

    \begin{equation*} \begin{bmatrix}-31&343\\78&-863\end{bmatrix}\begin{bmatrix}2589\\234\end{bmatrix}=\begin{bmatrix}3\\0\end{bmatrix}. \end{equation*}

    La première ligne de cette identité matricielle donne

    \begin{equation*} (-31)\cdot 2589+343\cdot 234=3, \end{equation*}

    soit

    \begin{equation*} 2589u+234v=3\quad\text{avec }(u;v)=(-31;343). \end{equation*}