# Exercices - Théorie des Nombres ## Partie 1 1. **Exercice 1 : Division Euclidienne** Effectuez la division euclidienne de $A = 1234$ par $B = 56$. Identifiez le quotient $q$ et le reste $r$. 2. **Exercice 2 : Nombres Premiers et Diviseurs** Le nombre $N = 143$ est-il premier ? Si non, donnez sa décomposition en facteurs premiers et la liste de tous ses diviseurs positifs. ## Partie 2 3. **Exercice 3 : PGCD et PPCM** Calculez le Plus Grand Commun Diviseur ($PGCD$) et le Plus Petit Commun Multiple ($PPCM$) des nombres $a = 180$ et $b = 252$. 4. **Exercice 4 : Calculs Modulaires** Déterminez le reste de la division euclidienne de $7^{2023}$ par $5$. 5. **Exercice 5 : Propriétés des Congruences** Soit $n$ un entier. Montrez que $n^2 + n$ est toujours un nombre pair. Utilisez le concept de congruence. 6. **Exercice 6 : Résolution de Congruence Linéaire Simple** Résolvez l'équation de congruence suivante pour $x \in \mathbb{Z}$: $5x \equiv 3 \pmod{11}$. ## Partie 3 7. **Exercice 7 : Algorithme d'Euclide Étendu et Identité de Bézout** Utilisez l'algorithme d'Euclide étendu pour trouver le $PGCD(247, 71)$ et des entiers $u, v$ tels que $247u + 71v = PGCD(247, 71)$. 8. **Exercice 8 : Propriété des Nombres Premiers** Soit $p$ un nombre premier tel que $p > 3$. Montrez que $p^2 \equiv 1 \pmod{24}$. 9. **Exercice 9 : Problème de Calendrier Modulaire** Un événement se produit tous les 7 jours et un autre événement tous les 11 jours. Si les deux événements ont eu lieu ensemble un mardi (jour 2, en considérant Lundi=1, Mardi=2, ..., Dimanche=7), quel sera le prochain jour de la semaine où ils se produiront à nouveau ensemble ? 10. **Exercice 10 : Chiffrement Simple et Théorie des Jeux (Allusion)** Dans un système de communication simplifié, un message est représenté par un entier $M$. Pour le chiffrer, on calcule $C \equiv M^3 \pmod{13}$. a) Si le message $M=2$, quel est le message chiffré $C$? b) Un joueur, Alice, veut envoyer un message secret $M$ (un entier entre 1 et 12) à Bob. Elle sait que si $M \equiv 0 \pmod 2$, elle perd un point dans un jeu annexe, et si $M \equiv 1 \pmod 2$, elle gagne un point. Si elle reçoit $C=8$, et qu'elle sait qu'elle a envoyé le plus petit message $M$ possible qui produirait ce chiffré, quel est le message $M$ qu'elle a envoyé ? Quel est l'impact sur son score au jeu annexe ? (Indice : La recherche de $M$ peut se faire par tâtonnement ou en utilisant des propriétés des congruences.) # Corrigés Détaillés ### Corrigé de l'Exercice 1 : Division Euclidienne > [!definition] Division Euclidienne > Pour deux entiers $A$ (le dividende) et $B$ (le diviseur) avec $B > 0$, il existe un unique couple d'entiers $(q, r)$ (quotient et reste) tels que $A = Bq + r$ et $0 \le r < B$. Nous devons effectuer la division euclidienne de $A = 1234$ par $B = 56$. 1. **Étape 1 : Estimer le quotient** On cherche combien de fois $56$ "rentre" dans $1234$. $ \frac{1234}{56} \approx 22.035 $ Le quotient $q$ est donc la partie entière de ce résultat, soit $q = 22$. 2. **Étape 2 : Calculer le reste** En utilisant la formule $r = A - Bq$: $ r = 1234 - (56 \times 22) $ $ r = 1234 - 1232 $ $ r = 2 $ 3. **Étape 3 : Vérifier la condition du reste** Le reste $r = 2$ doit satisfaire $0 \le r < B$. Ici, $0 \le 2 < 56$, ce qui est bien le cas. > [!example] Solution > La division euclidienne de $1234$ par $56$ donne un quotient $q = 22$ et un reste $r = 2$. > On peut écrire : $1234 = 56 \times 22 + 2$. ### Corrigé de l'Exercice 2 : Nombres Premiers et Diviseurs > [!definition] Nombre Premier > Un nombre entier naturel $p > 1$ est dit premier s'il n'admet que deux diviseurs positifs distincts : $1$ et lui-même. Nous devons déterminer si $N = 143$ est premier. 1. **Étape 1 : Tester la divisibilité par les petits nombres premiers** Pour vérifier si un nombre $N$ est premier, il suffit de tester sa divisibilité par les nombres premiers $p$ tels que $p^2 \le N$. Ici, $N = 143$. On calcule $\sqrt{143} \approx 11.96$. Nous devons donc tester les nombres premiers inférieurs ou égaux à $11$: $2, 3, 5, 7, 11$. * **Divisibilité par 2 :** $143$ n'est pas pair, donc non divisible par $2$. * **Divisibilité par 3 :** La somme des chiffres de $143$ est $1+4+3=8$, qui n'est pas un multiple de $3$. Donc $143$ n'est pas divisible par $3$. * **Divisibilité par 5 :** $143$ ne se termine ni par $0$ ni par $5$. Donc $143$ n'est pas divisible par $5$. * **Divisibilité par 7 :** $143 = 7 \times 20 + 3$. Le reste est $3$, donc $143$ n'est pas divisible par $7$. * **Divisibilité par 11 :** $143 = 11 \times 13$. Le reste est $0$. 2. **Étape 2 : Conclure sur la primalité** Puisque $143$ est divisible par $11$ (et par $13$), il n'est **pas premier**. 3. **Étape 3 : Décomposition en facteurs premiers** Nous avons trouvé $143 = 11 \times 13$. $11$ et $13$ sont tous deux des nombres premiers. C'est donc la décomposition en facteurs premiers. 4. **Étape 4 : Lister tous les diviseurs** Les diviseurs d'un nombre dont la décomposition est $p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$ sont de la forme $p_1^{b_1} \times p_2^{b_2} \times \dots \times p_k^{b_k}$ avec $0 \le b_i \le a_i$. Pour $143 = 11^1 \times 13^1$, les diviseurs sont : * $11^0 \times 13^0 = 1 \times 1 = 1$ * $11^1 \times 13^0 = 11 \times 1 = 11$ * $11^0 \times 13^1 = 1 \times 13 = 13$ * $11^1 \times 13^1 = 11 \times 13 = 143$ > [!example] Solution > Le nombre $N = 143$ n'est **pas premier**. > Sa décomposition en facteurs premiers est $143 = 11 \times 13$. > La liste de ses diviseurs positifs est $\{1, 11, 13, 143\}$. ### Corrigé de l'Exercice 3 : PGCD et PPCM > [!definition] PGCD et PPCM > Le Plus Grand Commun Diviseur ($PGCD$) de deux entiers $a$ et $b$ est le plus grand entier qui divise à la fois $a$ et $b$. > Le Plus Petit Commun Multiple ($PPCM$) de deux entiers $a$ et $b$ est le plus petit entier positif qui est un multiple de $a$ et de $b$. > > > [!theorem] Relation entre PGCD et PPCM > > Pour tous entiers positifs $a$ et $b$, on a la relation : $PGCD(a, b) \times PPCM(a, b) = |a \times b|$. Nous devons calculer le $PGCD(180, 252)$ et le $PPCM(180, 252)$. 1. **Étape 1 : Décomposition en facteurs premiers** Décomposons $180$ et $252$ en facteurs premiers. * Pour $180$: $ 180 = 18 \times 10 = (2 \times 9) \times (2 \times 5) = (2 \times 3^2) \times (2 \times 5) = 2^2 \times 3^2 \times 5^1 $ * Pour $252$: $ 252 = 2 \times 126 = 2^2 \times 63 = 2^2 \times 9 \times 7 = 2^2 \times 3^2 \times 7^1 $ 2. **Étape 2 : Calcul du PGCD** Le $PGCD$ est le produit des facteurs premiers communs, chacun élevé à la plus petite puissance. Facteurs communs : $2$ et $3$. Plus petite puissance de $2$ : $2^2$. Plus petite puissance de $3$ : $3^2$. $ PGCD(180, 252) = 2^2 \times 3^2 = 4 \times 9 = 36 $ 3. **Étape 3 : Calcul du PPCM** Le $PPCM$ est le produit de tous les facteurs premiers (communs ou non), chacun élevé à la plus grande puissance. Facteurs : $2, 3, 5, 7$. Plus grande puissance de $2$ : $2^2$. Plus grande puissance de $3$ : $3^2$. Plus grande puissance de $5$ : $5^1$. Plus grande puissance de $7$ : $7^1$. $ PPCM(180, 252) = 2^2 \times 3^2 \times 5^1 \times 7^1 = 4 \times 9 \times 5 \times 7 = 36 \times 35 = 1260 $ 4. **Étape 4 : Vérification (facultative)** On peut vérifier avec la relation $PGCD(a, b) \times PPCM(a, b) = a \times b$. $ 36 \times 1260 = 45360 $ $ 180 \times 252 = 45360 $ La vérification est concluante. > [!example] Solution > Le $PGCD(180, 252) = 36$. > Le $PPCM(180, 252) = 1260$. ### Corrigé de l'Exercice 4 : Calculs Modulaires > [!definition] Congruence > Soient $a, b \in \mathbb{Z}$ et $m \in \mathbb{N}^*$. On dit que $a$ est congru à $b$ modulo $m$, noté $a \equiv b \pmod m$, si $m$ divise $(a-b)$. Cela signifie que $a$ et $b$ ont le même reste dans la division euclidienne par $m$. Nous devons déterminer le reste de la division euclidienne de $7^{2023}$ par $5$. Cela revient à calculer $7^{2023} \pmod 5$. 1. **Étape 1 : Réduire la base modulo $5$** Commençons par réduire la base $7$ modulo $5$: $ 7 \equiv 2 \pmod 5 $ Donc, $7^{2023} \equiv 2^{2023} \pmod 5$. 2. **Étape 2 : Chercher un cycle des puissances de $2$ modulo $5$** Calculons les premières puissances de $2$ modulo $5$: * $2^1 \equiv 2 \pmod 5$ * $2^2 \equiv 4 \pmod 5$ * $2^3 \equiv 2^2 \times 2 \equiv 4 \times 2 \equiv 8 \equiv 3 \pmod 5$ * $2^4 \equiv 2^3 \times 2 \equiv 3 \times 2 \equiv 6 \equiv 1 \pmod 5$ Nous avons trouvé que $2^4 \equiv 1 \pmod 5$. Le cycle a une longueur de $4$. 3. **Étape 3 : Utiliser le cycle pour réduire l'exposant** Maintenant, nous devons réduire l'exposant $2023$ modulo la longueur du cycle, c'est-à-dire modulo $4$. Effectuons la division euclidienne de $2023$ par $4$: $ 2023 = 4 \times 505 + 3 $ Donc, $2023 \equiv 3 \pmod 4$. 4. **Étape 4 : Calculer le résultat final** Nous pouvons alors écrire : $ 2^{2023} \equiv 2^{4 \times 505 + 3} \pmod 5 $ $ 2^{2023} \equiv (2^4)^{505} \times 2^3 \pmod 5 $ Puisque $2^4 \equiv 1 \pmod 5$: $ 2^{2023} \equiv 1^{505} \times 2^3 \pmod 5 $ $ 2^{2023} \equiv 1 \times 8 \pmod 5 $ $ 2^{2023} \equiv 8 \pmod 5 $ Enfin, $8 \equiv 3 \pmod 5$. > [!example] Solution > Le reste de la division euclidienne de $7^{2023}$ par $5$ est $3$. ### Corrigé de l'Exercice 5 : Propriétés des Congruences Nous devons montrer que $n^2 + n$ est toujours un nombre pair pour tout entier $n$. Cela revient à montrer que $n^2 + n \equiv 0 \pmod 2$. > [!note] Rappel sur la parité > Un nombre est pair s'il est congru à $0 \pmod 2$. > Un nombre est impair s'il est congru à $1 \pmod 2$. Nous allons considérer deux cas pour $n$: 1. **Cas 1 : $n$ est pair** Si $n$ est pair, alors $n \equiv 0 \pmod 2$. Dans ce cas, $n^2 \equiv 0^2 \equiv 0 \pmod 2$. Donc, $n^2 + n \equiv 0 + 0 \equiv 0 \pmod 2$. Ainsi, si $n$ est pair, $n^2 + n$ est pair. 2. **Cas 2 : $n$ est impair** Si $n$ est impair, alors $n \equiv 1 \pmod 2$. Dans ce cas, $n^2 \equiv 1^2 \equiv 1 \pmod 2$. Donc, $n^2 + n \equiv 1 + 1 \equiv 2 \pmod 2$. Puisque $2 \equiv 0 \pmod 2$: $n^2 + n \equiv 0 \pmod 2$. Ainsi, si $n$ est impair, $n^2 + n$ est pair. Dans les deux cas (que $n$ soit pair ou impair), $n^2 + n$ est congru à $0$ modulo $2$. > [!example] Solution > Puisque $n^2 + n = n(n+1)$, on peut aussi remarquer que $n$ et $n+1$ sont deux entiers consécutifs. L'un des deux est nécessairement pair. Le produit d'un entier pair par n'importe quel autre entier est toujours pair. > > En utilisant les congruences, nous avons démontré que pour tout entier $n$, $n^2 + n \equiv 0 \pmod 2$. Par conséquent, $n^2 + n$ est toujours un nombre pair. ### Corrigé de l'Exercice 6 : Résolution de Congruence Linéaire Simple Nous devons résoudre l'équation de congruence $5x \equiv 3 \pmod{11}$. > [!definition] Inverse Modulaire > Un entier $a'$ est un inverse modulaire de $a$ modulo $m$ si $aa' \equiv 1 \pmod m$. Un inverse modulaire existe si et seulement si $PGCD(a, m) = 1$. 1. **Étape 1 : Vérifier l'existence d'un inverse modulaire** Pour résoudre $ax \equiv b \pmod m$, nous devons trouver l'inverse modulaire de $a$ modulo $m$. Ici, $a=5$ et $m=11$. Calculons $PGCD(5, 11)$. Puisque $5$ et $11$ sont des nombres premiers et distincts, $PGCD(5, 11) = 1$. Un inverse modulaire de $5$ modulo $11$ existe donc. 2. **Étape 2 : Trouver l'inverse modulaire de $5$ modulo $11$** Nous cherchons un entier $k$ tel que $5k \equiv 1 \pmod{11}$. On peut tester les multiples de $5$ modulo $11$: * $5 \times 1 = 5 \equiv 5 \pmod{11}$ * $5 \times 2 = 10 \equiv 10 \pmod{11}$ * $5 \times 3 = 15 \equiv 4 \pmod{11}$ * $5 \times 4 = 20 \equiv 9 \pmod{11}$ * $5 \times 5 = 25 \equiv 3 \pmod{11}$ * $5 \times 6 = 30 \equiv 8 \pmod{11}$ * $5 \times 7 = 35 \equiv 2 \pmod{11}$ * $5 \times 8 = 40 \equiv 7 \pmod{11}$ * $5 \times 9 = 45 \equiv 1 \pmod{11}$ L'inverse modulaire de $5$ modulo $11$ est $9$. Donc $5^{-1} \equiv 9 \pmod{11}$. 3. **Étape 3 : Multiplier l'équation par l'inverse modulaire** Multiplions les deux côtés de la congruence $5x \equiv 3 \pmod{11}$ par $9$: $ 9 \times (5x) \equiv 9 \times 3 \pmod{11} $ $ (9 \times 5)x \equiv 27 \pmod{11} $ $ 45x \equiv 27 \pmod{11} $ 4. **Étape 4 : Réduire les résultats modulo $11$** Puisque $45 \equiv 1 \pmod{11}$ (car $45 = 4 \times 11 + 1$) et $27 \equiv 5 \pmod{11}$ (car $27 = 2 \times 11 + 5$): $ 1x \equiv 5 \pmod{11} $ $ x \equiv 5 \pmod{11} $ > [!example] Solution > La solution de la congruence $5x \equiv 3 \pmod{11}$ est $x \equiv 5 \pmod{11}$. > Cela signifie que les solutions sont tous les entiers de la forme $x = 11k + 5$ pour $k \in \mathbb{Z}$. > > > [!tip] Vérification > > Pour $x=5$, $5 \times 5 = 25$. $25 \pmod{11} = 3$. La solution est correcte. ### Corrigé de l'Exercice 7 : Algorithme d'Euclide Étendu et Identité de Bézout > [!theorem] Identité de Bézout > Pour deux entiers $a$ et $b$ non nuls, il existe des entiers relatifs $u$ et $v$ tels que $au + bv = PGCD(a, b)$. Nous devons trouver le $PGCD(247, 71)$ et des entiers $u, v$ tels que $247u + 71v = PGCD(247, 71)$. 1. **Étape 1 : Appliquer l'algorithme d'Euclide pour trouver le PGCD** * $247 = 3 \times 71 + 34$ * $71 = 2 \times 34 + 3$ * $34 = 11 \times 3 + 1$ * $3 = 3 \times 1 + 0$ Le dernier reste non nul est $1$. Donc $PGCD(247, 71) = 1$. 2. **Étape 2 : Remonter l'algorithme d'Euclide pour trouver $u$ et $v$** Nous exprimons le reste de chaque étape en fonction des nombres précédents, en partant de l'avant-dernière ligne : * De $34 = 11 \times 3 + 1$, on isole le $PGCD(1)$: $ 1 = 34 - 11 \times 3 \quad (\text{Équation 1}) $ * De $71 = 2 \times 34 + 3$, on isole $3$: $ 3 = 71 - 2 \times 34 \quad (\text{Équation 2}) $ * Substituons l'Équation 2 dans l'Équation 1: $ 1 = 34 - 11 \times (71 - 2 \times 34) $ $ 1 = 34 - 11 \times 71 + 11 \times 2 \times 34 $ $ 1 = 34 - 11 \times 71 + 22 \times 34 $ Regroupons les termes en $34$: $ 1 = (1 + 22) \times 34 - 11 \times 71 $ $ 1 = 23 \times 34 - 11 \times 71 \quad (\text{Équation 3}) $ * De $247 = 3 \times 71 + 34$, on isole $34$: $ 34 = 247 - 3 \times 71 \quad (\text{Équation 4}) $ * Substituons l'Équation 4 dans l'Équation 3: $ 1 = 23 \times (247 - 3 \times 71) - 11 \times 71 $ $ 1 = 23 \times 247 - 23 \times 3 \times 71 - 11 \times 71 $ $ 1 = 23 \times 247 - 69 \times 71 - 11 \times 71 $ Regroupons les termes en $71$: $ 1 = 23 \times 247 + (-69 - 11) \times 71 $ $ 1 = 23 \times 247 + (-80) \times 71 $ Nous avons donc $u = 23$ et $v = -80$. > [!example] Solution > Le $PGCD(247, 71) = 1$. > Les entiers $u=23$ et $v=-80$ vérifient l'identité de Bézout : > $247 \times 23 + 71 \times (-80) = 5681 - 5680 = 1$. ### Corrigé de l'Exercice 8 : Propriété des Nombres Premiers Nous devons montrer que si $p$ est un nombre premier tel que $p > 3$, alors $p^2 \equiv 1 \pmod{24}$. > [!note] Décomposition modulaire > $p^2 \equiv 1 \pmod{24}$ est équivalent à dire que $p^2 - 1$ est divisible par $24$. > Puisque $24 = 3 \times 8$, et que $PGCD(3, 8) = 1$, il suffit de montrer que $p^2 - 1$ est divisible par $3$ ET par $8$. > On peut aussi écrire $p^2 - 1 = (p-1)(p+1)$. 1. **Divisibilité par 3** Puisque $p$ est un nombre premier et $p > 3$, $p$ n'est pas divisible par $3$. Donc, $p \not\equiv 0 \pmod 3$. Par conséquent, $p$ peut être congru à $1 \pmod 3$ ou $2 \pmod 3$. * Si $p \equiv 1 \pmod 3$: Alors $p^2 \equiv 1^2 \equiv 1 \pmod 3$. Donc $p^2 - 1 \equiv 1 - 1 \equiv 0 \pmod 3$. * Si $p \equiv 2 \pmod 3$: Alors $p^2 \equiv 2^2 \equiv 4 \equiv 1 \pmod 3$. Donc $p^2 - 1 \equiv 1 - 1 \equiv 0 \pmod 3$. Dans tous les cas, $p^2 - 1$ est divisible par $3$. 2. **Divisibilité par 8** Puisque $p$ est un nombre premier et $p > 3$, $p$ est impair. Donc $p-1$ et $p+1$ sont deux nombres pairs consécutifs. On peut écrire $p-1 = 2k$ pour un certain entier $k$. Alors $p+1 = 2k+2$. Le produit $(p-1)(p+1) = (2k)(2k+2) = 4k(k+1)$. Nous savons que le produit de deux entiers consécutifs $k(k+1)$ est toujours pair. Donc $k(k+1) = 2m$ pour un certain entier $m$. Alors $(p-1)(p+1) = 4(2m) = 8m$. Ceci montre que $(p-1)(p+1)$ est divisible par $8$. Donc $p^2 - 1$ est divisible par $8$. 3. **Conclusion** Nous avons montré que $p^2 - 1$ est divisible par $3$ et que $p^2 - 1$ est divisible par $8$. Puisque $PGCD(3, 8) = 1$, si un nombre est divisible par $3$ et par $8$, il est divisible par leur produit, c'est-à-dire par $3 \times 8 = 24$. Donc $p^2 - 1$ est divisible par $24$. Ce qui signifie $p^2 - 1 \equiv 0 \pmod{24}$, ou encore $p^2 \equiv 1 \pmod{24}$. > [!example] Solution > En décomposant le problème en divisibilité par $3$ et par $8$ (facteurs premiers entre eux de $24$), nous avons démontré que pour tout nombre premier $p > 3$, $p^2 \equiv 1 \pmod{24}$. > > > [!tip] Application > > Cette propriété est utile dans de nombreux problèmes d'arithmétique modulaire impliquant des nombres premiers. Par exemple, pour $p=5$, $5^2 = 25 \equiv 1 \pmod{24}$. Pour $p=7$, $7^2 = 49 = 2 \times 24 + 1 \equiv 1 \pmod{24}$. ### Corrigé de l'Exercice 9 : Problème de Calendrier Modulaire Nous avons deux événements : * Événement A : se produit tous les 7 jours. * Événement B : se produit tous les 11 jours. Les deux événements ont eu lieu ensemble un mardi (jour 2, en considérant Lundi=1, Mardi=2, ..., Dimanche=7). Nous voulons trouver le prochain jour de la semaine où ils se produiront à nouveau ensemble. 1. **Étape 1 : Comprendre la périodicité commune** Si les événements se produisent ensemble, cela signifie que le nombre de jours écoulés depuis la dernière occurrence commune est un multiple de $7$ et un multiple de $11$. Le plus petit nombre de jours après lequel ils se reproduiront ensemble est le $PPCM(7, 11)$. Puisque $7$ et $11$ sont des nombres premiers, $PGCD(7, 11) = 1$. Donc $PPCM(7, 11) = 7 \times 11 = 77$ jours. 2. **Étape 2 : Déterminer le jour de la semaine** Nous devons trouver quel jour de la semaine correspond à $77$ jours après un mardi. Les jours de la semaine sont numérotés de $1$ (Lundi) à $7$ (Dimanche). Mardi est le jour $2$. Nous voulons trouver le jour $(2 + 77) \pmod 7$. Attention : si le résultat est $0$, c'est le jour $7$ (Dimanche). Calculons $77 \pmod 7$: $ 77 = 11 \times 7 + 0 $ Donc $77 \equiv 0 \pmod 7$. Le jour de la semaine sera $(2 + 0) \pmod 7 \equiv 2 \pmod 7$. Le jour $2$ correspond à **Mardi**. > [!example] Solution > Les deux événements se produiront à nouveau ensemble après $PPCM(7, 11) = 77$ jours. > Puisque $77$ est un multiple de $7$ ($77 \equiv 0 \pmod 7$), le jour de la semaine ne changera pas. > Si les événements ont eu lieu ensemble un mardi, le prochain jour où ils se produiront à nouveau ensemble sera également un **Mardi**. > > > [!note] Lien avec les pré-requis > > La compréhension des multiples et des diviseurs, ainsi que la capacité à résoudre des congruences simples, sont cruciales ici. Ce type de problème est une application directe des concepts de $PPCM$ et d'arithmétique modulaire. ### Corrigé de l'Exercice 10 : Chiffrement Simple et Théorie des Jeux (Allusion) Le système de chiffrement utilise $C \equiv M^3 \pmod{13}$. $M$ est un entier entre $1$ et $12$. **a) Si le message $M=2$, quel est le message chiffré $C$ ?** 1. **Calcul direct** Nous devons calculer $C \equiv 2^3 \pmod{13}$. $ 2^3 = 8 $ Donc $C \equiv 8 \pmod{13}$. Puisque $C$ doit être le reste, $C=8$. > [!example] Solution a) > Si $M=2$, le message chiffré $C=8$. **b) Un joueur, Alice, veut envoyer un message secret $M$ (un entier entre 1 et 12). Elle sait que si $M \equiv 0 \pmod 2$, elle perd un point dans un jeu annexe, et si $M \equiv 1 \pmod 2$, elle gagne un point. Si elle reçoit $C=8$, et qu'elle sait qu'elle a envoyé le plus petit message $M$ possible qui produirait ce chiffré, quel est le message $M$ qu'elle a envoyé ? Quel est l'impact sur son score au jeu annexe ?** 1. **Décrypter le message $M$** Nous devons résoudre l'équation $M^3 \equiv 8 \pmod{13}$ pour $M \in \{1, 2, \dots, 12\}$. Par tâtonnement, calculons $M^3 \pmod{13}$ pour chaque $M$: * $M=1: 1^3 = 1 \pmod{13}$ * $M=2: 2^3 = 8 \pmod{13}$ * $M=3: 3^3 = 27 \equiv 1 \pmod{13}$ * $M=4: 4^3 = 64 \equiv 12 \pmod{13}$ * $M=5: 5^3 = 125 \equiv 8 \pmod{13}$ * $M=6: 6^3 = 216 \equiv 8 \pmod{13}$ * $M=7: 7^3 = 343 \equiv 5 \pmod{13}$ * $M=8: 8^3 = 512 \equiv 5 \pmod{13}$ * $M=9: 9^3 = 729 \equiv 1 \pmod{13}$ * $M=10: 10^3 = 1000 \equiv 12 \pmod{13}$ * $M=11: 11^3 \equiv (-2)^3 = -8 \equiv 5 \pmod{13}$ * $M=12: 12^3 \equiv (-1)^3 = -1 \equiv 12 \pmod{13}$ Les valeurs de $M$ qui donnent $C=8$ sont $M=2, M=5, M=6$. L'énoncé précise qu'Alice a envoyé le **plus petit message $M$ possible** qui produirait ce chiffré. Parmi $\{2, 5, 6\}$, le plus petit est $M=2$. 2. **Impact sur le score au jeu annexe** Si $M=2$, $M$ est pair ($2 \equiv 0 \pmod 2$). Selon les règles du jeu, si $M$ est pair, Alice perd 1 point. > [!example] Solution b) > Pour décrypter le message, nous cherchons $M \in \{1, \dots, 12\}$ tel que $M^3 \equiv 8 \pmod{13}$. > Par tâtonnement, nous trouvons que $M=2$, $M=5$ et $M=6$ satisfont cette congruence. > Puisque l'énoncé indique qu'Alice a envoyé le plus petit message $M$ possible, le message envoyé est $M=2$. > > Pour le score au jeu annexe : > Le message $M=2$ est un nombre pair ($2 \equiv 0 \pmod 2$). > Selon les règles du jeu, si $M$ est pair, Alice perd 1 point. > > Le message $M$ envoyé est $2$. L'impact sur le score d'Alice est une **perte de 1 point**. > > > [!note] Lien avec la Théorie des Jeux > > Cet exercice illustre comment les propriétés des nombres (parité, congruences) peuvent influencer des stratégies ou des résultats dans un contexte de jeu. Dans des situations réelles de théorie des jeux, une information incomplète (comme l'ambiguïté de $M$ si la condition supplémentaire n'avait pas été donnée) peut rendre la prise de décision plus complexe. Ces concepts sont fondamentaux pour l'étude des systèmes cryptographiques, où l'unicité du décryptage est cruciale. # 🗓️ Historique - Dernière MAJ: `08-Décembre-2025` - Rédigé par: [[Hamilton DE ARAUJO]]