Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Reste de division euclidienne et théorème de Fermat

Posté par
Manga2
20-04-14 à 03:23

Salut tout le monde,
Svp pouvez-vous me donner des indications concernant cet exercice? Merci d'avance!

En utilisant le théorème de Fermat, déterminer le reste de la division euclidienne de 3^{48} par 91 (91 n'est pas premier!).

Il s'agit de la dernière question d'un exercice (on ne nous a pas dit que les questions sont séparés).
Les résultats:

L'ensemble des solutions de l'équation 23x-48y=1 dans \mathbb{Z}^2 est \left\{ (-25+48k,-12+23k)/k\in\mathbb{Z}\right\}

23^2\equiv 1[48]

\forall (a,b)\in\mathbb{N}^2,\,\,\,\left\lbrace\begin{array}l a^{23}\equiv b\,[91] \\ a^{48}\equiv 1\,[91] \end{array} \Rightarrow b^{23}\equiv a\,[91]

\forall n\in\mathbb{N},\,\,\,\left\lbrace\begin{array}l n\equiv 8\,[23] \\ n\equiv 9\,[48] \end{array} \Leftrightarrow n\equiv 537\,[1104]

Encore merci d'avance!

Posté par
Manga2
re : Reste de division euclidienne et théorème de Fermat 20-04-14 à 04:07

Après réflexion je l'ai trouvé! (quand même je n'ai posté demande d'aide qu'après s'être affolé avec la question): On a 91=7x13 et 7 et 13 sont des nombres premiers donc 3^6\equiv 1\,[7] et 3^{12}\equiv 1\,[13] selon le théorème de Fermat. Par élévation au carré on a donc 3^{12}\equiv 1\,[7] donc 7\left|\left(3^{12}-1\right). On a aussi 13\left|\left(3^{12}-1\right). Puisque 13 et 7 sont premiers et différents donc premiers entre eux on a donc 91\left|\left(3^{12}-1\right) donc 3^{12}\equiv 1\,[91] donc 3^{48}\equiv 1\,[91]. On a donc le reste de la division euclidienne de 3^{48} par 91 est 1.

Désolé de vous avoir dérangé (déranger qui à une heure pareille!)

Posté par
Sylvieg Moderateur
re : Reste de division euclidienne et théorème de Fermat 20-04-14 à 07:32

Posté par
flight
re : Reste de division euclidienne et théorème de Fermat 20-04-14 à 12:47

salut

il aurait été plus direct d'ecrire 3^48 = 3^(2*3*6) = (3^6)^8    3^6 = 729 et 729 =1[91]  donc 3^6=1[91]

donc (3^6)^8 = 3^48 = 1[91]

Posté par
Manga2
re : Reste de division euclidienne et théorème de Fermat 20-04-14 à 13:43

Merci Sylvieg.
Merci pour ta réponse, flight. Mais d'où tu tires 729\equiv 1\,[91]? On peut le faire comme ça si c'est 3^6\equiv 1\,[91] que tu veux:

3\equiv 3\,[91]
3^3\equiv 27\,[91]
3^4\equiv 81\,[91]
3^5\equiv 243\,[91] donc 3^5\equiv 61\,[91]
3^6\equiv 1\,[91]

Mais dans ce cas là on n'applique pas le théorème de Fermat.

Posté par
Sylvieg Moderateur
re : Reste de division euclidienne et théorème de Fermat 20-04-14 à 20:14

L'intérêt du théorème de Fermat est de donner un exposant n qui vérifie an 1 [b] sans avoir besoin de chercher. Ici c'est tout à fait adapté.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1734 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !