Division euclidienne de $180^{59}$ par $391$ — Les-mathematiques.net The most powerful custom community solution in the world

Division euclidienne de $180^{59}$ par $391$

lpibedorolpibedoro
dans Arithmétique
Bonjour à tous, j'ai réussi à résoudre cet exercice de manière laborieuse en réduisant successivement le problème avec une décomposition de 59 en puissance de 2.

Par ailleurs, cet exercice me fait penser au théorème des restes chinois, notamment car on pourrait décomposer 391 en $17\times 21$ ; est-ce légitime d'y songer ? j'ai essayé de l'appliquer mais en vain... Soit je l'ai mal appliqué soit il n'a pas vraiment de sens ici.

Merci d'avance pour vos réponses

Réponses

  • FélixFélix
    Bonjour,

    391 = 17 * 21 ?
    Petite faute de frappe : 17 * 23.

    Cordialement.
  • MrJMrJ
    Tu calcules le résultat modulo 17 et modulo 23 (avec le petit théorème de Fermat ça va vite), puis tu en déduire le résultat modulo 391.
  • lpibedorolpibedoro
    Au temps pour moi...
  • lpibedorolpibedoro
    "Le résultat"? C'est à dire 180^59 modulo 17 puis 180^59 modulo 23?

    Donc d'après le petit théorème de Fermat :

    (180^59)^16 est congru à 1 modulo 17 et (180^59)^22 est congru à 1 modulo 23

    Mais je ne vois pas ensuite comment passer à 391
  • noix de totosnoix de totos
    lpibedoro a écrit:
    Mais je ne vois pas ensuite comment passer à 391

    Utilise la version explicite suivante du théorème Chinois :

    Th. Soient $a,b \in \mathbb{N^*}$ tels que $\textrm{pgcd}(a,b) = 1$ et $x_1,x_2 \in \mathbb{Z}$. Alors, le système
    $$\begin{cases} x \equiv x_1 \pmod a \\ x \equiv x_2 \pmod b \end{cases}$$
    a une unique solution modulo $ab$ donnée par
    $$x \equiv au x_2 + bv x_1 \pmod{ab}$$
    où $u,v \in \mathbb{Z}$ sont tels que     $au+bv=1$.
  • lpibedorolpibedoro
    On pose a=17 et b=23, on a bien pgcd(17,23)=1

    De plus, on a : 17*(-4) + 23 * 3 = 1 donc on peut poser u = -4 et v = 3

    Mais je ne vois pas comment trouver x1 et x2
  • noix de totosnoix de totos
    Ben, tu les as trouvé dans ton message précédent !
  • lpibedorolpibedoro
    donc (x1 , x2) = (1,1) ? (c'est ce que j'avais écrit)

    et donc le calcul final revient au calcul de Bezout et donnera donc 1..?
  • aléaaléa
    Si $x_1=x_2$, les chinois peuvent rester chez eux...
  • Chat-mathsChat-maths
    Je crois qu'en ce moment, chinois ou pas, on peut tous rester chez nous :-D.
  • lpibedorolpibedoro
    absolument d'accord donc comme je le disais je ne les ai pas trouvés précédemment
  • lpibedorolpibedoro
    je pense que mes erreurs de compréhension sont ici : "Tu calcules le résultat modulo 17 et modulo 23 (avec le petit théorème de Fermat ça va vite)"

    je ne vois pas comment le faire "rapidement"

    et: "Ben, tu les as trouvé dans ton message précédent !"

    je ne vois pas à quel moment je les ai trouvés dans mon message précédent
  • noix de totosnoix de totos
    Bon, je n'ai pas énormément de temps, mais je reprends tout : On a $391 = 17 \times 23$, puis

    $$180^{59} \equiv 10^{59} \equiv 10^{3 \times 16 + 11} \equiv 10^{11} \equiv 3 \pmod{17}$$
    et, de même
    $$180^{59} \equiv 19^{59} \equiv 19^{2 \times 22 + 15} \equiv 19^{15} \equiv 20 \pmod{23}.$$
    Ainsi, le théorème que j'ai rappelé plus haut, tuilisé avec $a=17$, $b=23$, $u=-4$, $v=3$, $x_1 = 3$ et $x_2 = 20$, fournit
    $$180^{59} \equiv 17 \times (-4) \times 20 + 23 \times 3 \times 3 \equiv - 1553 \equiv 20 \pmod{391}.$$
  • lpibedorolpibedoro
    Merci pour ta réponse, le "rapidement" m'a un peu perturbé quand je me suis retrouvé à 10^11 modulo 17 et 19^15 modulo 23, je pensais que j'étais passé à côté de quelque chose de plus rapide, enfin bon
  • noix de totosnoix de totos
    On peut toujours réduire : par exemple
    $$19^{15} = 19^6 \times (19^3)^3 \equiv 2 \times 5^3 \equiv 250 \equiv 20 \pmod{23}.$$
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!