Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Théorème chinois & un peu d'arithmétique



  1. #1
    MiMoiMolette

    Théorème chinois & un peu d'arithmétique


    ------

    Plop,

    Bon, voilà, j'ai eu un exercice où on me demande de calculer le reste de la division (donc la congruence) de 63241 par 175.

    175 = 7x25, donc non premier avec 63.

    Et on ne peut donc pas utiliser le théorème d'Euler (ou petit théorème de Fermat, c'est du pareil au même), c'est ça ?

    On m'a dit qu'il fallait utiliser le théorème chinois. Mais je ne vois pas du tout comment Sauriez-vous m'aider ?


    Et j'aurais aimé savoir aussi (des avis divergent...) comment savoir combien il y a de générateurs d'un groupe cyclique de type (Z/nZ)* (de type phi(fonction d'Euler) de n-1 ???), comment les trouver et comment prouver qu'une classe est génératrice du groupe.

    Merci =')

    -----
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  2. Publicité
  3. #2
    homotopie

    Re : Théorème chinois & un peu d'arithmétique

    En effet on peut passer par le théorème chinois.
    63 est congru à 0 modulo 7 donc 63^241 aussi.
    63 est congru à 13 modulo 25, 13 est premier avec 25, or (Z/25Z) est d'ordre 20 donc 63^241 est congru à (63^20)^12 x 63 congru à 1^12 x 13 càd 13.
    Reste à trouver quel multiple de 7 est congru à 13 modulo 25.

    (Z/nZ)* n'est pas cyclique dans le cas général (c'est vrai pour n=2,4, p^k et 2xp^k où p est un premier impair et c'est tout).

  4. #3
    indian58

    Re : Théorème chinois & un peu d'arithmétique

    Donc, il faut que tu trouves le reste de 9*63240 modulo 25

  5. #4
    MiMoiMolette

    Re : Théorème chinois & un peu d'arithmétique

    Citation Envoyé par homotopie Voir le message
    En effet on peut passer par le théorème chinois.
    63 est congru à 0 modulo 7 donc 63^241 aussi.
    63 est congru à 13 modulo 25, 13 est premier avec 25, or (Z/25Z) est d'ordre 20 donc 63^241 est congru à (63^20)^12 x 63 congru à 1^12 x 13 càd 13.
    Reste à trouver quel multiple de 7 est congru à 13 modulo 25.

    (Z/nZ)* n'est pas cyclique dans le cas général (c'est vrai pour n=2,4, p^k et 2xp^k où p est un premier impair et c'est tout).
    Chuis désolée, je crois que je suis larguée

    Pour décomposer en modulo 7 et modulo 25, on se sert du fait qu'il existe une bijection de Z/175Z dans Z/7Z x Z/25Z ? Je pensais que ça ne marchait que si "7" et "25" étaient premiers ?
    De plus, une fois qu'on a la congruence de 63^241 par 25, pourquoi faut-il trouver quel multiple (ou puissance ?) de 7 est congru à 13 modulo 25 ? J'ai du mal avec l'application du théorème chinois...Si vous pouviez m'éclairer... parce que je ne vois même pas où on s'en sert en fait ^^'

    @ indian58 : pourquoi ? :$


    Concernant le groupe cyclique, oui je parlais du cas n premier (que j'aurais dû appeler p, voui), mais à partir de là, les questions demeurent ^^
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  6. A voir en vidéo sur Futura
  7. #5
    homotopie

    Re : Théorème chinois & un peu d'arithmétique

    Citation Envoyé par MiMoiMolette Voir le message
    Pour décomposer en modulo 7 et modulo 25, on se sert du fait qu'il existe une bijection de Z/175Z dans Z/7Z x Z/25Z ? Je pensais que ça ne marchait que si "7" et "25" étaient premiers ?
    Nul besoin qu'ils soient premiers, ce qu'il faut c'est qu'ils soient premiers entre eux. C'est bien le cas ici 7 et 25 sont premiers entre eux.

    Citation Envoyé par MiMoiMolette Voir le message
    De plus, une fois qu'on a la congruence de 63^241 par 25, pourquoi faut-il trouver quel multiple (ou puissance ?) de 7 est congru à 13 modulo 25 ?
    On a vu que 63^241 est congru à 0 modulo 7 et à 13 modulo 25.
    La congruence de 63^241 modulo 7x25=175 est la seule classe modulo 175 congru à 0 modulo 7 et à 13 modulo 25 (c'est là qu'on utilise le théorème chinois). Or un nombre congru à 0 modulo 7 est un multiple de 7.
    Le plus rapide est de regarder quel nombre congru à 13 modulo 25 (il n'y en a que 7) est un multiple de 7.

    Citation Envoyé par MiMoiMolette Voir le message
    Concernant le groupe cyclique, oui je parlais du cas n premier (que j'aurais dû appeler p, voui), mais à partir de là, les questions demeurent ^^
    Ce n'est pas l'appeler "p" qu'il fallait mais écrire que c'est un premier (ce n'est pas parce que je vois la lettre "p" que je suppose que c'est un premier, d'autre part si je sais que le nombre e est un entier premier et bien ça ne me dérange pas qu'il soit noté ainsi).
    (Z/nZ)* dans ce cas est isomorphe en tant que groupe à Z/(n-1)Z. Son nombre de générateurs est le nombre d'entiers compris entre 1 et n-1 premiers avec n-1, càd fonction d'Euler (n-1).
    Quant à déterminer quelle classe x est génératrice, tant qu'on en a aucune, il n'y a guère pour n impair, le calcul de x(n-1)/2 (qui doit être égal à -1) pour le prouver (on peut encore accélérer un peu : si n=19 on prend le cube si c'est distinct de 1 et de -1, les ordres 1,2,3,6 sont éliminés restent 9 et 18 possibles, si finalement 9, -x=(-1).x convient). Pour n=2, la seule classe non nulle 1 est génératrice. Si c'était facile de déterminer quels sont les générateurs de (Z/nZ)*, beaucoup de problèmes d'arithmétique se résolveraient plus facilement ou se résolveraient tout court.

  8. #6
    MiMoiMolette

    Re : Théorème chinois & un peu d'arithmétique

    Alors là...Merci beaucoup pour tes explications !

    Tout s'éclaire admirablement !
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  9. Publicité

Discussions similaires

  1. Théorème des restes chinois
    Par invite43219988 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 21/10/2007, 11h21
  2. Demo d'un théorème d'arithmetique
    Par Deeprod dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 12/09/2007, 13h07
  3. Théorème chinois des restes
    Par Cieletmer dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 05/01/2007, 15h37
  4. [exo] Divisibilité & théoreme de Fermat
    Par n0unours dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 16/01/2006, 19h04
  5. Théorême des restes chinois
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 26/04/2005, 00h01