Dsa

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Jean-Laurent

J'aimerai savoir comment prouver que

140^101=1[7879]

Merci


Posted by: Trident

A=140^101=(140^2)^50*140

140^2=3842+2*7879

A=3842^50*140=(3842²)^25*140

3842²=1873*7879+3597

A=(3597^24)*3597*140

3597²=1642*7879+1091
3597*140=63*7879+7203

A=1091^12*7203

1091²=151*7879+552

A=552^6*7203

552^3=21347*7879+3595

A=3595²*7203

3595²=1640*7879+2465

A=2465*7203=2252*7879+4684

A=4684[7879]


Biensur je me suis aider de la calculette....

7879 étant premier, je ne vois pas d'autre methode que la brutte (enfin, je
n'en connais pas d'autre).

Pierre.





Posted by: pierre.bernard@tiscali.fr

> 140^101
> =4684[7879]

Ma calculatrice trouve plutôt :
140^101=4008 [7879]
En tout cas, je ne trouve pas 1.
Enoncé faux ?

Pierre




Posted by: albert junior

Trident wrote:
> A=140^101=(140^2)^50*140
>
> 140^2=3842+2*7879
>
> A=3842^50*140=(3842²)^25*140
>
> 3842²=1873*7879+3597
>
> A=(3597^24)*3597*140
>
> 3597²=1642*7879+1091
> 3597*140=63*7879+7203
>
> A=1091^12*7203
>
> 1091²=151*7879+552
>
> A=552^6*7203
>
> 552^3=21347*7879+3595
>
> A=3595²*7203
>
> 3595²=1640*7879+2465
>
> A=2465*7203=2252*7879+4684

2465*7203 = 4008 mod 7879

Non, cette ligne est fausse (la dernière, j'ai tout recompté !).

Je confirme les propos de l'auteur précédent

> A=4684[7879]

-
albert




Posted by: Jean-Laurent

effectivemenent l'énoncé est faux

170^101=1[7879]

Merci pour l'aide


Posted by: Trident

>> A=2465*7203=2252*7879+4684
>
> 2465*7203 = 4008 mod 7879
>
> Non, cette ligne est fausse (la dernière, j'ai tout recompté !).
>
> Je confirme les propos de l'auteur précédent
>
>> A=4684[7879]


Effectivement, j'avais tappé 2464 au lieu de 2465...
'solé

Donc, y'a pas d'autre méthode ?





Posted by: Sean McIlroy

## MAPLE:
> with(numtheory):

> ifactor(170);

(2) (5) (17)

> 2^101 mod 7879;

2580

> 5^101 mod 7879;

6801

> 17^101 mod 7879;

6035

> 2580*6801*6035;

105893610300

> 105893610300 mod 7879;

1




Posted by: Hibernatus

Sean McIlroy wrote:
> ## MAPLE:
>
>>with(numtheory):
>
>
>>ifactor(170);

Bien joué :)

Après combien d'essais ?



Posted by: Jean-Laurent

C cool ca marche nickel !
Par contre le calcul de 1/73 [10007] ne me donne pas de résultats
cohérent !


Posted by: Hibernatus

Jean-Laurent wrote:

> C cool ca marche nickel !
> Par contre le calcul de 1/73 [10007] ne me donne pas de résultats
> cohérent !

x = 1/73 = 10008/73 = 137 + 7/73

donc x = 137 + 7x
6x = -137 = 9870
x = 9870/6

Or 1/6 = 10008/6 = 1668

donc x = 9870 * 1668 = 1645.

1/73 = 1645.

On vérifie que 1645 * 73 = 120085 = 1 + 12 * 10007.

----

Remarque amusante : 9870 * 1668 = 1645 + 1645 * 10007

(étatit-ce évident ?)

----

Autre démarche : 1/73 = 10008/73 = 137 + 7/73 = 137n + (6n+1)/73

Pour n = 12, 6n+1 = 73, donc 1/73 = 137*12 + 1 = 1645.


Hib.



Posted by: pierre.bernard@tiscali.fr

170 convient. Mais voici d'autres nombres modulo 7879 qui conviennent :

2^78 = 3516
3^78 = 170
4^78 = 105
5^78 = 590
etc

Car, modulo 7879, on a x^101 = 1 si et seulement si x est une puissance
78-ème (non nulle).
Cela vient entre autre de : 78*101 = 7878.

Pierre




Posted by: Alain Pichereau

On Sat, 14 May 2005 23:36:43 +0200, "Jean-Laurent" <jeanlaurent@fr.st>
wrote:


>Par contre le calcul de 1/73 [10007] ne me donne pas de résultats
>cohérent !
>
>--
autre façon
par l'algo d'Euclide on recherche le pgcd de 10007 et 73
qui doit être 1
10007=137*73+6
73=12*6+1
donc 10007 et 73 sont bien 1er entre eux, donc 73 a un inverse modulo
10007 qu'on obtient en cherchant la relation de Bezout
1=73-12*(10007-73*137)
1=73*1645-12*10007
et l'inverse de 73 est 1645 mod 10007
*****************
http://perso.wanadoo.fr/alain.pichereau/
( olympiades mathématiques 1ère S )
*****************











-