CHAPITRE II

16. — Généralisation du théorème de Fermât, Théorème d'Euler (^). — Soil n un entier quelconque, et a un entier premier avec n, on a :

a'-?W ^ I = o (mod. n).

En effet, soient

les entiers de la suite i, 2, ... n — i, premiers avec n. Considérons les entiers :

(2) aai, aaa, ... a^o(„).

Je dis que les entiers de la suite (2) sont, dans l'ensemble, congrus à ceux de la suite (i).

En effet si l'on considère les entiers

(3) o . a, I . a, 2a, ... {n — i)a ils sont congrus, dans l'ensemble, aux entiers

D'ailleurs ce sont les entiers premiers avec n, de la suite (3) qui sont congrus aux entiers premiers avec n de la suite (4). H en

(1) EuLER. — Petrop. Comm., nov. 8 (1760-61) p. 74 = Corn. Arith., I, p. 374.

résulte bien que les entiers (i) sont congrus, dans Tensemble, aux entiers (2).

On en déduit que le produit des entiers (i) est congru au produit des entiers (2J, c'est-à-dire que :

d'où, en divisant les deux membres par UiOCi ... «^(n) qui est premier à n

a?W = 1 (mod. n).

Ce théorème est bien une généralisation de celui de Fermât, car lorsque n est un nombre premier p, on a (p (/i) = /> — i .

17. — Sur les restes suivant un module quelconque n des puissances d'un entier a premier an.

Théorème. — Si l'on considère la suite :

a étant premier à un module n, les restes des termes de cette suite par n se reproduisent périodiquement. Le nombre des termes de la période est le plus petit entier positij e tel que a ^^ i {mod. n). On l'appelle l'exposant de a par rapport à n. C'est un diviseur de <p{n).

La démonstration est identique à celle donnée pour les modules premiers aux n"^ 2 et 3.

Exemple. — Soit n = 18 ç(n) ^ 6, a= I donne la période 1 appartient à l'exposant i

Quel que soit n, i appartient à l'exposant i et — i à l'exposant 2 (sauf si /i =: 2).

Mais le théorème du n" 4 ne se généralise pas. Lorsque le module nest pas premier une congruence de degré m peut avoir plus de m solutions.

6o THÉORIE DES NOMBRES

Par exemple la congruence

x^ -\- X — a ^ o (mod. 35) a quatre solutions :

Il en résulte que le raisonnement du n° 5 ne se généralise pas et que l'on ne peut pas de cette façon trouver les entiers qui appartiennent à un exposant donné. Nous allons procéder autrement.

18. Problème. — Etant donné un modale n trouver les entiers gui appartiennent^ relativement à ce modale, à texposant le plus élevé possible, et déterminer cet exposant. On sait que cet exposant ne peut dépasser o{n).

Lorsqu'il est égal à ç> (n) les entiers appartenant à cet exposant seront dits racines primitives de n. Nous distinguerons plusieurs cas suivant les valeurs de n.

Lorsque n est un nombre premier le problème est déjà résolu. Nous savons qu'il y a des racines primitives.

Cas où n est une puissance d'un nombre premier impair

Alors

o(n)=p='-'(/>-0- Lemme, h étant un entier quelconque, m un entier positif impair et a un entier positif, on a

(1 4- /im)"'*-' = 1 4- /im* (mod. m=' + ')-

C'est évident pour a = i. Supposons donc que c'est vrai pour une valeur de a et démontrons-le pour la valeur a + i, Par hypothèse :

(I H- Am)'»*-' := 1 + /im« + km''-^\

Elevons les deux membres à la puissance m, il vient

Transformons cette égalité en congruence (mod. m^ + 2) en négligeant les termes qui contiennent en facteur m* + 2. D'abord les

GÉNÉRALISATION POUR LES MODULES NON PREMIERS 6l

termes non écrits au second membre contiennent en facteur m^^ ; or 3a > a + 2 puisque t.

m est impair ; donc dans

or 3a > a + 2 puisque a > i. hnsuite — - — est entier, puisque

— m \nm -+- km }

il y a en facteur m^^+ ' ; or

On peut donc négliger tous ces termes et il reste

(i + /tm)"'* = 1 + hm^^' (mod. m' + '). <

Corollaire. — On a, dans les mêmes hypothèses (') sur h,m, ol;

(i -+- /tm)""^"' ^ 1 (mod. m*).

TiiÉORiiME. — Un entier a qui n'est pas racine primitive d'un nombre premier p ne test pas non plus de p'^.

En effet il existe un entier i, positif et plus petit que p — i tel que

a* = I + hp.

Elevons les deux membres à la puissance p*"', il vient :

a'>*-' = (i -^hpY""-'

c'est-à-dire, d'après le corollaire du lemme :

a'>*~' = 1 (mod./)*).

Donc a appartient, relativement au module p^. à un exposant inférieur a (p — i) p*~S donc a n'est pas racine primitive.

Examinons maintenant si, au contraire, une racine primitive de p est aussi racine primitive de />*, nous arriverons au théorème suivant :

Théorème. — Toute racine primitive g de p est oiussi racine primitive de p'^, sauf si gP — ^ — i est divisible par p^.

En effet soit e l'exposant de g par rapport à p^, on a

5f' ^ I (mod. p*)

(^) Cependant, dans ce corollaire, m peut être un entier quelconque, pair ou impair.

d'où

g' ^ 1 (mod. p)

donc e est un multiple de p — i.

Mais d'autre part e est un diviseur de rp (p^) = {p — i) p''—\ Donc e est de la forme

et, pour montrer que g est racine primitive de p^ il suffit de montrer que g^''" ^^i'^~^ — i, n'est pas divisible par p^. Or on a :

En élevant les deux membres à la puissance p^—^ il vient, d'après le lemme {p étant impair)

Or

P t)onc si g''~* — i n'est pas divisible par p^, l'entier A- n'est pas divisible par p, par suite g(p-^)p^~^ n'est pas congru à i (mod. p^), donc g est racine primitive de p^. Au contraire, si g''~^ — i est divisible parp^, g n'est pas racine primitive de p*.

Il est facile maintenant de trouver les racines primitives de p=f. Soit g une racine primitive de p. Elle est congrue (mod. p) àp=»— ' entiers incongrues (mod. p^~^), compris dans la formule

g-hhp (/i = o, 1, ...p'-*— i).

Cherchons ceux de ces entiers qui sont racines primitives de p«. Ce sont ceux qui correspondent aux valeurs de h telles que {9 + Ap)^"* — I ne soit pas divisible par p-. Développant (^g f- hpy~^ et négligeant les multiples dep-, on arrive à la condition :

gp-i — gP-^hp —1^0 (mod. p-).

Posant, comme plus haut

cette condition s'écrit

ou encore

h ^ kg (mod. p).

On voit donc qu'il faut laisser de côté les p^—^ valeurs de h qui sont congrues à kg (mod. p). Ainsi chaque racine primitive de p fournit/)*— I — p^—^ racines primitives de p^. En recommençant ce calcul pour chacune des ©(/) — i; racines primitives de p, on trouve en tout (p*~' — P^~') fip — i) c'est-à-dire 9[<p(p*)] racines primitives de p*.

Exemple p = 7. — Les racines primitives de 7 sont 3 et — a. Pour

g = 3, k= — - — = io4 = — 1 (mod. 7)

et l'on a Pour

et l'on a

kg ^ — 3 (mod. 7).

g = — 2, k= ^ =9=2 (mod. 7)

kg ^ 5 (mod. 7).

Donc les racines primitives de 7* sont comprises dans les formules^

en laissant de côté les valeurs h = /i, 11, 18, ... dans la première formule et les valeurs h = 3, 10, 17, ... dans la seconde.

19. Résolution du problème du n^ 18 Jdans le cas où n est une puissance de 2. — Nous distinguerons les cas :

I** Soit d'abord n = li. On voit que i appartient à l'exposant i et — là l'exposant 2. D'ailleurs (p(4) = 2. 11 y a donc une racine primitive qui est — i. On voit qu'il y a <p((p(4)) racines primitives.

64 THÉORIE DES .NOJKîRES

2° Soit maintenant

Théorème. — Pour tout nombre impair a, on a

^a"— 2 ^ j (mod. 2"').

En effet c'est vrai pour m = 3. Car soit a = 2 a' + i. On a

(2a' -hiy = lia'{a' -h i)+ i.

L'un des deux entiers a', a' -f- i est pair, etc.

Démontrons donc que si c'est vrai pour une valeur m, c'est vrai pour la valeur m -\- i. Or;

Le facteur a^»"*"^ + i est pair ; et le facteur a^"'"'^ — i est divisible par 2"' par hypothèse, donc a""'~' est divisible par 2"*^'.

Conséquence. — L'exposant le plus haut possible ne peut dépasser 2"'""^, Comme d'ailleurs (p(2"') = 42"'*' on en conclut qu'il n'y a pas de racine primitive.

Démontrons maintenant qu'il y a effectivement des entiers appartenant à l'exposant 2"'~^. Remarquons d'abord que les entiers impairs sont de l'une des quatre formes

± I -h Sh, ±3 -\-8h.

Théorème. — Les entiers de la forme rh 3 h- 8A appartiennent à l'exposant 2"'-^, les entiers de la forme d= i 4- 8^ appartiennent à des exposants inférieurs.

Pour le démontrer il suffit de démontrer que

(5) !(± 3 4- S/i)'"""" ^ 1 (mod. a"")

mais que

(dz I -h S/i)'""' = I (mod. 2'").

Or dans l'égalité

où a est supposé impair et [^ >> i, le facteur a*' ~ + i est divisible par 2 mais non par 4 ; donc a^^ — i contient le facteur 2, exactement une fois de plus que a^' ~' — i. Donc pour démon-

trer les relations (5) et (6) il suffit de démontrer celles qu'on obtient en remplaçant m par m — i, puis celles obtenues en remplaçant m — I par m — 2 et ainsi de suite. Or pour m = 4 elles sont évidentes.

En résumé, pour le module 2'" (m > 2) l'exposant le plus élevé possible est 2"*"* ou - 9(2"') ; il y a 2"'~^ ou fp['p{2"')] entiers appartenant à cet exposant.

20. — Reste à résoudre le problème du n" 18 dans le cas où n contient des facteurs premiers différents.

Théorème. — Soient rii, rii, ... des modules premiers entre eux deux à deux. Si un entier a appartient à l'exposant e^^ par rapport au module n^, à l'exposant e-i par rapport au module n^, ... cet entier a appartient j par rapport au module n^n^ ... à un exposant éfjalau plus petit commun multiple de e^^ e^, ...

En effet, l'exposant ^ de a par rapport à n^Ui ... est le plus petit entier positif satisfaisant à la congruence

a" ^ 1 (mod. n^n-i ...)

Puisque n,, n^, ... sont premiers entre eux deux à deux cette congruence est équivalente à l'ensemble des suivantes :

a* ^ 1 (mod. «i), a" ^ 1 (mod. n^), ...

La première exprime que e est un multiple de e^, la seconde que e est un multiple de ei, etc. Le plus petit entier positif satisfaisant à ces conditions est bien le plus petit commun multiple de <?i, e-u ...

Conséquence. — Pour trouver un entier ayant par rapport à niUi ... l'exposant le plus élevé possible, il faut chercher un entier rti ayant par rapport à n^ l'exposant le plus élevé possible e^, un entier a^ ayant par rapport à n^ l'exposant le plus élevé possible e-i, ..., puis déterminer un entier a tel que

a ^ Oj (mod. «1) a ^ a^, (mod. «2) ••

ce qui est possible (n** 1). L'entier a ainsi déterminé aura par rapport à /iino ... un exposant égal au plus petit commun mulliple de ^1, e^, ...

Caben. — Théorie des nombres, II. 5

66 THÉORIE DES NOMBUES

En prenant pour «i toutes les valeurs possibles différentes deux à deux (mod. n,), pour a^ toutes les valeurs possibles (différentes deux à deux (mod. n^), ... on aura pour a toutes les valeurs possibles différentes deux à deux (mod. /I1/22 ...). S'il y a Vi valeurs pour «1, Vi pour ai, ... il y aura "jfjo .•• valeurs pour a.

Cas particulier. - — Soit n décomposé en facteurs premiers

Le plus haut exposant possible par rapport à 2'" est X(2*"), en posant

si m <^ 2 et

si m > 2 ; il y a en tout cas fp[o{-2"')] entiers incongrus (mod. 2'") appartenant à cet exposant.

Le plus. haut exposant possible pour p* est (p (p^), il y a ^ [<p(p*)] entiers incongrus (mod. /)*) appartenant à cet exposant. De môme pour //P, ...

Donc le plus haut exposant possible pour n est

et le nombre des entiers incongrus (mod. n) appartenant à cet exposant est

Condition pour que n ait des racines primitives. — Il faut et il suffit que

• ^lx{^'"h ?(/>*), ?(7^). .-] = ?(«) = ?(2'")î(p') ?(/)••• Pour cela il faut et il suffit d'abord que

c'est-à-dire que m <^ 2 ; ensuite que

soient premiers entre eux deux à deux. Mais ç)(a) est toujours pair sauf si a = 2. Donc, en définitive, les seuls entiers ayant des ra-

-cines primitives sont les entiers de la forme 2'" (m <C 3), /)^ et ip^. En tout cas, l'exposant maximum que nous poserons égal à

X(/i) est