reste chinois, th de fermat

[invite1ec1f66d]

bonjour
alors voila on me demande de mq:
p¹⁶=1 mod 16320
avec p>17
je sais qu'il faut utiliser le th de fermat pr des nbrs premiers bien choisi et le th des restes chinois mais je ne vois vraiment pas comment. si quelqu'un peut m'aider.. svp
-----

[invite97a92052]

Hello,

A priori il manque une indication sur p (je suppose qu'il est premier)

Une petite indication pour commencer :
16320 = 2 x 2 x 2 x 2 x 2 x 2 x 3 x 5 x 17

et... Phi(17) = 16

[invite1ec1f66d]

oup's oui p est premier sinon çà marcherai pas

on peut utilisé le th de fermat
p⁴= 1 modulo 5
p²= 1 modulo 3
pgcd(3,5)=1
p⁶=1 mod 15 mais apres je ne vois pas comment faire intervenir les autres facteur de 16320 a savoir 17 et 2^6
le pb vient pe etre du faite que je ne sais pas trop appliquer le th des reste chinois

[invite97a92052]

Ce sont de vieux souvenirs pour moi, mais :



De plus,

Si on avait la même chose modulo 64, ce serait fini.

Pour la suite :
On a déjà par Euler

Mais mieux, toujours par Euler, on a aussi que est congru à 1 modulo 32
=> ou

Il te reste un travail à faire pour montrer que ce n'est pas 33 (à priori je dirais que tu n'as besoin que de l'information que p est impair)

NB : il y a peut-être plus simple...

[A voir en vidéo sur Futura]

[invite1ec1f66d]

merci d'avoir répondu mais il y a un point que je ne comprend pas:

pourquoi:

p16=1 mod 32 s'a impliquerai p16=1 mod 64 ou p16=33 mod 32 ??

[invite1ec1f66d]

oup's j'ai mal écrit
donc en faite c'était pourquoi:

p¹⁶=1 mod 32 => p¹⁶=1 mod 64 ou p¹⁶=33 mod 32

[sylvainc2]

Une autre facon:
p^16 = (p^32)^(1/2) mod 64
= (1)^(1/2) mod 64
Donc:
p^16 = 1 mod 64: ok car il y a des solutions pour ca
OU
p^16 = -1 mod 64: il y a peut-être des solutions mais peut-etre pas. Pour chercher des solutions possibles, poser t=p^8 --> t^2=-1 mod 64 et chercher pour t impair de 3 à 31. C'est bourrin mais c'est facile à calculer, et on voit qu'il n'y a pas de solution et c'est bien ce qu'on veut (qu'il n'y en ait pas) car dans ce cas on a bien toutes les congruences:
p^16 = 1 mod 3 et mod 5 et mod 17 et mod 64. et selon le th. des restes chinois ca veut dire que p^16=1 mod 16320

[invite1ec1f66d]

merci SylvainC2 pour ta méthode
pourrais tu m'expliquer pourquoi
p¹⁶=1^1/2 mod 64

p¹⁶ =1 mod 64
ou
p¹⁶=-1 mod 64 je ne vois pas d'ou viens le -1??

[sylvainc2]

Quand on écrit x = 1^(1/2) c'est que x est la racine carrée de 1. Il y a en toujours deux: x=1 car 1^2=1 mais aussi x=-1 car (-1)^2=1. C'est la même chose ici sauf que c'est modulo 64.

[invite1ec1f66d]

oui c'est exacte.. merci
j'ai appliquer ta méthode et tout va bien sauf que je ne vois pas pourquoi il faut tester pour t allant de 3 a 31 ? moi j'aurais dit de 17 a 61 et j'aurais pris que les nombres premiers vu que p est un nombre premier supérieur a 17

[invite97a92052]

Quand on écrit x = 1^(1/2) c'est que x est la racine carrée de 1. Il y a en toujours deux: x=1 car 1^2=1 mais aussi x=-1 car (-1)^2=1. C'est la même chose ici sauf que c'est modulo 64.

Attention cet argument est faux ! 1 a plus de 2 racines carrées modulo 64, pour être précis, il en a 4, qui sont : 1, -1, 31, 33.
C'est justement pour contourner ce point délicat que j'ai appliqué Euler, qui exclut les racines -1 et 31 sans même qu'on ait besoin de les calculer explicitement.

Par contre il reste toujours le cas 33

[invite1ec1f66d]

pour répondre a g_h:

en appliquant Euler on a bien
p¹⁶=1 mod 32
mais je ne vois pas pourquoi Euler implique que
p¹⁶=1 mod 64
ou
p¹⁶=33 mod 64

[invite97a92052]

pour répondre a g_h:

en appliquant Euler on a bien
p¹⁶=1 mod 32
mais je ne vois pas pourquoi Euler implique que
p¹⁶=1 mod 64
ou
p¹⁶=33 mod 64

Si je te dis que :
x = 1 [10]
Les solutions sont :
x = ..., -9, 1, 11, 21, 31, ...

Si je réécris ça modulo 20, on a :
x = 1 [20] (ce qui donne 1, 21, 41, ...) : il n'y a pas toutes les solutions !
ou x = 11 [20] (ce qui donne -9, 11, 31, ...)

Ici c'est la même chose, quand tu passes d'une équation modulo 32 à une équation modulo 64, il faut faire en sorte de ne rien oublier !

[invite1ec1f66d]

d'accord merci pour l'explication

[invite97a92052]

Bon, c'est drôle mais ton problème me turlupine car je ne vois pas de solution simple.

Voici la solution que je propose pour écarter le cas 33.
Bien sur, on peut l'écarter à l'aide d'un ordinateur, mais ça a moins d'intéret.

On va montrer que pour tout nombre impair , on a :

(oui, c'est beaucoup plus fort que ce dont on a besoin, mais ça marche !)

On a donc :


On veut étudier ça modulo 64. On voit déjà que pour , les termes sont nuls [mod 64 toujours]. Reste les 6 autres termes.
De plus, on a :


J'utilise alors un résultat classique (assez intuitif quand on se penche dessus) pour extraire la puissance maximale d'un nombre premier p divisant une factorielle n!.
La puissance vaut (les divisions sont euclidiennes).

On obtient alors (calcul à la main, faisable de tête, 2 minutes chrono !)
avec :
- impair pour tout , et en particulier,
-
-
-
-
-
-

Notre somme vaut alors, modulo 64 :

Or, pour

On a donc :
(car cf plus haut)

Maintenant, 2 cas possibles :
- pair : est donc un multiple de , donc nul le terme est nul modulo 64
- impair : est la somme de deux nombres impairs, donc pair, et donc même conclusion, le terme est nul modulo 64.

Il nous reste donc :


Ouf !

Je mets ma main au feu qu'il y a plus simple pour ton exo, mais au moins, on a un joli résultat : la puissance 16-ème de tout nombre impair est congrue à 1 modulo 64

[invite1ec1f66d]

chapeau !!