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 - 27-11-2017 08:20:09

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

un raccoueci d'euclide.

Bonjour à tous.

Si je vous demande si tout entier n, premier avec 6, peut diviser un nombre de la forme 24k+1, vous me répondrez oui car :

n * j = 24 * k + 1
n * j - 24 * k = 1 existe car n premier avec 24 (Bezout)

Vous pourrez même me trouver le plus petit k par l'algorithme d' Euclide.

Oui, mais si je vous dis qu'on peut trouver ce plus petit k en 2 opérations seulement, me croiriez vous ?

Bon amusement



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 27-11-2017 11:07:29

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

Un raccourci d'Euclidde.

Très sympa (même si j'ai mis un moment avant de comprendre ce que tu demandais ^^)
Bref, pour n donné, on a k = (n²-1)/24 modulo n

Pour k = (n²-1)/24, on a 24k+1 = n² donc bien multiple de n
Et si nj-24k = 1, (avec j = n dans ce cas particulier) alors les j valides sont de la forme  n+24z et les k valides de la forme (n²-1)/24 + nz, avec z un relatif quelconque.

Et de là, on trouve le plus petit : (n²-1)/24 modulo n

Je suis pas sûr que ça soit "2 opérations seulement", tout dépend de ce qu'on appelle une opération quoi (là y'a le carré, la soustraction, la division, et le modulo, ça fait 4; mais bon le calcul est direct quand même)

 #3 - 27-11-2017 14:55:10

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

Unn raccourci d'Euclide.

Oui Scarta c'est bien ça, bravo !

Je redoutais que ça reste sans réponse, même si elle n'est pas difficile....une fois qu'on a la solution.

2 ou 4 opérations élémentaires, selon comme on le voit. Disons 2 étapes de calcul.

 #4 - 27-11-2017 22:08:20

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 530

Un raccourci d'Euclide

Salut nodgim,

en fait il suffit de considérer n modulo 24 :

si n = 24a+1 alors k = -a (car 1.(24a+1)+(-a).24=1).
si n = 24a+5 alors k = -5a-1 (car 5.(24a+5)+(-5a-1).24=1).
si n = 24a+7 alors k = -7a-2 (car 7.(24a+7)+(-7a-2).24=1).
si n = 24a+11 alors k = -11a-5 (car 11.(24a+11)+(-11a-5).24=1).
et symétriquement,
si n = 24a-1 alors k = a
si n = 24a-5 alors k = 5a-1
si n = 24a-7 alors k = 7a-2
si n = 24a-11 alors k = 11a-5.

 #5 - 28-11-2017 08:14:03

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

un racvourci d'euclide.

@ Ebichu :

Effectivement, en étudiant les 8 valeurs modulo 24 de n, on peut calculer une formule qui donne le plus petit k. ça suppose de disposer de la liste des 8 formules si on ne veut pas les recalculer à chaque fois, ce qui n'est pas forcément plus court que l'algorithme d'Euclide.

Et si tu étudiais les valeurs modulo 24 du carré de n ?

 #6 - 28-11-2017 09:00:56

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 530

Un raccourci d'Euclide..

La complexité de ma méthode est meilleure que celle de l'algorithme d'Euclide, qui demande un nombre d'étapes qui peut être aussi grand que l'on veut.

PS : mmh, je dis n'importe quoi. Comme un des deux nombres vaut 24, le nombre d'étapes est borné.

Qui plus est, il est facile de résumer cette méthode avec une seule formule :
* étape 1 : on écrit n sous la forme 24*a+r avec r compris entre -11 et 11.
* étape 2 : k = -r*a-(r² mod 23)+1.

 #7 - 28-11-2017 11:48:31

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 530

Un raccouri d'Euclide.

Si je comprends bien, ta méthode, c'est de faire (n²-1)/24 mod n ? Ça nécessite quand même de calculer n², ce qui est coûteux pour n grand. Mais ça répond bien à la question posée.

 #8 - 28-11-2017 11:49:54

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

un raccourci d'euxlide.

Ebichu, je n'ai pas dit que ce que tu as fait ne marche pas. Il y a plus direct.

 #9 - 28-11-2017 11:51:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

Un raccouric d'Euclide.

Croisement avec ton dernier message....

C'est bien en effet ce à quoi je pensais.

 

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 : Pim, Pam et ?

Sujets similaires

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