Notions et rappels d’Arithmétique
Rappels
Si a1 =k1 [n] et a2 =k2 [n]
alors a1 + a2 = (k1 + k1 )[n]
a1 * a2 =(k1 * k1 )[n]
1. Algorithme d’Euclide
Calcul du PGCD de 2 nombres
On suppose que r0 > r1
PGCD(r0 , r1 ) = PGCD(r0 - r1 , r1 ) = PGCD(r0 - 2r1 , r1 )= …= PGCD(r0 – mr1 , r1 ) , tant que r0 – mr1 >0
= PGCD(r0 mod(r1), r1 )
Exemple:
PGCD(84,30)= PGCD((84-30),30)= PGCD(54,30)= PGCD(24,30)= PGCD(30,24)=
PGCD(24,6)=6
Sinon on décompose: 84=2*30+24
30=1*24+6
24=4*6 +0 donc PGCD =6
PGCD(973,301)
973=3*301+70
301=4*70+21
70=3*21+7
21=3*7+0 donc PGCD =7
2. Algorithme d’Euclide Etendu
Extension de l’algorithme d’Euclide, peut être utilisé pour calculer l’inverse d’un nombre modulo [ ]
Si on peut écrire que PGCD(r0 , r1 ) = s* r0 + t* r1 , avec r0 > r1
r1-1 existe si PGCD(r0 , r1 ) = 1 [r0]
donc = s* r0 + t* r1 = 1 [r0]
t* r1 = 1 [r0] , car s* r0 = 0 [r0]
on peut conclure que t est l’inverse de r1 [r0]
Exemple :
r0 =973 et r1 =301, on cherche l’inverse de 301 [973]
973= 3*301 + 70 70= r0 -3 r1
301 = 4*70 +21 21=301-4*70= r1 -4(r0 -3r1)= -4r0 +13 r1
70=3*21 + 7 7=70-3*21= (r0 -3r1) -3(-4r0 +13 r1)=13r0 -42 r1
21=3*7 + 0
PGCD =7, donc l’inverse de 301 [973] n’existe pas.
12-1 [67] = ?
On a donc : r0 =67 et r1 =12
67 = 5 * 12+ 7 7= 67 – 5 *67 = r0 – 5 r1
12 = 7 + 5 5= 12 * 7 = r1 –( r0 – 5 r1) = 6 r1 – r0
7=5+2 2= 7 – 5 = …= 2 r0 – 11 r1
5=2*2+1 1 = 5- 2 *2 = … =28r1 – 5 r0
2 = 2* 1 + 0
28r1 – 5 r0 =1 [67] , donc 28 = 12-1 [67]
On peut vérifier que 28*12 = 336 = 5 * 67 +1 = 1 [67]
3. Théorème de Fermat
Si a est un entier non divisible par p, ou p est un nombre premier
ap = a [p] , on peut aussi écrire que ap-1 = 1 [p]
4. Fonction indicatrice d’Euler
Elle est notée ɸ(m), elle donne le nombre d’entiers premiers de m
Si
m = p1 e1 . p2 e2 ….. pn en ou les pi sont des nombres premiers
ɸ(m) = ∏ (pi ei - pi ei-1 ) pour i=1, …, n
exemples
m=6, 6= 31 * 21 donc ɸ(m) = (31 – 30 ) (21 – 20 ) = (3-1)(2-1)=2
nous avons 2 nombres premiers à 6 : {1 , 5}
m=5 5=51 , ɸ(m) = 51 – 50 =5-1=4 , {1 , 2, 3, 4 }
m=240 240=16 *15 = 24 *3 * 5, ɸ(m) = (24 – 23 ) (31 – 30 ) (51 – 50 ) = (16-8) (2) (4) 8 .2 .4 =
64, il y a donc 64 nombres qui sont premiers avec 240.
5. Théoreme d’Euler
Si a et m sont des entiers et PGCD(a,m) = 1 , c-a-d a et m sont premiers
alors a ɸ(m) = 1 [m]
Exemple ;
a=5 et m=12, on vérifie que PGCD(5,12) = 1
12= 3 * 22 , ɸ(12) = (3-1) ( 4 – 2) = 4
Donc 54 = 1 [12]
