**TI82** TxtView file generated by CalcText - Kouri9 * arithJ* ( ÿarithJARITHMETIQUE ------------ Relation DIVISE : ^^^^^^^^^^^^^^^ - a "divise" b <=> b=ka - a/b et b/c <=> a/c - si (a,b) /= (0,0), a/b <=> |a| =< |b| - a/b et a/c => a/bx+cy PGCD : ^^^^ - si d=a/\b et (a,b)/=(0,0) alors : - d/a et d/b - algo itératif donnant d : - DEBUT | c := a mod b | tant que c/=0 faire | | a:=b | | b:=c | | c:=a mod b | fin tant que | pgcd:=b FIN - algo recurif donnant d : - DEBUT | Si a mod b = 0 alors x := b | sinon x:= pgcd(b,a mod b) | Fin si FIN BEZOUT : ^^^^^^ - identite : d=a/\b => il existe (u,v):Z², au+bv=d - theoreme : a/\b=1 <=> il existe (u,v):Z², au+bv=1 THEOREME DE GAUSS : ^^^^^^^^^^^^^^^^^ - a/bc et a/\b=1 => a/c - pour le demontrer : transformer les hypotheses et multiplier au+bv=1 par c. NOMBRES PREMIERS : ^^^^^^^^^^^^^^^^ - p est premier ssi p>1 et p n'admet comme diviseurs que 1 et p. - raréfaction des nombres premiers : - PIE(x) : nombre d'entiers premiers inférieurs ou égal a x - si x grand, PIE(x)=x/(ln(x)) - Decomposition primaire : - n peut s'ecrire comme un produit de nombres premiers CONGRUENCES : ^^^^^^^^^^^ - a==b[n] <=> a-b : nZ <=> n/a-b <=> a mod n=b mod n - a==b[n] et c==d[n] => ac==bd[n] => a(+-)c==b(+-)d[n] - a==b[n] => ka==kb[n] ALGO D'EUCLIDE : ^^^^^^^^^^^^^^ - tableau : | u | v | q | r | |---|---|---|---| | 1 | 0 | / | a | | 0 | 1 | q1| b | ALGO D'EXPONENTIATION GAUCHE-DROITE : ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - a^e avec e en base 2 : e=1k(j-1)k(j-2)....k(1)k(0) k=alpha - Algo pour calculer a^e : - R<-a Pour i variant de j-1 à 0 | R<-R.R | Si k(i)=1 alors R<-R.a | Fin Si Fin Pour Afficher R - Algo pour calculer a^e mod n : - R<-a mod n, A<- a mod n Pour i variant de j-1 à 0 | R<-(R.R) mod n | Si k(i)=1 alors R<-(R.a) mod n | Fin Si Fin Pour Afficher R INVERSE MULTIPLICATIF : ^^^^^^^^^^^^^^^^^^^^^ - u est un inverse multiplicatif de a mod n ssi : (au) mod n=1 ou au==1[n] - u est l'inverse multiplicatif de a mod n ssi : (au) mod n=1 et u : {1,2,...,n-1} FONCTION INDICATRICE D'EULER : ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - PHI(n) est le nombre de solutions de : - x : {1,2,...,n} et - x/\n=1 - ou PHI(n) est le nombre d'entiers inférieur et premier a n - si p premier, PHI(p)=p-1 - si a/\b=1, PHI(ab)=PHI(a).PHI(b) - si n=q1^(a1).q2^(a2)...qk^(ak) alors PHI(N)=(q1^(a1)-q1^(a1-1)).(q2^(a2)-q2^(a2-1))...(qk^(ak)-qk^(ak-1)) THEOREME D'EULER : ^^^^^^^^^^^^^^^^ - n:N* et a :Z, a/\n=1 => a^(PHI(n))==1[n] PETIT THEOREME DE FERMAT : ^^^^^^^^^^^^^^^^^^^^^^^^ - p premier, a/\p=1 => a^(p-1)==1[p] ÿ%