Mathématiques et algorithmique

1. Vrai car \(14-2=12=6\cdot 2\) est divisible par \(6\text{.}\)

2. Vrai car \(14-0=14=7\cdot 2\) est divisible par \(7\text{.}\)

3. Faux car \(14-(-22)=36=8\cdot 4+4\) n'est pas divisible par \(8\text{.}\)

4. Vrai car \(14-(-13)=27=9\cdot 3\) est divisible par \(9\text{.}\)

5. Faux car \(25040432829023\equiv 3\;\mathrm{mod}\;10\) tandis que \(13907346592457\equiv 7\;\mathrm{mod}\;10\text{.}\)

1. \(-67,\;-25,\;17,\;59,\;101,\;143\text{.}\)

2. \(-59,\;-17,\;25,\;67,\;109\text{.}\)

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

La réponse est donnée par le reste de la division euclidienne de \(5+208=213\) par \(12\text{,}\) soit \(9\) heures, car

Principe : Calculer le reste \(r\) de la division euclidienne de \(ua\) par \(m\text{.}\) Alors \(u\) est un inverse de \(a\) modulo \(m\) si et seulement si \(r=1\text{.}\)

1. On a

   \begin{equation*} \begin{array}{cccr} ua&=&7\cdot 4\\ &=&28\\ &\equiv&2\;\mathrm{mod}\;26&\text{ car }28=26\cdot 1+2. \end{array} \end{equation*}

   Donc \(u=7\) n'est pas un inverse de \(a=4\) modulo \(m=26\text{.}\)

2. On a

   \begin{equation*} \begin{array}{cccr} ua&=&69\cdot 4\\ &=&276\\ &\equiv&1\;\mathrm{mod}\;25&\text{ car }276=25\cdot 11+1.\\ \end{array} \end{equation*}

   Donc \(u=69\) est un inverse de \(a=4\) modulo \(m=25\text{.}\)

3. On a

   \begin{equation*} \begin{array}{cccr} ua&=&3\cdot(-34)\\ &=&-102\\ &\equiv&6\;\mathrm{mod}\;9&\text{ car }-102=9\cdot(-12)+6.\\ \end{array} \end{equation*}

   Donc \(u=3\) n'est pas un inverse de \(a=-34\) modulo \(m=9\text{.}\)

4. On a

   \begin{equation*} \begin{array}{cccr} ua&=&(-536)\cdot 1954\\ &=&-1047344\\ &\equiv&1\;\mathrm{mod}\;205&\text{ car }-1047344=205\cdot(-5109)+1.\\ \end{array} \end{equation*}

   Donc \(u=-536\) est un inverse de \(a=1954\) modulo \(m=205\text{.}\)

5. On a

   \begin{equation*} \begin{array}{cccr} ua&=&3\cdot 0\\ &=&0\\ &\equiv&0\;\mathrm{mod}\;5&\text{ car }0=5\cdot 0+0.\\ \end{array} \end{equation*}

   Donc \(u=3\) n'est pas un inverse de \(a=0\) modulo \(m=5\text{.}\)

1. Non, car \(\text{PGCD}(4;26)=2\neq 1\text{.}\)

2. Oui, car \(\text{PGCD}(4;25)=1\text{.}\)

   Grâce à l'algorithme d'Euclide étendu, on obtient la combinaison linéaire

   \begin{equation*} 1=4\cdot (-6)+25\cdot 1. \end{equation*}

   Donc \(u_0=-6\) est un inverse de \(4\) modulo \(25\text{.}\)

   De plus, l'ensemble des inverses de \(4\) modulo \(25\) correspond à la progression arithmétique

   \begin{equation*} \left\{-6+25k\,|\,k\in\mathbb{Z}\right\} \end{equation*}

   soit

   \begin{equation*} \left\{\ldots,\;-6-25,\;-6,\;-6+25,\;-6+25\cdot 2,\;\ldots\right\}. \end{equation*}

   Le plus petit inverse positif de \(4\) modulo \(25\) est donc

   \begin{equation*} -6+25=19. \end{equation*}

3. Oui, car \(\text{PGCD}(-34;9)=1\text{.}\)

   Grâce à l'algorithme d'Euclide étendu, on obtient la combinaison linéaire

   \begin{equation*} 1=(-34)\cdot(-4)+9\cdot(-15). \end{equation*}

   Donc \(u_0=-4\) est un inverse de \(-34\) modulo \(9\text{.}\)

   De plus, l'ensemble des inverses de \(-34\) modulo \(9\) correspond à la progression arithmétique

   \begin{equation*} \left\{-4+9k\,|\,k\in\mathbb{Z}\right\} \end{equation*}

   soit

   \begin{equation*} \left\{\ldots,\;-4-9,\;-4,\;-4+9,\;-4+9\cdot 2,\;\ldots\right\}. \end{equation*}

   Le plus petit inverse positif de \(4\) modulo \(25\) est donc

   \begin{equation*} -4+9=5. \end{equation*}

4. Oui, car \(\text{PGCD}(1954;205)=1\text{.}\)

   Grâce à l'algorithme d'Euclide étendu, on obtient la combinaison linéaire

   \begin{equation*} 1=1954\cdot 79+205\cdot(-753). \end{equation*}

   Donc \(u_0=79\) est un inverse de \(1954\) modulo \(205\text{.}\)

   De plus, l'ensemble des inverses de \(1954\) modulo \(205\) correspond à la progression arithmétique

   \begin{equation*} \left\{79+205k\,|\,k\in\mathbb{Z}\right\} \end{equation*}

   soit

   \begin{equation*} \left\{\ldots,\;79-205,\;79,\;79+205,\;79+205\cdot 2,\;\ldots\right\}. \end{equation*}

   Le plus petit inverse positif de \(1954\) modulo \(205\) est donc

   \begin{equation*} 79. \end{equation*}

5. Non, car \(\text{PGCD}(0;5)=5\neq 1\text{.}\)

1. \begin{equation*} \begin{array}{|c|*{5}{c}|} \hline k&1&2&3&4&5\\ \hline \text{reste de }2^k/5&2&4&3&1&2\\ \hline \end{array} \end{equation*}
2. \begin{equation*} \begin{array}{|c|*{11}{c}|} \hline k&1&2&3&4&5&6&7&8&9&10&11\\ \hline \text{reste de }2^k/11&2&4&8&5&10&9&7&3&6&1&2\\ \hline \end{array} \end{equation*}
3. \begin{equation*} \begin{array}{|c|*{11}{c}|} \hline k&1&2&3&4&5&6&7&8&9&10&11\\ \hline \text{reste de }3^k/11&3&9&5&4&1&3&9&5&4&1&3\\ \hline \end{array} \end{equation*}
4. \begin{equation*} \begin{array}{|c|*{11}{c}|} \hline k&1&2&3&4&5&6&7&8&9&10&11\\ \hline \text{reste de }(-1)^k/11&10&1&10&1&10&1&10&1&10&1&10\\ \hline \end{array} \end{equation*}

5. Comme \(a=38\equiv 1\;\mathrm{mod}\;37\text{,}\) on a \(a^k\equiv 1^k=1\;\mathrm{mod}\;37\) pour tout entier \(k\geq 1\text{.}\)

6. Comme \(a=260\equiv 0\;\mathrm{mod}\;13\text{,}\) on a \(a^k\equiv 0^k=0\;\mathrm{mod}\;13\) pour tout entier \(k\geq 1\text{.}\)

7. Comme \(a=-23\equiv 2\;\mathrm{mod}\;5\text{,}\) on a la même liste de restes que pour \(a=2\) à la première question ci-dessus.

Il s'agit de trouver un entier \(x\) égal environ à \(667\) et tel que

Comme les entiers \(5, 6\) et \(11\) sont premiers entre eux deux à deux, on peut appliquer le théorème des restes chinois :

Les solutions sont donc caractérisées par

La solution qui se rapproche le plus de \(667\) est donc

Réponse : Il restait six cent cinquante-deux soldats dans l'armée du général.

Il s'agit de trouver un entier \(x\) égal environ à \(700\) et tel que

Comme les entiers \(5, 7, 11\) sont premiers entre eux deux à deux, on peut appliquer le théorème des restes chinois :

Les solutions sont donc caractérisées par

La solution qui se rapproche le plus de \(700\) est donc

Réponse : Victor a six cent soixante-quinze billes exactement.

1. Comme les entiers \(4\) et \(9\) sont premiers entre eux, on peut appliquer le théorème des restes chinois :

   \begin{equation*} \begin{array}{|c|c|c|c|c|c|} \hline a_i&m_i&M_i&\text{Euclide étendu}&u_i&a_iM_iu_i\\ \hline 3&4&9&1=9\cdot 1+4\cdot(-2)&1&27\\ \hline 7&9&4&1=4\cdot(-2)+9\cdot 1&-2&-56\\ \hline M=&36&&&x_0=&-29\\ \hline \end{array} \end{equation*}

   Les solutions sont donc caractérisées par

   \begin{equation*} x\equiv -29\;\mathrm{mod}\;36 \end{equation*}

   ou encore, si on préfère,

   \begin{equation*} x\equiv 7\;\mathrm{mod}\;36. \end{equation*}

2. Comme les entiers \(2, 5\) et \(7\) sont premiers entre eux, on peut appliquer le théorème des restes chinois :

   \begin{equation*} \begin{array}{|c|c|c|c|c|c|} \hline a_i&m_i&M_i&\text{Euclide étendu}&u_i&a_iM_iu_i\\ \hline 1&2&35&1=35\cdot 1+2\cdot(-17)&1&35\\ \hline 2&5&14&1=14\cdot(-1)+5\cdot 3&-1&-28\\ \hline 6&7&10&1=10\cdot(-2)+7\cdot 3&-2&-120\\ \hline M=&70&&&x_0=&-113\\ \hline \end{array} \end{equation*}

   Les solutions sont donc caractérisées par

   \begin{equation*} x\equiv -113\;\mathrm{mod}\;70 \end{equation*}

   ou encore, si on préfère,

   \begin{equation*} x\equiv 27\;\mathrm{mod}\;70. \end{equation*}

3. Comme les entiers \(2\) et \(8\) ne sont pas premiers entre eux, on ne peut pas appliquer le théorème des restes chinois.

1. On a \(a=a+m\cdot 0\text{,}\) donc \(a\equiv a\:\mathrm{mod}\;m\text{.}\)

2. Supposons que \(a\equiv b\;\mathrm{mod}\;m\text{,}\) de sorte qu'il existe un entier relatif \(k\) tel que

   \begin{equation*} a=b+mk. \end{equation*}

   Alors on a

   \begin{equation*} b=a-mk=a+m(-k)=a+mk' \end{equation*}

   en posant \(k':=-k\in\mathbb{Z}\text{.}\)

   Donc \(b\equiv a\;\mathrm{mod}\;m\text{.}\)

   La réciproque s'obtient par symétrie en échangeant les lettres \(a\) et \(b\text{.}\)

3. Supposons que \(a\equiv b\;\mathrm{mod}\;m\) et \(b\equiv c\;\mathrm{mod}\;m\text{,}\) de sorte qu'il existe deux entiers relatifs \(k_1,k_2\) tels que

   \begin{equation*} a=b+mk_1\quad\text{et}\quad b=c+mk_2. \end{equation*}

   Alors on a

   \begin{equation*} a=b+mk_1=(c+mk_2)+mk_1=c+m(\underbrace{k_2+k_1}_{=k_3\in\mathbb{Z}}). \end{equation*}

   Donc \(a\equiv c\;\mathrm{mod}\;m\text{.}\)

4. Supposons que \(a\equiv b\;\mathrm{mod}\;m\) et \(c\equiv d\;\mathrm{mod}\;m\text{,}\) de sorte qu'il existe deux entiers relatifs \(k_1,k_2\) tels que

   \begin{equation*} a=b+mk_1\quad\text{et}\quad c=d+mk_2. \end{equation*}

   Alors on a

   \begin{equation*} a+c=(b+mk_1)+(d+mk_2)=b+d+m(\underbrace{k_1+k_2}_{=k_3\in\mathbb{Z}}). \end{equation*}

   Donc \(a+c\equiv b+d\;\mathrm{mod}\;m\text{.}\)

   Le cas de la soustraction se démontre de manière semblable.

5. Supposons que \(a\equiv b\;\mathrm{mod}\;m\) et \(c\equiv d\;\mathrm{mod}\;m\text{,}\) de sorte qu'il existe deux entiers relatifs \(k_1,k_2\) tels que

   \begin{equation*} a=b+mk_1\quad\text{et}\quad c=d+mk_2. \end{equation*}

   Alors on a

   \begin{align*} ac&=(b+mk_1)\cdot(d+mk_2)\\ &=bd+bmk_2+mk_1d+mk_1mk_2\\ &=bd+m(\underbrace{bk_2+k_1d+k_1mk_2}_{=k_3\in\mathbb{Z}}). \end{align*}

   Donc \(ac\equiv bd\;\mathrm{mod}\;m\text{.}\)

6. Pour \(k=2\text{,}\) cette propriété découle de la précédente dans le cas particulier où \(b=a\text{.}\)

   Établissons le cas général \(k\geq 2\) par récurrence. Le passage de \(k-1\) à \(k\) s'obtient à nouveau grâce à la propriété précédente. En effet, on a

   \begin{equation*} a\equiv b\;\mathrm{mod}\;m\text{ et }a^{k-1}\equiv b^{k-1}\;\mathrm{mod}\;m\quad\Rightarrow\quad \underbrace{a\cdot a^{k-1}}_{a^k}\equiv\underbrace{b\cdot b^{k-1}}_{b^k}\;\mathrm{mod}\;m. \end{equation*}