{VERSION 6 0 "IBM INTEL LINUX" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 1 12 255 0 0 1 0 1 0 2 1 2 0 0 0 1 }{CSTYLE "" -1 256 "" 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 0 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "_pstyle 4" -1 203 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 }0 0 0 -1 -1 -1 1 0 1 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 49 "OPA 2005 TP1\nNombres pre miers et sommes de carr\351s" }}{PARA 18 "" 0 "" {TEXT 256 19 "El\351m ents de corrig\351" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restar t:" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Question 1" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "znorm:=proc(z);\n RETURN(z*conjuga te(z));\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "znorm(1+I) ; znorm(1-I);" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Question 2" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 119 "zdiv:=proc(a,b) local x,y,q ,r;\n x:=Re(a/b);\n y:=Im(a/b);\n q:=round(x)+round(y)*I;\n r:=a-q *b;\n RETURN([q,r]); \nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "res:=zdiv(7+I,4+3*I); (4+3*I)*res[1]+res[2];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "res:=zdiv(4+3*I,1+I); (1+I)*res[1]+res[2]; " }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Question 3" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 387 "zgcd:=proc(a,b) local za,zb,t;\n za:=a; \n zb:=b;\n t:=zdiv(za,zb);\n while (t[2]<>0) do\n za:=zb;\n \+ zb:=t[2];\n t:=zdiv(za,zb);\n od;\n# le pgcd est stock\351 dans zb . On va le normaliser avant de renvoyer le r\351sultat,\n# i.e. renvoy er le repr\351sentant modulo les inversibles qui est dans le premier q uadrant.\n while not(Re(zb)>0 and Im(zb)>=0) do\n zb:=zb*I;\n od; \n RETURN(zb);\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "zg cd(6,9);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "zgcd(7+I,4+3*I) ; zgcd(4+3*I,1+I);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "a:=(1 +I)*(4+3*I); b:=(1+I)*(7+I); zgcd(a,b);" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Question 4" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "i sprime(3); isprime(-3); isprime(6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 340 "\340 la diff\351rence de isprime() nous ne normaliserons pas l es premiers ; de ce fait iszprime(p) renvoi vrai si (p) est un ideal p remier. On utilise alors le crit\350re de primalit\351 dans Z[i] vu en cours.\nLes premiers normalis\351s (i.e. dans le premier quadrant) so nt ceux de normes premi\350res ou les entiers naturels premiers congru s \340 -1 modulo 4. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 262 "is zprime:=proc(p) local zp;\n zp:=p; while not(Re(zp)>0 and Im(zp)>=0) \+ do\n zp:=zp*I;\n od;\n if not(Im(zp)=0) then RETURN(isprime(znorm (zp)))\n else\n if isprime(zp) and mods(zp,4)=-1\n then RET URN(true)\n else RETURN(false);\n fi;\n fi;\nend: " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "iszprime(-3);iszprime(3*I); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "Le r\351sultat est coh\351ren t car iszprime n'est pas normalis\351, \340 la diff\351rence de isprim e." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "iszprime(1+I); iszpri me(1-I); iszprime(7+I); iszprime(4+3*I);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 216 "Pour la factorisation des entiers de Gauss de \253petite norme\273, nous aurons besoin des nombres premiers normalis\351s non \+ entiers (i.e., ne provenant pas de Z)\n de norme <= 25. Nous donnons a ussi la norme de ces premiers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 134 "for a from 1 to 5 do\n for b from 1 to 5 do\n z:=a+b*I;\n if (znorm(z)<=25) and iszprime(z) then print(z, znorm(z)); fi;\n \+ od:\nod;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "znorm(7+I);" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "On teste alors la divisibilit\351 par des premiers de norme divisant 50 :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "zdiv(7+I,1+I);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "On poursuit avec 4-3I de norme 50/2=25 :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "zdiv(4-3*I,1+2*I);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "zdiv(4-3*I,2+I);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 30 "Et 1-2I=-I(2+I) ; finalement :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "-I*(1+I)*(2+I)^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "znorm(4+3*I);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "zdiv(4+3*I,1+2*I);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "-I*(1+2*I)^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "znorm( 5+3*I);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "zdiv(5+3*I,1+I); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "-I*(1+I)*(1+4*I);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "znorm(7+2*I);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "Or 53 est premier !" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "iszprime(7+2*I);" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 10 "Question 5" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "randprime:=proc(n); \n RETURN(prevprime(RandomTools[Generate](intege r(range=5..n+1)))); \nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 323 "c= a^k est d'ordre 4 si et seulement si c^2=-1 modulo p ; on fait varier \+ al\351atoirement le nombre premier p et le a et note le nombre de cas \+ favorables ; \nla proc\351dure qui suit renvoit, apr\350s nba*nbp tent atives (nbp est le nombre de tirages de p et, pour un p donn\351, nba le nombre de tirages de a), la probabilit\351 de succ\350s." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 540 "teststrategie:=proc(nbp,nba ) local i,j,k,p,a,c,nb;\n nb:=0;\n for i from 1 to nbp\n do\n p: =randprime(1000);\n while ((p-1) mod 4 <>0)\n do\n p:=randp rime(1000);\n od;\n k:=(p-1)/4;\n for j from 1 to nba\n do \n a:=RandomTools[Generate](integer(range=1..p-1));\n # note r qu'il vaudrait mieux prendre a:=RandomTools[Generate](integer(range= 2..p-2));\n # car les classes de -1 et 1 ne sont pas d'ordre 4 ! \+ \n c:=a&^k mod p;\n if mods(c&^2,p)=-1 then nb:=nb+1; fi;\n \+ od;\n od;\n print(nb/(nba*nbp));\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "teststrategie(1000,1); teststrategie(100,10);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "On obtient un r\351sultat tr\350s \+ proche de 1/2." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Question 6" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "for i from 1 to 10 do tests trategie(1,100); od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 101 "Pour ces dix choix al\351atoires de p, la probabilit\351 (\340 p fix\351) d'ab tenir un \253bon\273 a est proche de 1/2." }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 10 "Question 7" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 358 "ordre4:=proc(p) local k,a,c;\n if not(isprime(p) and ((p-1) mod \+ 4=0))\n then RETURN(FAIL);\n else\n k:=(p-1)/4;\n a:=R andomTools[Generate](integer(range=2..p-2));\n c:=mods(a&^k,p);\n while not(mods(c^2,p)=-1)\n do\n a:=RandomTools[Gene rate](integer(range=2..p-2));\n c:=mods(a&^k,p);\n od;\n \+ RETURN(c);\n fi;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ordre4(13);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ordre4(9 97);" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Question 9" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 432 "DeuxCarres:=proc(p) local a,b,c,d; \n if (not(isprime(p)))\n then error \"Le nombre %1 n'est pas prem ier\",p;\n else\n if (p mod 4 <>1)\n then error \"Le no mbre premier %1 n'est pas de la forme 4k+1\",p; \n else\n \+ c:=ordre4(p);\n d:=zgcd(p,I-c);\n a:=Re(d);\n \+ b:=Im(d);\n RETURN([a,b,a^2+b^2]);\n# la derni\350re c omposante est l\340 uniquement pour v\351rification\n fi;\n fi; \nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "DeuxCarres(2); De uxCarres(9); DeuxCarres(997); DeuxCarres(13);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "DeuxCarres(1000117);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 28 "DeuxCarres(281474976710677);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}}{PARA 203 "" 0 "" {TEXT -1 0 "" }}}{MARK "1 0 0" 8 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }