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

[invite1237a629]

Plop,

Bon, voilà, j'ai eu un exercice où on me demande de calculer le reste de la division (donc la congruence) de 63²⁴¹ 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 =')
-----

[invite35452583]

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).

[invited5b2473a]

Donc, il faut que tu trouves le reste de 9*63²⁴⁰ modulo 25

[invite1237a629]

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 ^^

[A voir en vidéo sur Futura]

[invite35452583]

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.

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.

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.

[invite1237a629]

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

Tout s'éclaire admirablement !