[Arithmétique] Calcul d'une puissancielle modulo 23

anthony_unac · 15/05/2010 - 19h11

Bonjour,

Pouvez vous me donner un coup de main pour déterminer $r$ dans l'équation :
$7?\equiv\ r\[23]$ avec $7?$ la puissancielle de 7

Avant de sécher sur cette dernière équation, j'ai résolu sans soucis l'équation suivante :
$6?\equiv\ r_1\[23]$

en procédant comme ceci :
*********************

$6?\equiv\ r_1\[23]$
$6?=6^{5?}=23* k_1 + r_1$
$6^{phi(23)}=6^{22}\equiv\ 1[23]$ car 6 est premier avec 23

$5?\equiv\ r_2\[22]$
$5?=5^{4?}=22* k_2 + r_2$
$5^{phi(22)}=5^{10}\equiv\ 1[22]$ car 5 est premier avec 22

$4?\equiv\ r_3\[10]$
$4?=4^{3?}=10* k_3 + r_3$ et arrivé à ce stade, les entiers mis en jeu sont suffisamment petits pour pouvoir résoudre l'équation :
$4?=4^{3?}=10* k_3 + r_3$
$4?=262144=10* 26214 + 4$
$r_3=4$
$4?\equiv\r_3[10]\equiv\ 4[10]$

Connaissant $r_3$ , on en déduit :
------------------------------

$r_2=5^{r_3}=5^4=625$
$5?\equiv\5^4[22]\equiv\ 9[22]$

$r_1=6^{r_2}=6^{625}$
$6?\equiv\6^9[23]\equiv\ 16[23]$

Ainsi $6?\equiv\ 16[23]$

Mais lorsqu'on essaie de procéder de la même manière pour résoudre : $7?\equiv\ r\[23]$
On se heurte alors à l'obstacle suivant :
*****************************
$7?\equiv\ r\[23]$
$7?=7^{6?}=23* k + r$
$7^{phi(23)}=7^{22}\equiv\ 1[23]$ car 7 est premier avec 23

$6?\equiv\ r_b\[22]$
$6?=6^{5?}=22* k_b + r_b$
$mais 6^{phi(22)}=6^{10}\not\equiv\ 1[22]$ car 6 n'est pas premier avec 22
Du coup la résolution bloque !

Quel est alors l'outil qui permet de débloquer la situation.

Cordialement
Anthony

Thorin · 16/05/2010 - 01h16

Salut,

on peut montrer que :
- $\forall k>0 \ 5^k = 5[10]$

- $\forall k>0 \ 6^{10k+5} = 12*7776 [22]$

on en déduit successivement :

- $6^{5?}=12*7776=2[22]$

- $7^{6?}=7^{22k+2}=49=3[23]$

Tous les signes d'égalités sont à prendre en tant que "modulo"

hhh86 · 16/05/2010 - 09h26

Bonne méthode. En faisant autrement, j'avais trouvé que 7? est congru 13 ou -13 [23], j'arrivais pas à me débarrasser de l'indetermination du signe. D'où mon interrogation devant ton résultat.
7776 ne serait pas congru 10 modulo 22 par hasard ?

Thorin · 16/05/2010 - 10h12

7776 ne serait pas congru 10 modulo 22 par hasard ?

en fait, 12*7776 est congru à 10 modulo 22, j'avais mal tapé le calcul

anthony_unac · 16/05/2010 - 10h19

Envoyé par Thorin

Salut,

on peut montrer que :
- $\forall k>0 \ 5^k = 5[10]$

- $\forall k>0 \ 6^{10k+5} = 12*7776 [22]$

on en déduit successivement :

- $6^{5?}=12*7776=2[22]$

- $7^{6?}=7^{22k+2}=49=3[23]$

Tous les signes d'égalités sont à prendre en tant que "modulo"

Bonjour Thorin,

Votre première remarque est géniale et je crois qu'elle va débloquer la situation. Par contre j'ai un doute sur la fin de votre calcul

Ne serait ce pas plutot :
*****************
$6^{5?}=12*7776=93312=10[22]$
$7^{6?}=7^{22k+10}=7^{10}=13[23]$

Cordialement
Anthony

hhh86 · 16/05/2010 - 10h31

Envoyé par anthony_unac

Bonjour Thorin,

Votre première remarque est géniale et je crois qu'elle va débloquer la situation. Par contre j'ai un doute sur la fin de votre calcul

Ne serait ce pas plutot :
*****************
$6^{5?}=12*7776=93312=10[22]$
$7^{6?}=7^{22k+10}=7^{10}=13[23]$

Cordialement
Anthony

Voir ma remarque et celle de Thorin plus haut