Petit théorème de Fermat
dans Arithmétique
Comment calculer le reste de la division euclidienne d'un grand nombre en utilisant le petit théorème de Fermat ??
[Pierre de Fermat (1601-1665) prend toujours une majuscule. AD]
[Pierre de Fermat (1601-1665) prend toujours une majuscule. AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
la réponse est dans la question. La théorème (si tu apprends ce qu'il dit) te donne une congruence (donc des restes par division). Il ne reste qu'à utiliser les propriétés des congruences.
Bien évidemment, ça ne sert que si le grand nombre est une puissance suffisamment grande d'un nombre pas trop grand. Puisque c'est de ça que parle le théorème.
Cordialement.
NB : Je reste dans le général, puisque tu ne donnes pas d'éclaircissement sur le pourquoi de ta question.
Voir:
https://fr.wikipedia.org/wiki/Exponentiation_modulaire
https://fr.wikipedia.org/wiki/Exponentiation_rapide
Comme 17 est premier et ne divise pas 2016 (2016=118*17+10) alors le petit théorème de [large]F[/large]ermat nous donne 2016^(17-1) congrus a 1 modulo 17 .Donc il me reste a calculer maintenant 2016^2002 "l'exposant est toujours grand !!"
[En toute occasion Pierre de Fermat (1601-1665) prend toujours une majuscule. AD]
permet de regarder le nombre en puissance modulo 16.
J'ai bien compris ton problème je pense et les liens ci-dessus répondent à ton interrogation.
Et tu vas te retrouver avec une puissance faible de 2016.
Cordialement.