Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 05-01-2011 12:13:34

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Les deux derniers chhiffres

Parmi tous les entiers compris entre 0 et 99, quels sont ceux qui peuvent se trouver à la fin d'un entier de la forme N^N ?

La case réponse valide leur somme.



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 05-01-2011 14:36:50

Barbabulle
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 237

Les deux derniers chifres

Il apparaît évident que la suite a(n)=n^n%100 est périodique de période 100. En calculant donc les 100 premiers termes de cette suite et en retirant les doublons, nous obtenons :
1, 4, 27, 56, 25, 43, 16, 89, 0, 11, 53, 75, 77, 24, 79, 21, 84, 67, 76, 3, 36, 69, 31, 13, 17, 59, 41, 64, 7, 96, 63, 49, 51, 73, 57, 39, 61, 44, 47, 23, 29, 71, 33, 97, 19, 81, 87, 83, 9, 91, 93, 37, 99
Qui donne alors la somme 2600.


La paix dans le monde n'est pas menacée par les révoltés, mais par les soumis.        Georges Bernanos

 #3 - 05-01-2011 16:17:27

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

les deux dernierq chiffres

Pour le moment, je n'ai qu'un début de raisonnement.

N peut s'écrire par A+B avec A les dizaines et B les unités.
Alors

N^N mod(100)
= (A+B)^(A+B) mod(100)
= (A+B)^A . (A+B)^B mod(100)
= B^A . (A.B.B^(B-1)+B^B) mod(100)
= B^A . B^B . (A+1) mod(100)
= (A+1) . B^(A+B) mod(100)

Et on trouve toutes les valeurs possible avec :
- A = 0, 10, 20, 30, 40, 50, 60, 70, 80 ou 90.
- B = 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9.

Il y a donc 100 possibilités à tester.

D'autre part, il existe un cycle de 20 tel que

B^(A+B) mod(100)
= 1, 4, 27, 56, 25, 56, 43, 16, 89, 0, 1, 96, 23, 56, 25, 16, 7, 24 ou 89.

Il n'y a plus qu'à faire les calculs dans un tableur.

Je trouve 53 possibilités différentes (y compris 0) dont la somme vaut 2600.

Et ça marche enfin!

 #4 - 05-01-2011 17:39:59

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Les deeux derniers chiffres

La somme de ces nombres :

1 4 27 56 25 43 16 89 11 53 75 77 24 79 21 84 67 76 3 36 69 31 13 17 59 41 64 7 96 63 49 51 73 57 39 61 44 47 23 29 71 33 97 19 81 87 83 9 91 93 37 99

vaut

2600

Dédicace à la fonction bcpowmod de PHP ... (bouh j'ai honte)


EDIT
Essayons d'être un peu plus précis :
Je n'ai testé que les nombres N^N pour N de 0 à 99. Je pense que ta remarque porte sur tous les autres nombres N >= 100, montrer que N^N donne les mêmes restes modulos 100 que ceux de 0 à 99. Tentative d'explication.

Les nombres supérieurs à 100 s'écrivent N=100x+y avec y entre 0 et 99, donc (100x+y)^N vaut y^N modulo 100
- Dans le cas où y est premier avec 100 :
y^100x = (y^100)^x=1^x modulo 100 car y est inversible dans Z/100Z
et y^(100x+y) vaut donc y^y modulo 100
- Dans le cas où y n'est pas premier avec 100
Il faudrait montrer de la même manière que y^(100x+y) vaut bien y^y modulo 100, j'ai commencé à me pencher sur la question, mais je ne vois pas encore une manière simple de le montrer, mes souvenirs d'algèbre datent un peu ...

Du coup, y^(100x+y) vaut y^y modulo 100, on se ramène ainsi au cas où N est entre 0 et 99.

Il suffit ensuite de traiter les 100 cas de manière systématique (5 lignes en PHP avec la fonction bcpowmod, avec Excel j'ai pas cherché plus loin comment traiter les très grands nombres), pour trouver la liste, puis la somme, ci-dessus.

 #5 - 05-01-2011 18:25:41

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

les deux dernoers chiffres

@ Barbabulle & L00ping007 :
Vous n'expliquez pas pourquoi il n'y a pas d'autres valeurs que celles là (et je trouve que le "évident" de Barbabulle est un peu facile, ou alors j'ai raté un truc super simple)

 #6 - 06-01-2011 08:56:55

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

Les dexu derniers chiffres

Je viens de relire (parfois une nuit de sommeil ça aide), mais je ne trouve pas mon erreur.

Un indice ?

EDIT : merci pour l'aide. A deux fautes de frappes prêt j'avais bon. smile

 #7 - 07-01-2011 17:01:27

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

les deux dernierq chiffres

[TeX]a^{99} \equiv 1 [100][/latex] car [latex]Z/100Z*[/latex] a 99 éléments et donc l'ordre (multiplicatif de chacun) est un diviseur de l'ordre du groupe (au sens large).
Donc [latex]a^{100} \equiv a [100][/TeX]
J'utilise aussi le (début du) développement de:
[TeX](10+a)^{10+a}[/latex] pour montrer que: [latex](10+a)^{10+a} \equiv 11.a^{10}.a^a [100][/TeX]
Cela réduit la recherche aux [latex]N^N[/latex] entre 0 et 99 en permettant d'avancer en itérant sur des nombres pas "trop grands".
On trouve la liste ci-dessous dont la somme 2600 est validée par la case réponse.

Je n'ai rien trouvé de mieux pour le moment.

Merci pour cette énigme.

0
1
3
4
7
9
11
13
16
17
19
21
23
24
25
27
29
31
33
36
37
39
41
43
44
47
49
51
53
56
57
59
61
63
64
67
69
71
73
75
76
77
79
81
83
84
87
89
91
93
96
97
99

 #8 - 09-01-2011 14:11:53

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

lrs deux derniers chiffres

Bon alors pour commencer, N^N %100 n'est pas vraiment périodique de période 100.
Pour preuve, 0^0 = 1 et 100^100 % 100 = 0.

Sinon, on peut d'ores et déjà éliminer beaucoup de nombres:
- Si N^N est pair, alors N est pair, donc N^N est le carré de N^(N/2). Or aucun carré ne se termine par un 2 ni par un 8; donc tous les nombres de la forme 10k+2 et 10k+8 peuvent être éliminés.
- Si N^N est pair, alors N est pair et > 1. Donc N^N est (au moins) un multiple de 4. Comme 100%4 = 0; tous les nombres pairs qui ne sont pas multiples de 4 peuvent être éliminés.
- Enfin, si N^N est un multiple de 5, alors N est un multiple de 5 et > 1. Donc N^N est un multiple de 25 (au moins) et donc tous les nombres qui sont multiples de 5 et qui ne se terminent pas par 0, 25, 50 ou 75 peuvent être éliminés. De plus, les multiples de 50 doivent être des multiples de 100; donc 50 peut être éliminé aussi
On a donc éliminé pour l'instant 47 valeurs.
2, 5, 6, 8, 10, 12, 14, 15, 18, 20, 22, 26, 28, 30, 32, 34, 35, 38, 40, 42, 45, 46, 48, 50, 52, 54, 55, 58, 60, 62, 65, 66, 68, 70, 72, 74, 78, 80, 82, 85, 86, 88, 90, 92, 94, 95, 98

On peut trouver par contre des valeurs de N pour les 53 valeurs restantes:

Code:

00: 10  01: 0   03: 27  04: 2   07: 43  09: 89
11: 11  13: 33  16: 8   17: 37  19: 79
21: 21  23: 67  24: 18  25: 5   27: 3   29: 69
31: 31  33: 73  36: 28  37: 97  39: 59
41: 41  43: 7   44: 62  47: 63  49: 49
51: 51  53: 13  56: 4   57: 57  59: 39
61: 61  63: 47  64: 42  67: 23  69: 29
71: 71  73: 53  75: 15  76: 24  77: 17  79: 19
81: 81  83: 87  84: 22  87: 83  89: 9
91: 91  93: 93  96: 44  97: 77  99: 99

 #9 - 09-01-2011 23:47:32

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

led deux derniers chiffres

J'ai ecrit un peu abusivement que [latex]a^{100}\equiv a [100][/latex].
Je suis allé un peu vite en besogne pour avoir le temps de répondre.
En fait cela est vrai pour les a premiers avec 100, c'est à dire n'ayant ni facteurs 2 ni facteurs 5. Pour ceux-la soient il sont aussi générateurs d'un sous-groupe de Z/100Z* soit il en existe une puissance qui donne 0 modulo 100 et cette puissance divise aussi 100. On peut donc en effet se ramener à étudier les nombres de 0 à 100.
0^0=1 est une convention et doit être traité séparemment. Il vaut donc mieux regarder les nombres de 1 à 100 et gérer à part 0^0.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete