Cas particulier. Quel est le nombre de solutions de

la congruence

x'1 — 1 = 0 ( mod n).

Remarquons que le nombre i est reste quadratique de loui nombre premier impair, el qu'il est congru à i (mod ■>. I, (mod j el mod 8 ). ( )n a doue les résultats suivants :

Si n est impair, soi i a le nombre de ses facteurs premiers distincts, la congruence a ■>,'-'■ soin lions ;

Si // est pair, soit encore u. le nombre de ses facteurs premiers impairs ( u. pouvanl être =o) :

Si n est simplement pair, la congruence a ■>.''■ solutions;

Si n est divisible par j et non par 8, la congruence a ■>.',+l sol n lions ;

Si n est divisible par % ou une puissance supérieure de ■> , la congruence a ?.v-+- sol niions.

171. Comme application des résultats précédents, donnons une généralisation du théorème de Wilson :

Généralisation du théorème de Wilson. Le produit

a, y-, . . . y-z,(,i) des nombres positifs, pins petits que n et premiers avec lui, est congru à i ou à — i(mod/>). Ce produit est. congru <i — -i , si n est une puissance d'un nombre premier impair, OU le double d'une telle puissance, oit si n est égala \ ■ Ce produit est congru à -\-i dans tous les autres cas.

En effet, soil a/, l'un des nombres positifs, plus petits que n el

premiers avec lui. Le no m lue y./, étant premier avec n, possède un

inverse (mod/i) (n° 105), c'est-à-dire qu'il existe un nombre -//,•,

tel que

a/, a/,- 'i (mod/i)

el ce n oui lue y./, ' est évidemment lui-même pic m in- avec /i, el peut d'ailleurs être supposé positif et plus petil que //.

Si y./,' ei y./t sont différents, nous dirons que y.u el '//, sonl associés du premier genre.

Mais il peut arriver que v./, el y./, soient égaux. Pour cela, il faul

et il suffit tpie

-/; 1 1 mod n i,

1 0 | (Il VI'. III. DES CONGRUENI I 5.

i est-à-dire que x/ soil racine de la congruence

i j i i i (modn),

Maintenant, remarquons que si un nombre 'J i, esl racine de celte

congruence, le nbre // y./, i lequel esl premier avec /'. positif

el plus pel il que // » l'esl aussi .

Les deux nombres -/.•, el // x* ne -uni d'ailleurs pas égaux, car pour que cela arrn e il faudrai i que

ce qui n'est pas, puisque a/, esl premier avec // .

Enfin ces deux nombres ?./, ri // y/, oui un produit congru à

■ - 1 ; car

■/,<// -a . i — -j-'I — i (mod n).

ippelons ces deux nombres associés du seront! genre. Ainsi les nombres a se répari isseni en couples : les couples < J ";i ^ -

SOciés du premier genre dont le pl'oi I u i l esl cou -ru ;'i I . el les COUples

d'associés du second genre donl le produit esl congru a i.

Le produil de tous les nombres a esl donc congru àl i \'-'\ p. désignant le nombre de couples d'associés du second genre, c'està-dire la moitié ilu nombre des racines de la congruence i fi).

Pour terminer la question, il ne reste donc qu'à déterminer ce nombre «le racines ou, plus simplement, à voir si la moitié p. de ce nombre esl paire ou impaire.

Or, si Ton se reporie aux résultats du n" 170. on voit que ce nombre n'esl impair que si // esl une puissance d un nombre premier impair, OU le double d'une telle puissance, ou .-i // j.

Donc, dans ces cas seulement, le produil en question est congru i i (mod n). Dans les autres cas, il esl congru à i .

Remarquons que, si // esl un nombre premier, ceci donne une démonstration du i héorème de \\ il son, différente de celle donnée au n" 133.

\~"2. Restes, par rapport à un module non premier n . des puissances successives il un nombre x, premier avec le module.

DES CONGRUENCES v NODULES non PREMIERS. 100

Soil v. un nombre, premier avec un module //. ( >n < 1 1 \ i s< ■ par n les puissances successives

cl l'on obtient des restes

Nous nous proposons de démontrer <|ue :

i" Les puissances successives de a forment une suite périodique; deux puissances de même rang dans deux périodes étant congrues i mod/?); par suite, les restes forment aussi une suite périodique ; deux restes de même rang dans deux périodes étant égaux ;

■>. ' Soit /.' le nombre de termes de (a période, on a

2/, i ( inoil i) i et /•/ = i ; 3° /, est un diviseur de cs(/2 .

( >n voit que ces théorèmes sont des généralisations de ceu\ démontrés au n" 149 pour les modules premiers.

Ces théorèmes du n" li9 ont été déduits de l'étude de la congruence binôme, qui a été déduite elle-même de la théorie générale des congruences à module premier. Comme il n'existe pas de théorie analogue pour les modules non premiers , nous allons traiter la question des restes, directement. D'ailleurs la méthode que nous allons suivre s'appliquerait, sans aucun changement, aux modules premiers.

I. Les restes r, , /"2l . • • sont positifs et plus petits (pie n. De plus, il> sont premiers avec n, puisqu'ils sont congrus I mod n > .iu\ puissances successives de a qui sont premières avec //.

Il résulte de là que le nombre de ces restes est limité et al leinl . au pi u>. »(j2 I ; par Suite, il y a n ('cessa ire me ni des restes qui se reproduisent .

II. // y a dans la suite i (3) des restes égaux à i . - En effet, nous avons N,| qu'il \ a des restes qui se reproduisent.

Soit

/'«i = rn, • ni ni I,

106 i II kP. III. Kl S « "\'.l!l BN( I 5.

I ' 'I oll

'u"< y.1"' mod n .

< >n en déduil

y»' -"• : l i mod " .

il on

III. Suit n, le premier reste de In suite [3) qui soit égala \ De /"i à ii, les restes sont différents. Car &i l'on avail

rm — - /•„,- (m el /// /. ».

ou en déduirail . comme plus baul .

de sorte que //, ne sérail pas le premier reste de la suite [3 i qui sérail congru à i .

I\ . Deux restes <l<>ni 1rs rangs, dans l<i suite \ |3 . diffèrent de h sont égaux. En effel ,

Mats, puisque //, i . on a

a* i i mod n .

Donc

a'" '■ y."1 | mod n i.

I )onc

En particulier, 1rs restes qui sonl égaux à i sont les restes r*,

l'il,- /':i/.

Il reste à démontrer que /. est un diviseur de es n . Or, nous venons de voir que les restes qui sont égaux à i sonl ceux donl l'indice esl un multiple de /. ; d'autre pari, d'après le théorème • I Euler, /■ „ esl égal à i .

Donc ©( a i c>i un multiple de /. ' i.

l ii celte façon, | 'démontrer que /. esl un diviseur de T " ■■ nous sup

posons établi le théorème d Euler. On peut, au contraire, démontrer que /. esl un diviseur de n sans s'appuyer sur le théorème d'Euler, el <t\ déduire ce dernier i Iiii.i ème.

En effet, les restes r„ r r, sonl tous différents. Si ces restes constituenl