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 - 07-04-2017 21:35:01

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

fraction tardivement irréductibke

Bonsoir @ tous.

Soit N/D = (b-a) / (1 + a*b) avec 1 <= a < b entiers.

Pour un N donné, on dit que N est " ir k " si la fraction N / D est irréductible seulement au k-ième plus petit D.

Exemple N = 10
10 / (1 + 1*11) = 10 / 12 réductible
10 / (1 + 2*12) = 10 / 25 réductible
10 / (1 + 3 * 13) = 10 / 40 réductible
10 / (1 + 4 * 14) = 10 / 57 irréductible

10 est donc  " ir 4 "

Trouver le plus petit N  " ir 20 ".

Amusez vous bien



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 08-04-2017 08:14:16

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

Fraction ardivement irréductible

Et pour les plus avisés : quels sont les " k " pour lesquels " ir k " existe ?

 #3 - 09-04-2017 07:00:13

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

fraction tardivzment irréductible

Bonjour,
Voici ce que j'obtiens, par bricolage :

Code:

"ir  2" =                2 = 2
"ir  4" =               10 = 2*5
"ir  6" =              170 = 2*5*17
"ir 10" =             6290 = 2*5*17*37
"ir 14" =           635290 = 2*5*17*37*101
"ir 16" =        125152130 = 2*5*17*37*101*197
"ir 20" =      32164097410 = 2*5*17*37*101*197*257
"ir 24" =   12897803061410 = 2*5*17*37*101*197*257*401
"ir 26" = 7442032366433570 = 2*5*17*37*101*197*257*401*577

En posant k0=1, chaque "ir k" est égal à :
produit( (ki^2 + 1) ) pour 0 ≤ i ≤ k-1.

 #4 - 09-04-2017 07:56:17

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

Fraction taardivement irréductible

Enigmatus, c'est bien ça, bravo !

Evidemment, je m'attendais à des méthodes de routine. La justification est cependant très rapide, 1 ou 2 lignes suffisent (quoique ce que tu as écrit est plus avancé encore que ce que j'avais vu, mais il faut que je regarde si ça marche toujours, je n'en suis pas sûr...)

 #5 - 09-04-2017 08:09:49

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

Fraction tardvement irréductible

nodgim a écrit:

je n'en suis pas sûr...

Moi non plus… smile

 #6 - 09-04-2017 09:12:38

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

fraction tardivement irrédictible

En fait, ta conjecture n'est pas correcte. Il faut que tu ailles un peu plus loin dans ta recherche pour t'en rendre compte. Et, oui la primalité des nombres est importante dans ce problème....

 #7 - 09-04-2017 12:04:49

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

fraction tardovement irréductible

J'ai fait un calcul exhaustif jusqu'à "ir 16". Au-delà, je ne sais pas si les nombres trouvés en #3 sont les plus petits.

 #8 - 09-04-2017 13:30:36

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

Fraction tardivemnet irréductible

Pourquoi ir 16 ? Tu as donné les nombres jusqu'à ir 26.

 #9 - 09-04-2017 13:58:07

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

fraction tardivrment irréductible

nofgim #8 a écrit:

Pourquoi ir 16 ? Tu as donné les nombres jusqu'à ir 26.

En effet, j'ai calculé tous les nombres de 1 à 125152130 (C'est le plus petit "ir 16").
Au-delà, j'ai vérifié par exemple que 32164097410 était bien "ir 20", mais il pourrait y en avoir un plus petit.

 #10 - 09-04-2017 15:15:42

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 453

Fraction tardivement iréductible

Je n'ai pas tellement le temps de justifier, mais je tente 32164097410=2*5*17*37*101*197*257.

L'idée est que si on prend N de la forme 2*n, alors pour i impair, la fraction N/(1+i*(N+i)) sera simplifiable par 2.
Si on prend N de la forme 5*n, alors pour i=2 ou 3 modulo 5, la fraction N/(1+i*(N+i)) sera simplifiable par 5.
Si on prend N de la forme 17*n, alors pour i=4 ou 13 modulo 17, la fraction N/(1+i*(N+i)) sera simplifiable par 17.
Et ainsi de suite. Les deux nombres comme 4 et 13 sont à chaque fois les solutions de x²=-1 dans Z/pZ.

Je suppose que la conjecture d'enigmatus que tu invalides, c'est parce que si on continue, on trouve 401, 577, 677 puis 1157=13*89 qui lui n'est pas premier.

Quand tu demandes quels sont les " k " pour lesquels " ir k " existe, as-tu la réponse ? Ça me parait intuitivement difficile à obtenir, mais si tu me dis que c'est possible, ça pourrait me motiver à chercher.

 #11 - 09-04-2017 16:05:22

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

Fraction tarddivement irréductible

OK Ebichu, c'est bon pour toi également,bravo !

Tu as vu que la réponse était assez simple, mais il fallait reprendre le problème sous un autre angle.

La question subsidiaire n'a pas en effet de réponse simple, c'était en quel que sorte un piège, dans lequel Enigmatus est tombé, et de peu !   

Comme je ne pourrai pas donner la réponse au bout du temps imparti, j'anticipe en la donnant maintenant.

------------------------------------------------------------------------------------------

Soit N/D = (b-a) / (1 + ab) avec 1 <= a < b entiers. Pour un N donné, on dit que N est " ir k " si la fraction N / D est irréductible seulement au k-ième plus petit D.

Exemple N = 10

10 / (1 + 1 * 11) = 10 / 12 réductible
10 / (1 + 2 * 12) = 10 / 25 réductible
10 / (1 + 3 * 13) = 10 / 40 réductible
10 / (1 + 4 * 14) = 10 / 57 irréductible

10 est donc  " ir 4 " Trouver le plus petit N  " ir 20 ".

---------------------------------------------------------------------------------------------

Soit p, un facteur commun à N et D.
On a N = b - a = 0 modulo p, donc b = a modulo p, donc D = 1 + ab = 1 + a² modulo p.

On a donc un facteur commun si 1 + a² divise N. Autrement dit, tant que N possède au moins un facteur premier dans la suite des 1 + a² successifs (1 + 1², 1+ 2², ...), la fraction sera réductible. 
Il suffit donc d'attribuer à N le plus petit facteur premier nouveau de chaque 1+ a² .


Suite des 1+ a² et leur décomposition :

1: 2 ------------> ici on donne à N la valeur 2 (c'est le plus petit nombre pair). N sera irréductible au rang suivant, soit 2. 2 est donc ir 2. 
2: 5 ------------> ici, si on veut aller plus loin, on doit donner à N le facteur 5, soit 2 * 5 = 10. 10 est réductible au rang 3, mais pas au rang 4. 10 est ir 4. 
3: 10 = 2 * 5
4: 17------------------> si N = 2 * 5 * 17, il est ir 6
5: 26 = 2 * 13
6: 37 ------------------> si N = 2 * 5 * 17 * 37, il est ir 10
7: 50 = 2 * 5 * 5
8: 65 = 5 * 13
9 : 82 = 2 * 41
10: 101  ------------------> si N = 2 * 5 * 17 * 37 * 101, il est ir 14
11: 122 = 2 * 61
12: 145 = 5 * 29
13: 170 = 2 * 5 * 17
14: 197 ------------------> si N = 2 * 5 * 17 * 37 * 101 * 197, il est ir 16
15: 226 = 2 * 113
16: 257  ------------------> si N = 2 * 5 * 17 * 37 * 101 * 197 * 257 , il est ir 20
17: 290 = 2 * 5 * 29
18: 325 = 5 * 5 * 13
19 :362 = 2 * 181
20: 401

Attention : il se trouve que les nombres 1 + a² qui ont des facteurs premiers inconnus du N précédent sont tous premiers dans cette liste. Ce n'est pas toujours vrai. Pour a = 34, 1 + 34² = 13 * 89, avec 13 et 89 qui sont inconnus du N précédent. Pour trouver le plus petit N suivant, il faut le multiplier par 13 ( qui donnera ir 34 ) et non par 13 * 89.

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

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