Cas particulier, — Quel est le nombre de solutions de

la congruence

x^ — ii = o (modn).

Remarquons que le nombre i esl reste quadratique de tout nombre premier impair, et qu'il esl congru à i (mod 2), (mod 4) et (mod 8). On a donc les résultats suivants :

Si n est impair y soit (jl le nombre de ses facteurs premiers distincts, la congruence a 2i* solutions;

Si n est pair ^ soit encore u le nombre de ses facteurs premiers impairs (jx pouvant être =0) :

Si n est simplement pair, la congruence a 7.^ solutions;

Si n est divisible par 4 et non par 8, la congruence a i^"^^ solutions;

Si n est divisible par 8 ou une puissance supérieure de •>., la congruence a 1'^'^^ solutions.

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 Wjlson. - Le produit a, a2 . . . oL^(n) des nombres positifs, plus petits que n et premiers avec lui, est congru à -|-i ou à — i (mod Ai). Ce produit est congru à — ijsi n est une puissance d'un nombre premier impair, ou le double d^une telle puissance, ou si n est égal à 4- Ce produit est congru à -i-i dans tous les autres cas.

En effet, soit aA l'un des nombres positifs, plus petits que n et premiers avec lui. Le nombre a^^ étant premier avec n, possède un inverse (mod /i) (n** lOo), c'est-à-dire qu'il existe un nombre a^v',

tel que

aiitXk'^i (modn)

et ce nombre a^'Cst évidemment lui-même premier avec /<, et peut d'ailleurs être supposé positif et plus petit que n.

Si OL/^ et oLff sont différents, nous dirons que a^ et a^' sont associés du premier genre.

Mais il peut arriver que a^ et a^' soient égaux. Pour cela, il faut

et il suffit que

il^ï (mod/i),

lOiJ cil A p. III. - DES CONGHUËNGES.

c'esl-à-dire que ola soil racine de k congruence

Ma in tenant, reinarr|uoni* que si un nombre a^ es L racine de celle coBgriience, ie nombre n --a^{ lequel est premier avec /*, posilif et plus petit que n) Test aussi.

Les deux nombres 'x^ et n —^k ne sont d^ailleurs pas êgauii, car |JOur que cela arrive il faudrait ï|ue

ce qui n*e$t pas, puisque ajt est premier avec n*

Enfin ces deux nombres ka et /î — ak ont un produit congru h

-\\ car

ajî ( /i -- mi, ) -' ^ aj -- ^ I (moà n )-

Appelons ces deux nombres associés du second genre.

Ainsi les nombres a se répartissent en couples : les couplet d'associés du premier genre doolle produit est congru k t , et les couples d\issociés du second genre dont le produit est congru à — ^i.

Le produit de tous les nombres ot est doue congru à ^ ^t)**, jt désignant le nombre de couples d'associés du second genre, c*esiii-dire la moitié du nombre des racines de la congrue net (ii)*

l*our terminer la question^ il ne reste donc qu'à dt'^îermîner ce nombre de racines ou, plus simplement^ avoir si la moitié p, de ce nombre est paire ou impaire.

Or, si Ton se reporte aux résultats du n" 170, on voit que et* nombre n*est impair que ^t n est une puissance d'un nombre premier impair, ou le double d'une telle puissance, on si n ^^ 4* Donc, dans ces cas senlement, le produit en question est congru k -^ X (mod n). Dans les autres cas, il est congru à -i-K

Remarquons que, si n est un nombre premier, ceci donne tttie flémonstraHon do théorème de Wilson^ dUTérenle de celle donaée

au n'

172. fîesteê^ par rapport à un module non premier n, des^ /ftttssances successives d'un nombre a, premier at^ec le module*

DES GONGRUENCBS A MODULES NON PREMIERS. lo5

Soit a un nombre, premier avec un module n. On divise par n les puissances successives

et l'on obtient des restes

(4^) ri, r,, ..., a, r^^i,

Nous nous proposons de démontrer que :

1° Les puissances successives de ol forment une suite périodique; deux puissances de même rang dans deux périodes étant congrues (mod/i); par suite, /es restes forment aussi une suite périodique; deux restes de même rang dans deux périodes étant égaux;

9r Soit k le nombre de termes de la période y on a

ak'^~i (mod/i) et r*^— i; 3** A* est un diviseur de o{n).

On voit que ces théorèmes sont des généralisations de ceux démontrés au n° 149 pour les modules premiers.

Ces théorèmes du n" 149 ont été déduits de Té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 Tj, Tj, . . . sont positifs et plus petits que /i. De plus, ils sont premiers avec n^ puisqu'ils sont congrus (mod n) aux puissances successives de a qui sont premières avec n.

Il résulte de là que le nombre de ces restes est limité et atteint, au plus, ç(/i); par suite, ilya nécessairement des restes qui se reproduisent.

II. Ilya dans la suite (43) des restes égaux à i . — En effet, nous avons vu qu'il y a des restes qui se reproduisent.

Soit

rm — rm' (m>m'),

io6

CHAP- nu — DES CON6RUEITCE5,

tl'oii

On en déduit

( raoJ n i

d'où

ï mofl n ),

m. Soiirf, ie premier resic th^ la siuie (43) qui soil égal â i , />c' Ti fif /> /ex restes sont tlifférents, — Car si Ton avait

f'm^ rm* f m H m :: A), on en déduiraÎL^ comme plus haut,

de sorte que r* oe serait pks le premier reste de la suite i\î3) qui serait congru ii k

l\ . />e«.r rej/i?4f rfo/i^ les rangs^ dans ta suite (43). diffèrent de k sont égaujt:, — En eflTet,

Mats, puisque /^ -^ i , on a Donc Donc

%^=EH (mùân).

Eti particulier, les restes qui sont égaux à i soDt les restes r^t

Il reste à démontrer que k est un diK^istutr de 'f{n). Or, noit* venons de voir que les restes qui sont égaust à i sont ceux dont rîndice est un multiple de /r ; d'autre parti d'après le théorème d*EuIer, r^^a^ est égal k t .

Donc f{n) est un multiple de k (*).

( * } îif celle façïjn, jjour tlérfiontrcr que k est un dîvrsem' de f (n)> î\ou^ s^upposons élabïi le lliéorèmo trEuler» On peut» au contraire, dt^munircr qiit? A cil un diviseur de n sans s'appuyer soi le théorumc d'KuIcr, et en déduire ce dcrnîcr tliëorème*

En effet, tes rcsi€s r^ /•,, *,., r^ sont lous différents* Si ces restes conaUtoeni