Enigme Les deux derniers chiffres @ Prise2Tete

scarta · #1

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.

Barbabulle · #2

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.

Milou_le_viking · #3

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!

L00ping007 · #4

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.

scarta · #5

@ 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)

Milou_le_viking · #6

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.

rivas · #7

[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

scarta · #8

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

rivas · #9

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.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

Les deux dernniers chiffres

#0 Pub

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

les feux derniers chiffres

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

les deux derniers chiffees

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

les dzux derniers chiffres

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

les deux derniers chuffres

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

les deux dzrniers chiffres

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

Les deux denriers chiffres

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

Les deux dernieers chiffres

Code:

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

les seux derniers chiffres

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums