Les principaux théorèmes

Nombres premiers

Petit théorème de Fermat

Indicatrice d'Euler "Ø"

Déterminez le nombre d'entier k_i/k_i<P et PGCD (k_i, P)=1

Exemple:

Ø(17)=16 ; Ø(12)=4

Théorème de Gauss

Si a>0 et p est premier (avec PGCD(a,b)=1) alors a^c(p)=1[p]

Identité de Bézout

Si PGCD(a,b)=1 alors il existe M, M appartenant à Z* tel que Ma+Nb=1 ; (Ma=1[b] ou Nb=1[a])

Corps Z/PZ

Si p est premier alors (Z/PZ,+,x) est un corps commutatif.. En particulier tout élément admet un inverse.

Résidus quadratiques

a est un "résidus quadratique modulo p" si:

Exemple:

Montrez que X²=2[3] n'a pas de solution ("2" est-il résidu quadratique de Z/3Z)
Z/3Z = {0, 1, 2} = {0, 1, -1}
0² = 0[3]
1² = 1[3]
2² = 1[3]
X² = 2[3] n'a pas de solution.

Théorème des restes Chinois

Grand théorème de Fermat

Si N est supérieur ou égal à 3, il b'existe pas (x, y, z) appartenant à Z/ x^N+y^N=z^N

Nombre de diviseur d'un entier N

Si N=P₁^k₁.P₂^k₂....P₅^k₅ où les Pi sont premier, alors le nombre de division de N et D(N)=(1+k₁)(1+k₂)...(1+k₅)

Exemple:

Déterminez le nombre de diviseur de (391), (72), (101)
-394 = 17¹x23¹ ↔ D(391)=(1+(1))(1+(1))=4
Liste {1, 17, 23, 391}

Nombres premiers

On montre qu'il existe une infinité de nombre premier, l'ordre de succession des nombres premiers n'obéit à aucun reste commun, cependant on peut "cibler" des familles infinies de nombres premier à partir de certaines équations. C'est le cas par exemple des nombres de Mersenne et des nombres de Fermat.

Nombres premiers de Mersenne et de Fermat

Nombre de Mersenne

Ce sont les nombres de la forme N_Me(P)=2^P-1 avec P premier.

Exemple:

P=2 ; N_Me(2)=3
P=3 ; N_Me(3)=7
P=5 ; N_Me(5)=31
P=7 ; N_Me(7)=127
P=17 ; N_Me(17)=131071

Nombres de Fermat

Ce sont des nombres de la forme N_Fe(N)=(2^2N+1-1)/(2^2N-1) avec n appartenant à N.

Recherche de nombres premiers

L'identification de Bézout nous rappelle que si deux nombres a et b sont premier entre eux,n il existe deux entiers relatifs M et N tels que aM+bM=1 (E)
L'algorithme d'Euclide nous permet de calculer M et N en faisant des divisions successives.

Exemple:

Supposons a<b, effectuons la division de b par a b=aq+r=aq₁+r₁, effectuons la division de a par ₁ (car a>r₁)

Exercice:

2632 et 29 sont premier entre eux, trouvons M et N tel que 2632(M)+29(N)=1
2632 = 90.29+22
29 = 1.22+7
22 = 3.7+1
1 = (2632-90.29) - [29-22]
1 = (2632-90.29) - 3[29-(2632-90.29)]
1 = 2632(1+3)+29(-90-30-270)
1 = 2632(4) + 29(-363)

Même question pour:
a = 1631 et b = 64
a = 3250 et b = 103