Meilleure réponse
Tout dabord, vous devez regarder le module (ou le nombre que nous « essayons de diviser par). Dans ce cas, cela » est 1818. Ensuite, vous insérez 1818 dans la fonction totient de Euler « , pour obtenir ϕ (18) ϕ (18). En particulier, pour tous les entiers nn, on a
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
où le produit passe par tous les facteurs premiers uniques de nn. Donc, dans ce cas,
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, donc létape suivante est le Théorème dEuler , qui dit que pour tout autre entier aa qui est relativement premier à nn, nous avons que aa à la puissance ϕ (n) ϕ (n) laisse un reste de 11 lorsquil est divisé par nn. Autrement dit,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Puisque 1717 est en effet relativement premier par rapport à 1818, nous connaissons 176176 feuilles un rappel de 1. Cela signifie que nous pouvons simplement continuer à diviser 176176 sur 1720017200 sans changer le reste. Une autre façon de dire ceci est que 17 à toute puissance qui « un multiple de 6 laissera un reste de 1. Donc à la fin, puisque 200 est 2 de plus quun multiple de 6, nous savons que
17200≡172 (mod18) .17200≡172 (mod18).
Cela rend le problème beaucoup plus simple – nous y sommes presque! Un raccourci ici pour terminer le problème est de se rendre compte que 1717 laisse un reste de −1−1 lorsquil est divisé par 1818 (soit 17≡ − 1 (mod18) 17 1 − 1 (mod18)), donc 172172 laisse un reste de (- 1) 2 = 1. (- 1) 2 = 1.
Notre réponse est donc 1 . La prochaine fois que vous rencontrez un problème concernant le reste dune grande puissance, vous pouvez utiliser cette belle solution généralisée et avoir un son intelligent en même temps :). Si vous navez pas vu la notation modmod auparavant, consultez Arithmétique modulaire .
PS Vous avez peut-être entendu parler dun cas particulier de ce théorème appelé le petit théorème de Fermat , qui fonctionne quand vous avez un module qui « est un nombre premier (pas le cas ici). Le théorème dit que pour tout premier pp et un entier aa qui nest pas un multiple de pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Cest une astuce intéressante mais cest fondamentalement la même chose que « s ci-dessus puisque ϕ (p) = p − 1ϕ (p) = p − 1 pour tout premier pp. Ce type de questions devient vraiment simple si vous comprenez le concept de restes négatifs . Essayez toujours de réduire le dividende à 1 ou -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Réponse
Contexte important nécessaire pour résoudre le problème :
Nous savons que le reste obtenu lorsque r divise pq est le produit des restes obtenus lorsque r divise p et q séparément. Cest ce quon appelle le lemme sur les restes. Vous pouvez le prouver par le théorème de division dEuclide.
La solution
17 quand divisé par 18 laisse le reste -1 (il est pratique de travailler avec -1 que 17)
Lapplication du lemme du reste à 17 × 17 × 17 … × 17 (2000 fois) divisé par 18 sera le reste obtenu lorsque le les restes individuels sont multipliés, cest-à-dire -1 × -1 .. × -1 (2000 fois) qui est le reste est 1 \ blacksquare
Sil était 17 élevé à un nombre impair, le reste serait -1 ou 17 .