question congruence

[inviteb8f38dc5]

Trouver les entiers relatifs n < 69 tels que :

141^1000 = n (mod 69)

Je ne vois pas quel méthode utiliser , merci de votre aide.
-----

[invitea3eb043e]

Quand on a affaire à des puissances farfelues, il faut essayer de se ramener à des nombres plus simples, par congruence et ensuite de chercher des périodicités dans les restes.
Ainsi, 141 est congru à combien ?
Ensuite, essaie les puissances de ce nombre. Avec un peu de patience, tu vas les trouver (il y en a forcément moins de 69).

[inviteb8f38dc5]

141 = 3 (mod 69) donc 141^1000 = 3^1000 (mod 69)

Mais apres ?

[invitea3eb043e]

C'est un début. Maintenant, avant de mettre 3 à la puissance 1000, tu pourrais essayer la congruence modulo 69 de la puissance 2, puis 3, puis 4. Comme le résultat est compris entre 0 et 69, ça finira par boucler avant d'atteindre 1000.

[A voir en vidéo sur Futura]

[inviteb8f38dc5]

Donc :

3^4 = 12 (mod 69)

3^8 = 144 = 6 (mod 69)

3^16 = 36 (mod 69)


mais je ne vois pas ou ca me mene , je peux bien sur arriver au resultat mais cela me semble trop laborieux en terme de calcul, quel est la bonne methode a adopter dans ce cas ?

[invitea3eb043e]

Déjà fatigué ? Faut poursuivre, ce n'est quand même pas si difficile !

[inviteb8f38dc5]

Ah ok , je voulais juste savoir s'il existait un genre d'astuce, mais s'il ny en a pas , je n'ai pas d'autre choix que de continuer.
Merci a toi Jeanpaul.

[invitea3eb043e]

Les maths, ce n'est pas que du génie, c'est parfois une affaire de patience...