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 : 3801

Un racccourci 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

  • |
  • Répondre

#0 Pub

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

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

un racxourci d'euclide.

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 : 3801

un racxourci 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 : 888

un raccourci d'euclude.

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 : 3801

Un raccourci d'Euclidee.

@ 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 : 888

un raccourci d'euclode.

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 : 888

Un raccourci d'Euclidee.

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 : 3801

un raccoirci d'euclide.

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 : 3801

Un raccourci d'Eucldie.

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 : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
13-12-2019 Enigmes Mathématiques
P2T
Pouvoir d'achat par perceval
11-06-2008 Enigmes Mathématiques
P2T
15-10-2009 Enigmes Mathématiques
P2T
2009 avec les chiffres de 1 à 9 par LeSingeMalicieux
03-01-2009 Enigmes Mathématiques
25-09-2010 Enigmes Mathématiques
P2T
Le Mont Tagne par starsky
11-02-2018 Enigmes Mathématiques
P2T
Super Bingo par godisdead
08-05-2012 Enigmes Mathématiques
18-03-2020 Enigmes Mathématiques
19-09-2022 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

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