CARACTÉRISATION DES QUENINES ET LEUR
Contents
1. 2 414 2 419 2 426 2 428 3 429 2 431 2 438 2 440 3 441 2 443 2 453 2 4559 3 459 5 464 3 468 5 470 2 473 2 476 3 483 2 485 3 488 3 491 2 495 2 498 7 504 11 506 3 509 2 510 10 515 2 516 5 519 2 524 3 525 5 530 2 531 2 534 6 543 2 545 2 546 5 548 3 551 3 554 2 558 2 561 2 564 11 575 2 576 5 581 3 585 2 590 7 593 2 596 3 600 11 606 2 608 3 611 2 614 2 615 2 618 2 624 7 629 2 638 2 639 2 641 2 644 6 645 2 648 10 650 2 651 2 653 2 659 2 660 13 663 3 680 3 683 2 686 2 690 2 699 5 704 3 711 3 713 2 714 6 716 3 719 2 723 2 725 2 726 2 729 3 735 5 740 3 741 2 743 2 744 14 746 2 749 2 755 2 761 2 765 2 771 2 774 2 776 3 779 2 783 2 785 2 789 3 791 2 798 11 800 3 803 2 804 7 806 3 809 2 810 2 813 3 818 2 828 11 831 2 833 2 834 2 846 2 848 3 849 3 854 3 860 3 861 3 866 2 870 2 873 2 876 7 879 2 888 5 891 2 893 2 894 6 900 11 905 3 911 2 915 3 923 2 930 2 933 2 935 2 936 10 938 2 939 2 944 3 950 2 953 2 956 3 965 2 966 5 974 2 975 2 986 2 989 2 993 2 996 5 998 2 999 3 TABLE 3 Les p quenines inf rieures 1000 avec p minimal entre parenth ses indique que p est d ordre seulement n dans Z 2n 17 ainsi obtenus n tant pas prouv2. est d ordre n modulo n 1 D MONSTRATION T 2x mod n 1 donc n x 2 x mod n 1 Ainsi l ordre spiralique de tout l ment est celui de 2 dans l anneau Zm 1Z De m me que pour les quenines il est ais de g n raliser les p recquines tous les n tels que n 1 soit premier par l utilisation d une racine primitive La m thode des effacements est galement valable pour g n raliser tout n et nous allons voir que la repr sentation spirale g n ralis e de la Section 5 est tout fait adapt e 7 ORIENTATION DES RAYONS Par analogie avec le cas des k quenines pour k gt 2 on donne la repr sentation spirale de la Figure 8 aux p recquines l id e est de faire deux rayons pour chaque moiti de la permutation et de renverser le deuxi me rayon par rapport aux quenines 1 gt 6 3 7 9 10 5 8 4 2 2 1 3 7 4 2 5 8 6 3 T gt 9 8 4 9 10 10 5 FIGURE 8 P recquine de 10 CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE 21 Contrairement aux quenines les rayons sont toujours croissants vers le centre de la spirale m me dans le cas de la g n ralisation toutes les racines primitives des Figures 9 et 10 En effet le changement d orientation vers l ext rieur de la spirale correspond dans les k quenines au changement de signe dans le calcul 0 x k x mod 2n 1 Or les p recquines ne pr sentent pas ce changement de signe et don
3. il existe q un diviseur de 2n 1 avec q gt 1 Dans ce cas pour tout m de orbite de q on a m 1 2 q Ce qui implique forc ment que q divise m puisqu il divise la fois 2n 1 et 1 2 q Donc l orbite de q ne contient que des diviseurs de q Or 1 q 1 ne divisent pas q donc l orbite de q ne peut tre compl te Par la suite 2n 1 ne peut tre admissible Or il est possible de compl tement caract riser les quenines Ceci peut tre fait avec un peu de th orie des corps finis 2 CARACT RISATION DES QUENINES Nous rappelons qu un g n rateur du groupe des inversibles d un corps fini est ap pel une racine primitive de l unit En effet c est une racine q 1 i me de 1 et la primitivit vient du fait qu elle n est pas une racine d ordre inf rieur Nous avons vu que Monique Bringer a donn une condition suffisante et les cas particuliers du Th or me 1 Jacques Roubaud donne une caract risation dans Roubaud 1993 2 4 II qui semble incorrecte Une condition n cessaire et suf fisante pour que n soit admissible est qu il soit d ordre n ou 2n dans le groupe multiplicatif des entiers modulo 2n 1 Dans cette caract risation le cas o n est pair n est pas consid r un contre exemple simple est celui de l octine 2 est d ordre 8 modulo 17 mais malheureuse ment l orbite de 2 n est que d ordre spiralique 4 ce qui rend l octine impossible Nous don
4. s primitifs ils sont appel s racines primitives indus trielles N anmoins aucun contre exemple n ayant t trouv Dubrois Dumas 2006 algorithme 3 il semble donc possible de fabriquer de mani re effective des quenines pour tout n tel que 2n 1 est premier Dans Roubaud 1993 Jacques Roubaud se d sole n anmoins que seuls les entiers n tels que 2n 1 soit premier poss dent une permutation spirale Il propose alors une g n ralisation tous les nombres en proc dant par effacement ce qui donne lalgorithme g n ral 1 de fabrication de pseudo quenines ou spinines D FINITION 2 La n spinine ou n ine puisqu il n y a pas d ambiguit est la permu tation obtenue par effacements sur la X m m ine spirale avec m le plus petit entier sup rieur n tel que 2m 1 est premier Ainsi on peut fabriquer pour tout n des permutations a on le savait d j qui proviennent d une permutation spirale Afin de diff rencier les permutations nous notons la 7 spinine ou plus simplement la septine obtenue par effacement de 8 dans la 3 octine comme 3 8 septine Par opposition la permutation qui serait obtenue par effacement des 8 et 9 dans la 2 neuvine serait not e 2 9 septine Il reste savoir comment repr senter les septines sous forme de spirale Pour cela il faut remarquer que les nombres effac s sont successifs et plus grands que n Ce sont donc les derniers de la spirale En outre l effacement va les rempl
5. y a pas de quenine de cardinal 4 puisque par exemple l orbite de 3 est le sin gleton 3 Roubaud 1993 L Oulipo et plus particuli rement Jacques Roubaud s est alors int ress la qu te des quenines l aide des corps finis En effet consid rons la permutation n inverse de op Celle ci peut tre d finie comme suit Audin 2007 2e E 2x si 2z lt n nt 2n 1 92x sinon D MONSTRATION Soit x tel que 2x lt n alors on 0 n 0 2x x Pour x tel que 2x gt n alors on 06 x on 2 n 1 n n x x Donc on n Id et on tant bijective n est son inverse 12 J G DUMAS Il est clair que les cardinaux des sous groupes cycliques engendr s par 0 o On sont identiques Il revient donc au m me d tudier l un ou l autre des sous groupes L id e est de consid rer les entiers modulo 2n 1 Dans ce cas 6 x est simplement plus ou moins 2x il existe un e 0 1 tel que 6 x 1 2x 2n 1 partir de l Monique Bringer a montr un certain nombre de r sultats dont les suivants TH OR ME 1 Bringer 1969 Sin est admissible alors 2n 1 est premier n 4p west pas admissible n X 1 west pas admissible Sin et 2n 1 sont premiers n est admissible Sin 2p et que p et 4p 1 2n 1 sont premiers n est admissible D MONSTRATION Reprenons seulement de Bringer 1969 la preuve que 2n 1 est forc ment premier Sinon
6. 653 659 683 686 690 713 719 723 725 726 741 743 746 749 755 761 765 771 774 779 783 785 791 803 809 810 818 831 833 834 846 866 870 873 879 891 893 911 923 930 933 935 938 939 950 953 965 974 975 986 989 993 998 TABLE 1 Les quenines inf rieures 1000 indique que 2 est d ordre n dans Z n 1Z Dans Roubaud 1993 Jacques Roubaud indique que 141 est une quenine ceci est inexact Esposito 2000 en particulier 2 est d ordre seulement 94 2 x 47 lt 141 3 x 47 modulo 283 14 J G DUMAS Cette suite se retrouve sur le site de l encyclop die en ligne des suites d entiers de N J A Sloane la r f rence A054639 Il est noter que Joerg Arndt a conjectur la caract risation suivante des quenines Arndt 2009 41 8 2 elles correspondent aux bases normales optimales de type 2 dans GF 2 En fait cette conjecture est une cons quence directe du Th or me 2 et se r crit de la mani re suivante COROLLAIRE 1 2n 1 tant premier soit Z 2n 1Z le corps 2n 1 l ments alors n est admissible si et seulement si Soit 2 est d ordre 2n dans Z 2n 1Z etn 1 ou 2 mod 4 Soit 2 est d ordre n dans Z 9n 17 etn 3 mod 4 D MONSTRATION Les diff rences entre le corollaire et le Th or me 2 r sident dans les deux points suivants 1 2 est d ordre 2n est incompatible avec n 3 mod 4 2 2 est d ordre n est incompatible avec n 1 mod 4 Dans les d
7. condition suffisante Prenons w le cardinal de la plus petite orbite des l ments de 1 n par n et supposons que l l ment u soit d ordre w Dans ce cas le fait qu il existe k tel que 0 u u 1 g u implique donc que 1 g 1 car u est inversible Cela revient g 1 et il y a deux cas 1 Si g 1 Alors w est plus grand que l ordre de g Donc w gt n et donc w n car la permutation est au plus d ordre n 2 Si g 1 Alors a Soit l ordre de g est j 2n et donc g 1 Ainsi g 1 et donc b Soit l ordre de g est j n et n est impair Alors g 1 1 ce qui prouve que n divise 2w Or n est impair donc le lemme de Gauf implique que n divise w L encore w n Ce th or me nous permet alors de conclure sur l existence des quenines COROLLAIRE 2 Soit n tel que 2n 1 est premier Il existe g 1 n tel que ng soit d ordre n D MONSTRATION On consid re la plus petite racine primitive modulo 2n 1 X 2n 1 Il y a deux cas 1 Si x 2n 1 lt n Alors n x 2n 1 Convient 2 Sinon posons g x 2n 1 L ordre j de g est soit n soit 2n En effet g 1 et donc si g g I 1 alors 2n n 1 j ou encore n n 1 j et comme n et n 1 sont premiers entre eux n j Ensuite soit n est pair et donc g 1 g g 1 et donc g est forc ment d ordre 2n soit n est impair g g 1
8. et l ordre de g est n Dans les deux cas n x 2n 1 Convient CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE 17 Par exemple la 2 dixhuitine existe mais on peut pr f rer la 5 dixhuitine de rayon 18 5 3 6 qui est donn e sur la Figure 6 FIGURE 5 La 3 onzine FIGURE 6 La 5 dixhuitine En particulier la Table 3 donne la liste des p quenines inf rieures 1000 avec leur plus petite racine primitive Par ailleurs le th or me suivant montre que l on pourrait toujours utiliser la plus petite racine TH OR ME 4 Grosswald 1981 Le nombre de racines primitives modulo p dans un intervalle de taille au moins p est sup rieur c p 1 pour c lt 537 d s que log p 1 gt 24 En particulier il existe alors des racines primitives modulo p inf rieures p4 Ainsi on peut v rifier que tout premier p lt 16777216 poss de bien une racine primitive plus petite que voir par exemple Silva 2000 Les autres nombres premiers v rifient 1 499 lt P Ao TO et poss dent donc une racine primitive convenable leur plus petite racine primitive N anmoins chercher la plus petite racine primitive est plus difficile que de trouver une racine primitive quelconque voir par exemple Shoup 1992 Murata 1991 Elliott 1997 Le Corollaire 2 nous garantit qu en choisissant une racine primitive au hasard soit celle ci soit sa n gation modulo 2n 1 sera donc
9. l me Puisse t elle de corps non d me me recevoir en secret dans sa chambre Car plus me blesse au c ur que coup de verge si qui la sert l o elle est ne rentre Toujours serai pour elle chair et ongle et ne croirai conseil d ami ni d oncle Et jamais la sur de mon oncle je n aimai plus ni tant de par mon me Et si voisin que l est le doigt de l ongle je voudrais tre son gr de sa chambre plus peut L Amour qui dans le c ur me rentre faire de moi qu un fort de fr le verge Car depuis que fleurit la verge s che et qu Adam l gua neveux et oncles si fine amour qui dans le c ur me rentre ne fut jamais en corps ni m me en me o qu elle soit dehors ou dans sa chambre mon c ur y tient comme la chair l ongjle Car ainsi se prend et s nongle mon c ur en elle ainsi qu corce en verge elle est de joie tour et palais et chambre et je ne prise autant parents ni oncle au ciel j aurai deux fois joyeuse l me si jamais nul de trop aimer n y entre Arnaut envoie sa chanson d ongle et d oncle toi qui tiens son me sous ta verge son D sir dont le prix en chambre entre Sestina Lo ferm voler qu el c r m intra no m p t ges b cs escoissendre ni ongla de lausengi r qui p rd per mal dir s arma e car non l aus batre amb ram ni amb verja sivals a frau lai ont non aurai oncle jausirai j i en vergi r o dins chambra Quand mi s
10. plus petite que n et permettra alors la fabrication d une n ine 5 LA QU TE DES SPININES Il noter qu il est possible de fabriquer des racines primitives au moins de mani re probabiliste avec un algorithme polynomial donc ne n cessitant pas de factorisation de y ni d exploration exhaustive de l ordre Dubrois Dumas 2006 Les l ments 18 J G DUMAS 1 2 2 2 3 2 5 2 6 2 8 3 9 2 11 2 14 2 15 3 18 2 20 6 21 3 23 2 26 2 29 2 30 2 33 2 35 2 36 5 39 2 41 2 44 3 48 5 50 2 51 2 53 2 54 6 56 3 63 3 65 2 68 3 69 2 74 2 75 5 78 5 81 2 83 2 86 2 89 2 90 2 95 2 96 5 98 2 99 2 105 2 111 3 113 2 114 6 116 3 119 2 120 7 125 3 128 3 131 2 134 2 135 2 138 5 140 3 141 3 146 2 153 5 155 2 156 10 158 2 165 3 168 10 173 2 174 2 176 3 179 2 183 2 186 2 189 2 191 2 194 2 198 5 200 3 204 21 209 2 210 2 215 5 216 5 219 5 221 2 224 3 228 13 230 2 231 2 233 2 239 2 243 2 245 2 249 5 251 2 254 2 260 3 261 2 270 2 273 2 278 2 2810 2 2840 3 285 3 288 5 293 2 296 3 299 2 300 7 303 2 306 2 308 3 309 2 315 3 320 3 321 7 323 2 326 2 329 2 330 2 336 5 338 2 341 5 345 3 350 2 354 2 359 2 363 5 366 6 369 3 371 2 375 2 378 2 380 6 384 11 386 2 393 2 398 2 404 3 405 3 410 2 411 2 413
11. Arnaut Daniel XII si cle CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE 11 O6 81 82 83 84 85 86 Os 1 6 3 5 4 2 2 1 6 3 5 4 3 5 4 2 1 6 4 2 1 6 3 5 5 4 2 1 6 3 6 3 5 4 2 1 FIGURE 2 Permutation spirale de la sextine En effet si l on inscrit de haut en bas les rimes d une strophe dans la strophe suivante ces rimes se retrouvent dans l ordre donn lorsque l on suit les m andres de la spirale en partant du bas en 6 on tourne pour rencontrer successivement 1 5 2 4 3 qui forment bien les rimes de la deuxi me strophe Ce type de permutation sur 6 vers est appel une sextine et a t g n ralis n vers par Raymond Queneau D FINITIONS 1 Bringer 1969 Une permutation spirale est une permutation on de l ensemble 1 2 n v rifiant la condition suivante On 2P p Le sous groupe cyclique Gn engendr par o est le groupe de Queneau Daniel Les entiers n tels que Gn soit de cardinal n sont dits admissibles Une permutation spirale avec n admissible est appel e une quenine ou encore une ne Autrement dit n est admissible si et seulement si les orbites po tiques de chacune des rimes sont d ordre spiralique n i e chaque rime se trouve une seule fois un endroit donn de la strophe dans l ensemble du po me Arnaut Daniel a exhib une quenine de cardinal 6 mais toutes les quenines ne sont pas possibles par exemple il n
12. DES QUENINES ET LEUR REPR SENTATION SPIRALE 15 8 15 21 A4 56 63 68 111 116 125 128 140 141 165 176 200 224 260 284 285 296 308 315 320 345 369 404 405 428 440 455 464 476 485 488 506 524 548 551 581 596 608 663 680 704 711 716 729 740 776 789 800 806 813 848 849 854 860 861 905 915 944 956 999 TABLE 2 Les 3 quenines inf rieures 1000 qui ne sont pas des 2 quenines indique que 3 est d ordre n dans Z 9n 17 En effet la repr sentation en spirale n est plus valable il faut l adapter la racine primitive 3 i e aux trois cas possibles dans la d finition de ou 0 L id e est de consid rer 3 rayons comme sur les Figures 3 et 4 Comme il est possible d utiliser n importe quelle racine primitive il faut donc g n raliser cette repr sentation une spirale comportant un nombre de rayons exac tement gal au multiplicateur i e la racine primitive utilis e 1 1 FIGURE 3 La 3 octine FIGURE 4 La 3 neuvine Ainsi tous les entiers n dont 2n 1 est premier permettent d avoir une per mutation spirale g n ralis e Il suffit de savoir fabriquer des racines primitives En particulier la plus petite racine primitive est int ressante puisqu elle permet d avoir la repr sentation spirale la plus simple en ce sens qu elle pr sente le moins de rayons possibles D FINITION 1 La plus petite racine primitive de m est not e x m 4 CARACT RISATION G N RALE Dans cette sec
13. Math amp Sci hum Mathematics and Social Sciences 46 ann e n 184 2008 4 p 9 23 CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE Jean Guillaume DUMAS R SUM Les nombres de Raymond Queneau sont les entiers n pour lesquels la quenine per mutation spirale envoyant tout nombre pair sur sa moiti et tout nombre impair sur son oppos ajout n est d ordre maximal n Nous tudions dans cette note la caract risation des nombres de Queneau les pr c dentes caract risations tant notre connaissance incompl tes Nous proposons en outre une nouvelle repr sentation graphique sous forme de spirale la fois des quenines racine primitive diff rente de 2 et galement des spinines g n ralisation des quenines par la m thode des effacements de Jacques Roubaud Nous tendons ensuite cette repr sentation spirale aux p recquines MOTS CL S P recquine Permutation de Queneau Daniel Quenine Racine primitive Spi rale SUMMARY Characterization of Quenines and their spiral representation The Raymond Queneau numbers are the integers n for which the quenine the spiral permutation sending even numbers to their halves and odd numbers to their opposites added to n is of order n In this note we study the characterization of Queneau numbers since previous characterizations one to our knowledge incomplete We also propose a new graphical representation of spiral shape both of the quenines with p
14. acer dans la n spinine par les entiers qui les suivent dans la m quenine L id e de repr sentation est donc d crire les nombres sur les rayons classiques de la spirale en omettant les CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE 19 ALGORITHME 1 Spinine Roubaud 1993 Entr e Un entier n gt 0 quelconque Sortie La spinine d ordre n 1 Trouver le plus petit m gt n tel que 2m 1 soit premier 2 Fabriquer la y m m ine ou si m est trop grand une m ine quelconque en fabri quant une racine primitive industrielle 3 Fabriquer l orbite spiralique de 1 de la m ine Cela permet de v rifier mais de mani re non polynomiale en la taille de n si la racine obtenue ci dessus est bien primitive 4 Dans cette orbite spiralique de 1 effacer tous les entiers sup rieurs n 5 L orbite ainsi obtenue est p riodique de p riode n successeurs des nombres effac s Ces successeurs sont alors crits en fin de rayon dans l ordre des effacements Cela fonctionne par exemple sur la dixine obtenue partir de la 2 onzine 1 6 3 10 5 9 7 8 4 2 Nous d taillons plut t la fabrication de la septine par effacement de la 2 neuvine Prenons n 7 Choisissons m 9 m 8 serait le plus petit Fabriquons 9 1 8 2 7 3 6 4 5 la 2 neuvine Et1 95 7 6 3 8 4 2 l orbite spiralique de 1 Effa ons dans l orbite de 1 le 8 et le 9 ils sont remplac s respectivement par 4 et 5 qui seront donc plac s
15. appear 2009 AUDIN M Math matiques et litt rature Math matiques et Sciences humaines 178 2007 p 63 86 BACH E SHALLIT J Algorithmic Number Theory Efficient Algorithms Cambridge MA MIT press 1996 BRINGER M Sur un probl me de Raymond Queneau Math matiques et Sciences hu maines 27 1969 p 13 20 DUBROIS J DUMAS J G Efficient polynomial time algorithms computing industrial strength primitive roots Information Processing letters 97 2 2006 p 41 45 ELLIOT P D T A MURATA L On the average of the least primitive root modulo p Journal of the London Mathematicial Society 56 2 p 435 454 ESPOSITO FAR SE G Oulipian exercices 7 2000 http www iap fr users esposito oulipo7 html GROSSWALD E On Burgess bound for primitive roots modulo primes and an application to y p American Journal of Mathematics 103 6 1981 p 1171 1183 MURATA L On the magnitude of the least prime primitive root Journl of Number Theory 37 1 1991 p 47 66 OLIVEIRA E SILVA T Least primitive root of prime numbers 2000 http www ieeta pt tos p roots html ROUBAUD J Un probl me combinatoire pos par la po sie lyrique des troubadours Math matiques et Sciences humaines 27 1969 p 5 12 CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE 23 ROUBAUD J R flexions historiques et combinatoires sur la n ine autrement dit que nine La bibli
16. c par cons quent elles ne pr sentent pas non plus le changement d orientation des rayons 3 FIGURE 9 La 3 p recquine de 6 FIGURE 10 La 5 p recquine de 16 Cela est galement le cas pour les effacements des p recquines comme illustr sur les Figures 11 et 12 FIGURE 11 La 2 10 p recquine de 9 FIGURE 12 La 2 10 p recquine de 7 Dans le cas des quenines l alternance de l orientation des rayons est due au changement de signe de la congruence comme nous venons de le voir La question qui reste pos e est la d termination de cette orientation sur la repr sentation spirale 22 J G DUMAS En regardant les Figures 3 4 et 5 des 3 octine 3 neuvine et 3 onzine on distingue deux types de 3 n quenines suivant que le rayon horizontal est gauche ou droite En observant cette orientation de rayons sur plus de quenines comme par exemple sur la Figure 13 il semble que les 3 n quenines de type 1 rayon sortant gauche soient celles qui v rifient n 0 mod 3 alors que les 3 n quenines de type 2 rayon sortant droite v rifient n 2 mod 3 3 11 3 14 3 15 EST ae a na a FIGURE 13 Quelques orientations de 3 n quenines Une g n ralisation de cette conjecture permettrait alors de dessiner les g n quenines comme celle de la Figure 6 sans connaissance a priori de la permutation g n r e BIBLIOGRAPHIE ARNDT J Algorithms for programmers http www jjj de fxt fxtbook to
17. en fin de spirale SR D La Figure 7 montre deux r alisations de la septine les 3 8 septine et 2 9 septine respectivement partir de la 3 octine et de la 2 neuvine FIGURE 7 Septines partir de la 3 octine gauche et de la 2 neuvine droite Si la septine issue de l octine poss de bien une forme de spirale l effacement du 8 dans la permutation se transcrit par un simple effacement sur la spirale on voit que celle issue de la neuvine bien que toujours spiralique est malheureusement d une esth tique plus discutable En effet il est n cessaire que les groupes 6 7 et 4 5 soient sur le m me rayon mais ils ne s y retrouvent pas dans un ordre croissant 20 J G DUMAS 6 P RECTINES L absence de dixine pure i e sans effacement a conduit Jacques Roubaud et Georges P rec a d velopper une autre permutation similaire dor navant appel e p recquine En effet Georges P rec en a eu besoin pour le d veloppement de son uvre la vie mode d emploi mais la m thode des effacements n existait pas encore Roubaud 1993 D FINITION 3 Une p recquine est une permutation Tmn de l ensemble 1 2 n v rifiant la condition suivante Ta 2x sL 2L IN n t 2g n 1 sinon Pour ces permutations la caract risation est beaucoup plus simple et donne en particulier que n 1 doit tre premier TH OR ME 5 La permutation T x 2 n 1 est d ordre n si et seulement si 2
18. eux cas le caract re de r sidu cit de 2 voir par exemple Bach 1996 Th or me 5 8 1 nous donne la r ponse 1 Sin 3 mod 4 alors 2n 1 7 mod 8 et donc 2 est un r sidu quadratique modulo 2n 1 Ce qui implique que l ordre de 2 ne peut donc pas tre maximal 2n mais seulement inf rieur ou gal n 2 Au contraire si n 1 mod 4 alors 2n 1 3 mod 8 et donc dans cas 2 n est pas un r sidu quadratique modulo 2n 1 Supposons alors que l ordre de 2 est n Il s en suit que 2 1 ou encore 2 1 1 Cela implique que RS 221 2 et donc 2 serait un r sidu quadratique ce qui est absurde 3 G N RALISATIONS DES QUENINES Jacques Roubaud dans Roubaud 1993 g n ralise les quenines aux k quenines permutations pour lesquelles la multiplication par 2 est remplac e par une multipli cation par k consid rons 03 x JE si sr lt n Ogn t 4 2n 1 3xr sin lt 3x lt 2n 3x 2n 1 sinon Notons que 2n 1 tant premier 3x ne peut pas tre gal 2n 1 Cette g n ralisa tion donne par exemple directement l octine ou 3 quenine 1 6 2 5 4 7 8 3 La Table 2 donne les entiers dont 3 est une racine primitive de 2n 1 premier qui ne sont pas des 2 quenines Dans le cas de 3 et plus g n ralement pour tout k 3 est appel le multiplicateur de la quenine et est appel le rayon pour la raison qui suit http www research att com njas sequences A054639 CARACT RISATION
19. nons donc ici une caract risation compl te TH OR ME 2 2n 1 tant premier soit Z 9n 17 le corps 2n 1 l ments alors n est admissible si et seulement si Soit 2 est d ordre 2n 2 est racine primitive dans Z 9n 17 Soit n est impair et 2 est d ordre n dans Z 9n 17 D MONSTRATION Tout d abord prouvons la condition n cessaire Comme l ordre de 2 divise 2n le cardinal des inversibles de Z 2n 1Z les seuls ordres possibles diff rents de n et 2n sont strictement inf rieurs n Supposons que 2 est d ordre j lt n Alors nous avons f 2 272 2 Nous avons donc deux cas CARACT RISATION DES QUENINES ET LEUR REPR SENTATION SPIRALE 13 1 Si 6 2 2 alors l orbite de 2 ne contient que j lt n l ments ce qui n est pas suffisant car n est suppos admissible 2 Dans l autre cas 6 2 2 Or 1 lt 6 x lt n par d finition Donc 1 lt 2n 1 2 lt n ou encore n lt 1 Mais 2 est d ordre 2 modulo 2 x1 1 3 Donc si n est admissible alors 2 est d ordre n ou 2n modulo 2n 1 Il ne nous reste plus qu exclure le cas o n 2p est pair et 2 est d ordre n modulo 2n 1 En effet dans ce cas 2 1 2n 1 Il s en suit que 6P 2 1 F2P2 2 Or nous avons vu que 6P 2 2 Il s en suit de nouveau que la seule possibilit est 69 2 2 Mais alors n n est pas admissible puisque l orbite de 2 par n ne contient qu au plus p lt n l ments dis
20. oth que Oulipienne 5 66 2000 p 99 124 Contribution la r union 395 de l Oulipo le 17 septembre 1993 SHOUP V Searching for primitive roots in finite fields Mathematics of Computation 58 197 1992 p 369 380
21. oven de la chambra ont a mon dam sai que nulhs m non intra ans me son tuch plus que fraire ni oncle non ai membre no m fremisca neis l ongla aissi com fai l nfans denant la verja tal paor ai no l sia tr p de l arma Del c r li fos non de l arma e consentis m a celat dins sa chambra Que plus mi nafra l c r que c ps de verja car lo sieus s rvs lai ont ilh es non intra tots temps serai amb li is com charns et ongla e non creirai chastic d amic ni d oncle Anc la seror de mon oncle non am i plus ni tant per aquesta arma Qv aitant vesins com es lo dets de l ongla s a li is plagu s v lgra sser de sa chambra de mi p t far lamors qu ins el c r m intra mi lhs a son v l qu m f rts de fr vol verja Pu is florit la secha verja ni d En Adam m gron nebot ni oncle tant fina amors com cela qu el c r m intra non cug fos anc en c rs ni eis en arma ont qu ilh estei f rs en pla a o dins chambra mos c rs no s part de li is tant com ten l ongla Qu aissi s enpren e s enongla mons c rs en li is com l esc r a en la verja qu ilh m es de j i tors e palatz e chambra e non am tant fraire parent ni oncle qu en paradis n aur doble j i marma si ja nulhs m per ben amar lai intra Arnauts tramet sa chan on d ongla e d oncle a grat de li is que de sa verja larma son Desirat cui pr tz en chambra intra FIGURE 1 Ongle et oncle
22. rimitive root distinct from 2 and of the spinines which generalize quenines by Jacques Roubaud s erasing technique We then extend this representation to p recquines KEY WORDS Perecquine Primitive root Queneau Daniel permutation Quenine Sestina Spiral 1 L OULIPO LA PO SIE DES TROUBADOURS ET LES QUENINES Arnaut Daniel est un troubadour de la fin du XIT si cle Un de ses po mes c l bres ongle et oncle cf Figure 1 est une s rie de six strophes de six vers chacune Rou baud 1969 Chacun des mots la rime de la premi re strophe est reproduit dans les strophes suivantes dans un autre ordre Plus pr cis ment chaque passage d une strophe l autre est d termin de la m me fa on l aide de la spirale de la Figure 2 ILaboratoire J Kuntzmann 51 rue des Math matiques Universit de Grenoble UMR CNRS 5224 BP 53X 38041 Grenoble Jean Guillaume Dumas imag fr 10 J G DUMAS Sextine Ce v u dur qui dans le c ur m entre nul bec ne peut le d chirer ni ongle de lausengier qui m disant perd l me et ne l osant battre branche ou verge secr tement l o il n y a point d oncle j aurai ma joie en verger ou en chambre Quand j ai souvenir de la chambre o mon dam je sais que pas un n entre tant me sont durs plus que fr re ni oncle nul membre n ai qui ne tremble ni d ongle plus que ne fait l enfant devant la verge telle est ma peur de l avoir trop dans
23. tincts Nous prouvons ensuite la condition suffisante Prenons w le cardinal de la plus petite orbite des l ments de 1 n par n et supposons que l l ment u soit d ordre w Dans ce cas le fait qu il existe k tel que 2 u u 1 2 u implique donc que 1 2 1 car u est inversible Cela revient 2 1 et il y a deux Cas 1 Si 2 1 Alors w est plus grand que l ordre de 2 Donc w gt n et donc w n car la permutation est au plus d ordre n 2 Si 2 1 Alors a Soit l ordre de 2 est j 2n et donc 2 1 Ainsi 2 1 et donc wW nN b Soit l ordre de 2 est j n et n est impair Alors 2 1 1 ce qui prouve que n divise 2w Or n est impair donc le lemme de Gauf implique que n divise w L encore w n Ainsi nous pouvons d cider facilement si une quenine donn e existe ou non La Table 1 donne les 178 premi res quenines 1 2 3 5 6 9 11 14 18 23 26 29 30 33 35 39 41 50 51 53 65 69 74 81 83 86 89 90 95 98 99 105 113 119 131 134 135 146 155 158 173 174 179 183 186 189 191 194 209 210 221 230 231 233 239 243 245 251 254 261 270 273 278 281 293 299 303 306 309 323 326 329 330 338 350 354 359 371 375 378 386 393 398 410 411 413 414 419 426 429 431 438 441 443 453 470 473 483 491 495 509 515 519 530 531 543 545 554 558 561 575 585 593 606 611 614 615 618 629 638 639 641 645 650 651
24. tion nous tendons la caract risation du Th or me 2 toutes les racines primitives en notant n la permutation spirale de multiplicateur g TH OR ME 3 Soitn un entier tel que 2n 1 est premier et soitg lt n Soit Z 2n 1Z le corps 2n 1 l ments alors n g est d ordre n si et seulement si Soit g est d ordre 2n g est racine primitive dans Z 9n 17 Soit n est impair et g est d ordre n dans Z 9n 17 16 J G DUMAS La preuve est identique celle du Th or me 2 l exception de la condition gsn D MONSTRATION Supposons que g est d ordre j lt n Alors nous avons 62 9 g g g Nous avons donc deux cas 1 Si 02 9 g alors l orbite de g ne contient que j lt n l ments ce qui n est pas suffisant car n est suppos admissible 2 Dans l autre cas f g g Or 1 lt f x lt n par d finition Donc 1 lt 2n 1 g lt n ou encore n lt g C est l que la condition suppl mentaire est n cessaire Donc si n est admissible alors g est d ordre n ou 2n modulo 2n 1 Il ne nous reste plus qu exclure le cas o n 2p est pair et g est d ordre n modulo 2n 1 En effet dans ce cas g 1 2n 1 Il s en suit que wE kopno KAA a g 1 gg g Or nous avons vu que f g g gr ce la condition et par ailleurs g g impliquerait que l orbite de g ne contienne qu au plus p 3 lt n l ments Nous prouvons ensuite la
Download Pdf Manuals
Related Search