[PDF] Congruence - Equations diophantiennes

View - Download Congruence - Equations diophantiennes

Previous PDF

Next PDF

FST Mulhouse.

Licence 1 Maths-Info

Mathématiques : ARITHMETIQUE-ALGEBRE

Elisabeth REMM

Chapitre 3Congruence - Equations diophantiennes

1.La relation de congruence

1.1.Définition de la congruence modulop.Soitpun entier positif donné.

Définition 1.Soientmetndeux entiers. n dit quemest congru ànmodulopet on écrit m≡n(modp) ou parfois pour raccourcir l"écriture m≡n[p] sipdivise la différencem-n. Ceci est aussi équivalent à dire quemetnont les mêmes restes dans la division euclidienne parp. Cette relation est appelée la relation de congruence modulop.

Exemples

(1)18≡13 (mod 5) (2)m= 2k≡0 (mod 2), oùk?Z. (3)m= 2k+ 1≡1 (mod 2), oùk?Z. Théorème 1.La relation de congruence modulopest une relation d"équivalence.

Démonstration.Elle est en effet

(1) Réflexiv ecar m-ma pour reste0dans la division parp. (2) Symétrique car si m-na pour reste0il en esr aussi de même den-mdans la division parp, 1

2 L1-Maths-Info Chapitre 3

(3) T ransitive.En effet si m1est congru àm2modulopetm2congru àm3modulop, alors m

1-m2est divisible parp, c"est-à-direm1-m2=kp,m2-m3est aussi divisible parp,

soitm2-m3=k2p. Aisni m

1-m3=m1-m2+m2-m3=kp+k1p= (k+k1)p

etm-m2est aussi divisible parpsoitm1congru àm3modulop, ce qui montre la transi- tivité. La relation de congruence modulopest donc Réflexvie, Symétrique et Transitive.

C"est une relation d"équivalence.

1.2.Addition,soustraction et multiplication de nombres congruents.Nous allons re-

garder le comportement de cette relation par rapport aux opérations arithmétiques ordinaires. Proposition 1.Soitpun entier positif donné et soientm1,m2,n1,n2des entiers tels que m

1≡m2(modp), n1≡n2(modp).

Alors (1)m1+n1≡m2+n2(modp), (2)m1-n1≡m2-n2(modp), (3)m1n1≡m2n2(modp) Démonstration.La démonstration est facile et laissée au lecteur. Il suffit de se servir des hypothèses : m

1-m2=k1p, n1-n2=k2p.

La troisième propriété est un peu plus délicate à établir. On écrit m

1n1-m2n2=m1n1-m1n2+m1n2-m2n2=m1(n1-n2) + (m1-m2)n2

ce qui permet de conclure. Par contre, pour la division les choses sont moins simples. Nous y reviendrons en fin de cours dans l"étude de certaines structures algébriques.

1.3.L"ensemble des classes d"équivalence.Considérons la relation d"équivalence modulo

p. Soitmun entier. Sa classe d"équivalence est par définition le sous-ensemble deZ, notécl(m)

et défini comme suit : cl(m) ={n?Z, n≡m(modp)}. Proposition 2.Pourpentier positif donné, il existepclasses d"équivalence pour la relation de congruence modulop, à savoir cl(0),cl(1)···,cl(p-2),cl(p-1). m≡r(modp).Comme les restes de la division parpsont les entiers positifs compris entre0

etp-1, on en déduit qu"il y a au pluspclasses d"équivalence, celles décrites dans la proposition.

Il reste à montrer que ces classes forment une partition deZ. Il est clair que la réunion de ces

classes est l"ensembleZ. Montrons que leurs intersections sont vides. Sin?cl(r1)etn?cl(r2) alors le reste de la division denparpestr1etr2, ce qui impliquer1=r2et donccl(r1) = cl(r2).

Elisabeth Remm 3

On noteZ/pZl"ensemble quotient associé à cette relation, c"est-à-dire l"ensemble des classes

d"équivalence. On en déduit Par soucis de simplification d"écriture, nous adopterons l"écriture suivante cl(m) =m (p) ou si la précision depest superflue, car sous-entendue cl(m) =m. Les opérations sur les classes s"écrivent alorsm+n=m+n,m·n=mn mais en prenant garde qu"il s"agit toujours de la congruence modulo le même entier.

Exemples.

(1)Z/2Z={0,1}. (2)Z/3Z={0,1,2}. (3)Z/4Z={0,1,2,3}. Comme ces ensembles sont finis et munis de deux opérations+et×, nous pouvons dresser les tables de ces opérations.

Exemples.

(1) Dans Z/2Zles tables d"addition et de multiplication s"écrivent+01 001

110,×01

000 101
(2) Dans Z/3Zles tables d"addition et de multiplication s"écrivent+012 0012 1120

2201,×012

0000 1012
2021
(3) Dans Z/4Zles tables d"addition et de multiplication s"écrivent+0123 00123
11230
22301

33012,×0123

00000 10123
20202
30321

Nous étudierons plus en détail les propriétés de ces opérations dans le dernier chapitre consacré

aux structures algébriques.

4 L1-Maths-Info Chapitre 3

2.Applications : les preuves par3,5et9

2.1.Quelques calculs avec la congruence.Nous avons vu, ci-dessus, la relation : soitp

un entier positif donné et soientm1,m2,n1,n2des entiers tels quem1≡m2(modp), n1≡ n

2(modp), alors

m

1n1≡m2n2(modp).

Nous en déduisons immédiatement

Proposition 3.Soitpun entier positif donné et soientm1,m2des entiers tels quem1≡ m

2(modp), alors pour toutk?N

m k1≡mk2(modp).

Exemples.

(1) Mo dulo3: Nous savons que10≡1 (mod 3). Nous en déduisons que pour toutk?N, 10 k≡1 (mod 3) et aussi 10 k+ 2≡1 + 2 (mod 3). Mais comme2 + 1 = 3≡0 (mod 3), nous obtenons, pour toutk?N, 10 k+ 2≡0 (mod 3) et donc10k+ 2est divisible par3. (2) Mo dulo7: Nous voulons simplifier l"expression931002+931001+931000( mod 7).Consi- dérons l"entier93. On vérifie sans peine que93≡2 (mod 7).Nous en déduisons que pour tout entierk,93k≡2k(mod 7).Mais23≡1 (mod 7).Ceci implique 2

999≡1 (mod 7),21000≡2 (mod 7),21001≡4 (mod 7),21002≡1 (mod 7).

Ainsi 3

1002+ 931001+ 931000≡(2 + 4 + 1)≡0(mod 7).

2.2.La preuve par3ou par9.Considérons un nombre entiernécrit sous sa forme décimale :

n=a1a2·ap avecai? {0,1,2,···,9}.Par exemplen= 5432, alorsa1= 5,a2= 4,a3= 3,a4= 2. Cette

écriture est équivalente à

n=a1·10p-1+a2·10p-2+···+ap-1·10 +ap. Par exemple5432 = 5·103+4·102+3·10+2.Mais nous avons10≡1(mod 3),102≡1(mod 3) et donc plus généralement, pour toutk?N: 10 k≡1(mod 3). Ainsi n=a1·10p-1+a2·10p-2+···+ap-1·10 +ap≡a1+a2+···+ap(mod 3). De même nous avons10≡1 (mod 9)et donc pour tout entierk,10k≡1 (mod 9).Nous aurons donc aussi n=a1·10p-1+a2·10p-2+···+ap-1·10 +ap≡a1+a2+···+ap(mod 9).

On en déduit la règle de divisibilité :

Elisabeth Remm 5

Proposition 4.(1)Un nombr eentier nest divisible par3si et seulement si la somme de ses chiffres est divisible par3. (2) Un nombr eentier nest divisible par9si et seulement si la somme de ses chiffres est divisible par9.

2.3.La preuve par11.D"après ce que nous venons de voir, les critères de divisibilité par

un entierprepose sur l"étude de10k(modp). Icip= 11et10≡ -1 (mod 11),102≡

1 (mod 11),103≡ -1 (mod 11),ce qui donne en général

10

2k≡1 (mod 11),102k+1≡ -1 (mod 11).

Ainsi n=a1·10p-1+a2·10p-2+···+ap-1·10 +ap≡(-1)p-1a1+ (-1)p-2a2-ap-1+ap. Proposition 5.Un nombre est divisible par11lorsque la différence entre la somme des chiffres de rang pair et la somme des chiffres de rang impair est un multiple de11.

Prenons par exemplen= 5432. Nous avons

5432≡ -5 + 4-3 + 2 =-2 = 9 ( mod 11).

De meme25432≡2-5 + 4-3 + 2 = 0 ( mod 11)et donc ce nombre est divisible par11.

2.4.Quelques autres règles de divisibilité.On pourra, à titre d"exercices, démontrer de

manière analogue d"autres règles de divisibilté Proposition 6.(1)Un nombr eest divisible p ar4lorsque les deux chiffres de droite forment un nombre multiple de4. (2) Un nombr eest divisible p ar5lorsque le chiffre des unités est0ou5. (3) Un nombr eest divisible p ar8lorsque les trois chiffres de droite forment un nombre mul- tiple de8.

Il existe également un critère de divisibilité par7, mais cela commence à devenir peu simple

à utiliser. On séparer ce nombre par tranches de trosi chiffres en partant des unités et d"insérer

alternativement des-et des+entre les tranches. On effectue l"opération ainsi écrite et ce résultat est divisible par7si et seulement le nombre de départ l"est.

3.Congruence modulo un nombre premier

Dans cette partie nous allons nous intéresser à la congruence moduloplorsquepest un nombre premier. Nous verrons en dernière partie du cours que les ensemblesZ/pZont des structures algébriques différentes lorsquepest premier ou pas. Nous avons ci-dessus étudier les tables de multiplications deZ/pZpourp= 2,3etp= 4. Nous pouvons remarque sur ces exemples une différence de structure entreZ/4Zet les deux autreZ/2ZetZ/3Z. En effet dans Z/4Z, il existe un élément non nul dont le carré est nul. En effet on a (2 (4))2=0 (4).

Cette propriété est fausse dansZ/2Zcar(1

(2))2=1 (2)et dansZ/3Zcar(1 (3))2=1 (3)et (2 (3))2=1 (3). Dans ces deux ensembles on a aussi la propriété plus générale : x·y= 0?x= 0 ouy= 0

6 L1-Maths-Info Chapitre 3

propriété qui est bien entendu fausse dansZ/4Z, nous l"avons vu pourx=y=2 (4).

3.1.L"ensembleZ/pZlorsquepest premier.

Proposition 7.Soitpun nombre premier. Alors l"équation x·y= 0, x,y?Z/pZ a pour seules solutionsx= 0ouy= 0. Démonstration.En effet soientx,y?Z/pZ. Il existe des entiersmetn,m < petn < ptels quex=m (p)ety=n (p). Alors x·y=m (p)·n (p)=mn (p).

Supposonsx·y= 0, c"est-à-diremn

(p)=0 (p).Alors le produitmnest dans la classe de0ce qui est équivalent à dire quemnest congru est0modulopou encore quemnest divisible par p. Commepest premier, d"après le théorème de Gauss, alors soitmest divisible parpsoitn est divisible parp, soitm (p)=0 (p), soitn (p)=0 (p).D"où la proposition. Remarque : la réciproque est aussi vraie : sipn"est pas premier, il existe dansZ/pZ deux éléments non nulsxetytels quex·y= 0.En effet sipn"est pas premier, il existem etndiviseurs depautres que1etptels quep=mn. On en déduit quem (p)·n (p)=mn (p)=0 (p).

3.2.Le théorème de Fermat.

Théorème 2.Soitpun nombre premier eta?Zun entier non multiple dep. Alors a p-1≡1 (modp).

Démonstration.Commençons par démontrer le lemme suivant, souvent appelé identité de Fro-

benius Lemme 1.Soitpun nombre premier. Alors pour toutxetydansZ, on a (x+y)p≡xp+yp(modp). En effet si nous développons(x+y)p, par exemple par récurrence, nous voyons que et chacun des coefficientsap-k,kest entier. Or nous avons vu que ces coefficients ne sont rien d"autre que les coefficients binomiaux a p-k,k=?p-k p? =p!(p-k)!k!. On en déduit que ces coefficients binomiaux sont tous entiers. Or p!(p-k)!k!=p(p-1)···(p-k+ 1)k! soit (k!)?p-k p? =p(p-1)···(p-k+ 1).

Elisabeth Remm 7

On en déduit quepdivise l"entier(k!)?p

p-k? .Or nous avons supposéppremier. Ceci implique que soitpdivise2, soit divise3, soit diviseksoit divise?p-k p?.Maisk < p. Donc la seule possibilité estpdivise?p-kquotesdbs_dbs28.pdfusesText_34

[PDF] calcul consommation ampoule 100w

[PDF] consommation ampoule 60w

[PDF] combien coute une ampoule allumée

[PDF] calcul consommation ampoule led

[PDF] lumiere allumée toute la nuit consommation

[PDF] calcul de consommation électrique d'un appareil

[PDF] consommation ventilateur 40w

[PDF] consommation congelateur ancien

[PDF] consommation four electrique kwh

[PDF] tableau de consommation des appareils électroménagers pdf

[PDF] consommation frigo américain

[PDF] consommation frigo kwh

[PDF] cout electricite congelateur

[PDF] consommation vieux frigo

[PDF] consommation congelateur 30 ans