Congruence

joq35
joq35
dans Arithmétique
Bonsoir
Je dois montrer que 56^6 modulo 100= 56

Pouvez-vous me mettre sur une piste svp, j’ai du mal à voir comment faire la démonstration ?
Merci.

Réponses

  • Dom
    Dom
    On doit trouver des théorèmes dans le cours.

    Je ne sais pas si c'est vrai ton truc, mais on peut essayer de voir...avec ces théorèmes.

    Stabilité par addition, et par multiplication....
  • joq35
    joq35
    Bonjour
    Merci pour votre réponse. J’ai beau chercher à essayer d’appliquer ces théorèmes, je n’y arrive pas.
    Vous n’auriez pas une piste plus concrète pour cet exemple ?
    Merci.
  • Tonm
    Tonm
    Bonjour, $56^6-56=56(56^5-1)$ puis tu suis?
  • Goleon
    Goleon
    Salut,

    $$
    56^2 = (50+6)^2 = \dots =36 \pmod{100}
    $$

    Et on recommence $36 ^2 = - 4 \pmod{100}$ et ensuite $-4 \times 36 = -134 = 56 \pmod{100}$.
  • Chaurien
    Chaurien
    ...J'ai beau chercher...
  • GaBuZoMeu
    GaBuZoMeu
    -4 \times 36 = -134 = 56 \pmod{100}
    Cherchez l'erreur ... ;-)
  • Fin de partie
    Fin de partie
    $56^6=(56^2)^2\times 56^2$ (3 multiplications) ou bien $56^6=(56^3)^2$ (3 multiplications) et on peut faire les calculs à la main. Après il suffit de lire les deux derniers chiffres du résultat obtenu. B-)

    PS:
    Si ce type d'exercice sert à montrer la puissance du concept de congruence, c'est un peu de la daube.

    Si c'est pour rappeler qu'on trouve le reste modulo $100$ d'un nombre en lisant les deux derniers chiffres de l'écriture décimale d'un nombre supérieur à $100$ alors cet exercice tombe pile à propos.
  • joq35
    joq35
    >Chaurien : Tu sais l’évidence n’est pas la même pour chacun. J’ai passé plus d’une heure 30 sur ce truc avant de demander de l’aide. Effectivement, comment souvent avec les maths, je suis un peu bête en voyant finalement comment faire grâce à votre aide. Merci à vous. Mais j’essaye toujours de chercher avant de demander de l’aide.
  • Goleon
    Goleon
    Merci, Gbzm :
    $$
    4 \times 36 = 4 \times 30 + 4 \times 6 = 120 + 24 = 144
    $$
  • Fin de partie
    Fin de partie
    Joq35:

    Tu ne sais pas faire des multiplications, suivie d'une division euclidienne par $100$?

    Joq35:
    Chaurien te faisait remarquer seulement que tu avais commis une belle faute d'orthographe.
  • joq35
    joq35
    Autant pour moi Chaurien ;-)
    Bon dimanche à tous
  • Fin de partie
    Fin de partie
    Si on connait la formule du binôme de Newton et si on a a remarqué que pour $k\geq 2$ , $50^k$ est divisible par $100$
    et que $50$ fois un nombre pair aussi alors:
    $56^6=(50+6)^6=\sum_{k=0}^6 \binom{6}{k}50^k 6^{6-k}=6^6+\underbrace{50\times 6^6+\sum_{k=2}^{6} \binom{6}{k} 50^k6^{6-k}}_{\text{est divisible par 100}}$

    Le reste cherché est donc le reste de la division euclidienne de $6^6$ par $100$

    Par l'usage des tables de multiplication on a:
    $6^6=72\times 72\times 10-72\times 72$

    Ce n'est pas la mer à boire de poser une multiplication et une soustraction.


    @Joq35:

    autant pour moi au temps pour moi
  • Dom
    Dom
    Bon.
    Modulo 100 revient à (re)garder les deux derniers chiffres dans l’écriture décimales.
    Un peu d’huile de coude (j’entends poser les multiplications à la main en s’arrêtant dès qu’on a nos deux chiffres).

    J’utilise implicitement les théorèmes dont je parlais.

    56 = 56 (mod 100)
    56x56 = 36 (mod 100)
    56x56x56 = 36x56 = 16 (mod 100)
    56x56x56x56x56x56 = 16x16 = 56 (mod 100)
  • nicolas.patrois
    nicolas.patrois 
    >>> 56**6
30840979456

    Ben quoi ? :-D
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Dom
    Dom
    Oui. D’ailleurs, choisir 6 n’est pas très pertinent.
    C’est faisable.

    Prendre 6000, par exemple, est peut-être plus instructif.
  • AP
    AP
    Bonsoir
    variante
    vu que 4 divise 56, la congruence demandée est en fait vraie modulo 4 et il suffit de la montrer modulo 25, car 25 et 4 sont premiers entre eux
    Donc l'exercice revient à montrer que $56^6$ c'est $56$ modulo 25, et comme 25 est premier avec 56 , cela revient à montrer que $56^5$ c'est $1$ modulo $25$
    Et modulo $25$
    $56$ c'est $6$
    $56^2$ c'est $36$ soit $11$
    $56^4$ c'est $121$ soit $-4$
    $56^5$ c'est $-24$ soit $1$
  • nicolas.patrois
    nicolas.patrois
    Dom a écrit:
    Oui. D’ailleurs, choisir 6 n’est pas très pertinent.
    C’est faisable.

    Prendre 6000, par exemple, est peut-être plus instructif.
    >>> pow(56,6000,100)
76
    Et c’est instantané.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Dom
    Dom
    Haha.
  • Fin de partie
    Fin de partie
    Je propose cet exercice pour illustrer la puissance de la notion de congruence.

    Soit $N=10^{10000000000000000000000000}$.

    Calculer le reste du nombre $313^N$ dans la division euclidienne par $39$.

    Ou si vous pensez que c'est trop simple:

    Calculer le reste du nombre $350^{N+1}$ dans la division euclidienne par $39$.
  • nicolas.patrois
    nicolas.patrois
    Et dans le même genre :
    https://projecteuler.net/problem=188
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • depasse
    depasse
    Modulo $39$, $313$ c'est $1$ et donc, quel que soit $N$, le reste de la division de $313^N$ par $39$ est $1$.
    Modulo $39$, $350$ c'est $-1$ et donc, quel que soit $N$ pair, le reste de la division de $350^{N+1}$ par $39$ est $-1$.

    Plus difficile: sachant que cinquante de mes amis ont des retraites deux à deux différentes, comment démontrer qu'il n'y a que $42$ régimes de retraite différents à moins de supposer qu'un individu qui ne produit plus rien mérite plus qu'un autre individu qui ne produit plus rien non plus?
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 17

Ben314159JLapinraoul.S +14 Invités