[PDF] LIPN – Laboratoire dInformatique de Paris Nord

MTHSC 412 Section 26 Congruence Classes

1 Multiplication is a well de ned binary operation on Z n 2 Multiplication on Z n is associative 3 Multiplication on Z n is commutative 4 [1] is the multiplicative identity for Z n Kevin James MTHSC 412 Section 2 6 {Congruence Classes

THE GENERAL THEORY OF CONGRUENCES*

congruence which is composed of the tangents to the curves v = const, on S„ Moreover, the curves u = const, and v = const, on Sp form again a conjugate system, the first Laplacian transform of the given conjugate system on Sv The point Pa is related in similar fashion to the congruence composed of the

Exercices - Congruences

Donc x et y sont multiples de 5 4 Si (x;y) est solution de (E), alors x = 5k et y = 5k0, avec k et k0deux entiers 11x2 27y2 = 5 11 (5k)2 7 (5k0) = 5 11 252k2 7 5 k02 = 5 55k2 35k02 = 1 Or, il existe ce genre de relation si et seulement si les entiers 55 et 35 n’ont pas de diviseurs

I Division euclidienne/ divisibilité /congruence Division

LIPN – Laboratoire dInformatique de Paris Nord

Created Date: 2/3/2014 12:16:52 PM

S~minaire BOURBAKI TRAVAUX DE SHIMURA (~)

de hombres E , ind4pendant de la condition de congruence consid~r4e Ses composantes connexes g~om~triques, elles, seront d4finies sur des corps de classe de E

LARITHMETIQUE - AlloSchool

de congruence est transitive On dit que la relation de congruence est une relation d’équivalence 3) Soit un entier naturel non nul Si ≡ [ ] et ≡ [ ] alors : a) + ≡ + [ ] On dit que la relation de congruence est compatible avec l’addition dans ℤ 2

Mathématiques pour - Dunod

Le quotient et le reste de la division euclidienne de A = 53 par B = 6 sont respec-tivement Q = 8 et R = 5 En effet, 53 = 6 × 8 + 5 et 0 ≤ 5 < 6 Dans la division euclidienne de 1 893 par 11, le quotient vaut 172 et le reste vaut 1 On peut obtenir ces résultats en posant la division ou avec une calculatrice 1 1 2 Numération des entiers

MATHÉMATIQUES - ResearchGate

de p ne dépend que de la classe de congruence de p modulo 4d, et que la suite N p est donc périodique de période 4d Dans le cas des courbes elliptiques, la suite a p (E ) obéit une loi du même

ПРОФЕСОР АЛИПИ НИКОЛОВ МАТЕЕВ (1914–1979)

[36] Някои основни свойства на група и пръстен Математика, 7, 1968, 4, 8–11 [37] Квадратни матрици от втори ред и действия с тях

[PDF] paramètres de dispersion et de position

[PDF] écart type relatif

[PDF] écart absolu moyen

[PDF] les origines de la guerre d'algérie

[PDF] paraphrasing exercises with answers pdf

[PDF] paraphrasing techniques

[PDF] cat devant une paraplegie pdf

[PDF] tétraplégie pdf

[PDF] la paraplegie

[PDF] physiopathologie paraplégie

[PDF] paraplégie niveau lésionnel

[PDF] lésion médullaire cervicale

[PDF] prise en charge paraplégie

[PDF] lésion médullaire incomplete

[PDF] paraplégie conséquences psychologiques

Universite Paris 13, Institut Galilee

Departement de Mathematiques

Licence 2emeannee Informatique

2013-2014

Cours de Mathematiques pour l'Informatique

Des nombres aux structures

Sylviane R. Schwer

Lecon du 11 fevrier 2014 : divisibilite et relation de congruence dansZ

1 Denition et premieres proprietes des congruences

Denition 1.1Soitnun entier naturel. Etant donnes deux entiersaetbdeZ, on dit que \aest congru abmodulon", et l'on note \ab(modn)" ou \anb" siab2Z:

Exemple 201420 ; 201424102

Lemme 1.1anbsi et seulement siaetbont le m^eme reste dans la division euclidienne parn. Preuve :Soit (qa;ra) et (qb;rb) les deux couples uniques d'entiers 0qa;qb< net a=qan+raetb=qbn+rb.ab= (qaqb)n+ (rarb).ab2nZsi et seulement si r arb2nZ. Orn < rarb< net ]n;n[\nZ=f0gdoncra=rb2

1.1 etude de la relation de congruence modulon

Soitn2Ndonne, dansZ, la relationnsatisfait les proprietes de re exivite :8a2Z;anacar 02nZ symetrie :8a;b2Z;anb,bnacarnZest stable par oppose. transitivite ::8a;b;c2Z;anbetbnc)anccarnZest stable par addition. Les relations possedant ces trois proprietes forment une classe de relation tres impor- tante, d'ou la denition suivante. Denition 1.2 (Relation d'equivalence)Une relationRre exive, symetrique et tran- sitive sur un ensembleEnon vide est appelee une (relation)equivalencesurE. 1 L'egalite (denie comme l'identite) est la relation d'equivalence generalement disponible sur tout ensemble. Ses classes d'equivalence sont reduites aux singletons. C'est la seule relation qui est a la fois une relation d'ordre et une relation d'equivalence. Dans l'ensemble des humains, la relation "^etre ne la m^eme annee" est une relation d'equivalence. La relation "ressembler a" n'est pas une relation d'equivalence (cf. la sorite du chevelu du TD 1). ndansZest en fait un cas particulier de relations d'equivalences, celles denies a l'aide d'une fonction. En eet, il s'agit de la fonction deZdansZqui a tout entier relatif aassocie son le reste par la division euclidienne parn. On a le theoreme qui suit, dont la preuve est triviale. Theoreme 1.1Soitfune application (ou fonction totale) denie d'un ensembleEdans un ensembleF, la relation denie surEparxfysif(x) =f(y)est une relation d'equivalence. Denition 1.3 (Classe d'equivalence)SoitRune relation d'equivalence sur un en- sembleEnon vide. Une partieAnon vide deEtelle que

8a;a02A;aRa0et8a2A;8b62A;a(:R)b

est appelee classe d'equivalence deR. Soita2E, l'image deaparR,R(a) =fb2E;aRbgest appelee classe d'equivalence deamoduloRet est notee[a]R. Les classes d'equivalence des relations de congruence modulo n sont appeleesclasses de congruence modulo n. classes de congruence modulo 0 :a0b,a=b. Il s'agit donc de la relation d'egalite surZ. classes de congruence modulo 1 :a1b,ab2Z. Il s'agit donc de la relation d'indierence surZ. Il n'y a qu'une seule classe de 1-congruence.

1.1.1 Proprietes generales des relation d'equivalence

La re exivite d'une relationRsur un ensembleEpermet a l'union des classes d'equivalence RdansEde recouvrirEcar8x2E;x2[x]R. Si la relationRest une equivalence, on a de plus Proposition 1.2SoitRune equivalence sur un ensembleE,

8a;b2E;aRb,[a]R= [b]R:

2 Preuve.): SupposonsaRb, montrons que [a]R[b]R. Soitc2[a]R,aRcpar denition etcRapar symetrie. Par transitivite, on acRb, soitc2[b]R, donc [a]R[b]R. En echangeant les r^oles deaetb, on obtient [b]R[a]R, d'ou l'egalite cherchee. (: Supposons [a]R= [b]R, par re exivite,a2[a]R, orbRadoncaetbappartiennent a la m^eme classe dequivalence, ils sont donc equivalents :aRb2 Corollaire 1.1SoitRune equivalence sur un ensembleE, etCune classe dequivalence, alors8a2C,C= [a]R. Tout elementa2Cest appele un representant de la classeC. En eet,C6=;, donc9c2C;C= [c]R, et par denition deC,8a2CaRc,8a62

C;(:R)c.

Proposition 1.3 (relation d'equivalence et partition)SoitRune equivalence sur un ensembleE, les classes d'equivalence deRforment une partition deE, c'est-a-dire queEest l'union disjointe des classes d'equivalence deR. Preuve :SoitCune classe dequivalence deE. C'est une partie non vide deE. SoitCetC0deux classes d'equivalence dierentes. Montrons qu'elles sont disjointes. Comme ces deux classes ne sont pas identiques, l'une d'elle, disonsC, contient un element cnon contenu dansC0, c'est-a dire que8c02C0,c(:R)c0. Par denition d'une relation dequivalence,8c02C0;c062C. Deux classes dequivalence dierentes sont donc disjointes. Il nous reste a prouver que l'union des classes dequivalence recouvreE.

Or8a2E;a2[a]R2

Proposition 1.4Soitfune application d'un ensembleEnon vide dans un ensembleF, Les classes d'equivalence des relationsfsont en correspondance bijective avecf(E).

PreuvePar denition def.

Corollaire 1.2classes de congruence modulo n,n >1:Zpossede exactementnclasses de congruence modulon. Ces classes sont innies, disjointes deux a deux et leur union egaleZ. La proposition 1.4 permet la creation d'un nouvel ensemble d'importance, Denition 1.4 (ensemble quotient)SoitRune relation d'equivalence surE, l'ensemble fCi;i2Igdes classes d'equivalence deRest appele ensemble quotient de E par la relation

Ret est noteeE=R.

D'apres le corollaire 1.1,9(ai)i2IE;tel queE=R=f[ai]R;i2Ig. On dit que (ai)i2Iest un systeme de representant de deE=R, car il contient un et un seul element de chaque classe d'equivalence. On vient donc de denir de nouveaux objets, les classes d'equivalence, et un nouvel ensemble, l'ensemble des classes d'equivalence, ou ensemble quotient. La bijection qui existe entre l'ensemble quotient et un systeme de representants, nous interpelle sur la 3 possibilite de denir dansE=Rdes operations similaires aux operations denies dans E: faire sur les classes ce qu'on peut faire sur les representants. Il faut pour cela que le resultat des operations ne dependent pas du choix du systeme de representants. Il faut donc commencer par verier le comportement des operations vis-a-vis de la relation d'equivalence. C'est ce que l'on va commencer par faire sur les congruences modulon.

1.2 Operations arithmetiques et congruence modulon

Proposition 1.5Soitn2N;n >1eta;b;c;d2Ztels queanbetcnd, alors

1. compatibilite avec l'additiona+cnb+d

2. compatibilite avec le passage a l'opposeanb

3. compatibilite avec la multiplicationacnbd

4. stabilite par sommek+ank+b,8k2Z

5. stabilite par multiplicationkankb,8k2Z

6. stabilite puissanceaknbk,8k2N

Preuve :

1. compatibilite avec l'addition :ab2nZetcd2nZ)(a+c)(b+d)2nZ

par propriete arithmetique deZet stabilite additive denZ

2. compatibilite par passage a l'oppose carnZest stable par passage a l'oppose. On

en deduit donc la compatibilite avec la soustractionacnbd

3. compatibilite avec la multiplicationab2nZetcd2nZ. Oracbd=

acbc+bcbd. Doncacbd= (ab)c+b(cd)2nZ

4. trivial

5.kakb=k(ab)

6. Par recurrence : posons P(k) =aknbk. P(1) est vrai par hypothese suraetb.

Montrons queP(k))P(k+ 1).

a k+1=a:akn[Hyp P(k), P(1) et compatibilite avec la multiplication]b:bk=bk+1. CommeP(1), etP(k))P(k+ 1), l'identite est demontree pour tout8k2N.

Attention

manmb;anb

221032 mais 111016

4 Remarque :Unecongruenceest une relation d'equivalence compatible avec les operations internes de l'ensemble. Les congruences modulonsont donc bien des congruences deZ.

Proposition 1.6Soitn2N;n >1,a;b2Z,m2Z

Si(m^n= 1);alors(m:anm:b)anb)

Preuve :mest regulier pour la multiplication dansZ. . m:anm:b, 9k2Z, tel quemamb=m(ab) =kn. D'apres le theoreme de Gauss, m^n(mjk, c'est-a-dire que9k02Z;k=mk0. Doncm(ab) =mk0netab=k0n. Les identites 1 et 2 de la proposition sont fondamentales car elles permettent de denir une addition et une multiplication entre classes de m^eme congruence. En eet, elles disent que la classe de la somme [resp. du produit] d'un element quelconque d'une classeAavec un element quelconque d'une classeBest independant du choix des elements, c'est-a- dire que l'ensemble des classes possede ces operations comme operations internes. Nous verrons que les congruences sont des moyens de construire de nouvelles structures.

Exemples d'application a l'arithmetique.

4321 + 89639 est multiple de 9

432189639918 = 891

1010073277+2= (32)50.

Or 3

2= 972 d'ou 101007250=.

Or 2

371 et 50 = 316 + 2. Donc 1010072507= 22= 4.

Exemple d'application aux calendriers.

Calcul du nom du jour de tous les premiers de mois de 2014 connaissant le nom du jour du premier de l'an.2014 est une annee ordinaire. Une semaine est composee de 7 jours, chaque nom de jour de la semaine revient tous les 8 jours, c'est-a-dire que 871. LeMercrediest le nom du jour du premier janvier.

Table 1: nombre correspondant a chaque nom de jour pour 2014mercredijeudivendredisamedidimanchelundimardi

1234567

Le passage du premier d'un mois au premier du mois suivant correspond a un decallage de 28, 30 ou 31 jours selon le mois : pour passer du premier janvier au premier fevrier, il faut se decaller de 31 jours, nombre de jours du mois de janvier. Or 2870, 3072,

3173. Deux jours portent le m^eme nom si leurs quantiemes dans l'annee sont congrus

modulo 7. Le tableau 1 attribue 5

Table 2: nom du premier jours du mois pour 2014

janvierfevriermarsavrilmai... nombre jours3128313031 modulo quantieme du11 + 311+31+281+31+28+311+31+28+31+30... premier dans l'annee 71
74
74
77
72...
nom du premiermercredisamedisamedimardijeudi... Une annee ordinaire commence et nit par le m^eme jour de la semaine. En eet il y a 7 mois de 31 jours, 4 mois de 30 jours et 1 mois de 28 jours donc :

365743074271.

2 systemes de congruence

Theoreme 2.1 (theoreme des restes chinois)Soitn1etn2deux entiers premiers en- tre eux, etu1;u2un couple d'entiers satisfaisantu1n1+u2n2= 1. Alors8r1;r22Z, le systeme de congruence xr1(n1) xr2(n2) est equivalent a l'unique congruence xr2(u1n1) +r1(u2n2) (n1n2)

Preuve :

Posonsr=r2(u1n1) +r1(u2n2) ; alorsrr1[u2n2] (n1).

Maisu2n2+u1n1= 1 doncu2n21 (n1), doncrr1(n1).

De m^emerr2(n2). Doncrverie et le systeme (*) et la congruence unique. Soitxveriant le systeme (*). alorsxrest un multiple den1n2doncxr2n1Z\n2Z, orn1^n2= 1, doncxr2n1n2Z, c'est-a-dire quexverie l'unique congruence. Reciproquement, sixverie la congruence unique,9k2Ztel quex=r2u1n1+ r

1u2n2+kn1n2, doncx=r1u2n2+ (r2u1+kn2)n1Or 1 =u1n1+u2n2doncr=r1(1

u

1n1) + (r2u1+kn2)n1r1(n1)

et de m^emexr2(n2)2

Exemple :Pour resoudre(

x5 (8) x9 (11) comme 8^11 = 1, et 3:114:8 = 1, posonsr1= 5;n1= 8;u1=4;r2= 9;n2= 11;u2= 3 etr=123, il sut de resoudre x 12353 (88) soitx2 f53 + 88k;k2Zg 6

2.0.1 generalisation

L'Exemple classiqueUne bande de 17 pirates s'est empare d'un butin compose d'ecus de m^eme valeur. Ils decident de se les partager equitablement et de donner le reste, qui s'eleve a 3 ecus, au cuisinier chinois. Mais avant le debut du partage, les pirates se chamaillent et six d'entre eux sont tues. Le partage equitable entre les pirates restant, laisse au cuisinier 4 ecus. Mais survient alors un naufrage et seuls 6 pirates, le cuisinier et le tresor sont sauves. Ce dernier partage laisse 6 ecus au cuisinier. Quelle est alors la fortune minimale que peut esperer ce dernier s'il decide d'empoisonner les 6 pirates survivants ? Mise en equation du problemeIl s'agit de trouver le plus petitxstrictement positif veriant le systeme ()8 :(i)x3 (17) (ii)x4 (11) (iii)x5 (6)

Resolution du systeme

On constate de 17^11 = 1, et 217311 = 1 donc nous pouvons appliquer le theoreme chinois au systeme de congruence (iet (ii) en posantn

1= 17u

1= 2r 1= 3n

2= 11u

2=3r

2= 4etr=r2(u1n1) +r1(u2n2) = 4:2:17 + 3(3)11 = 37.

Le systeme () est equivalent au systeme

(i&ii)x37 (187) (iii)x5 (6) D'apres le theoreme des restes chinois (puisque 17, 11 et 6 sont premiers entre eux deux a deux, 187^6 = 1), et par division euclidienne 187 = 6:31 + 1 donc en posantn

1= 187u

1= 1r

1= 37n

2= 6u 1=31r

2= 5etr=r2(u1n1) +r1(u2n2) =5947.

La solution cherchee satisfait donc

x 5947 (1122):

Resolution du probleme

x=5947 +k:1122, aveck2Zdonnant la plus petite valeur positive pourx, soit le reste de la division euclidienne de5947 par 1122 qui est1785.1

Attention :(947 = 6:(1122) + 785

7 Interpretation du resultat dans les termes du probleme poseSi le cuisinier chinois empoisonne les 6 pirates restant, il garde le tresor entier, constitue d'au minimum

785 ecus.

Theoreme 2.2 (theoreme chinois generalise)Soitk2N;k2,n1;2;;kk en- tiers naturels premiers entre eux deux a deux, et kr1;r2;:::;rk2Z. Le systeme de congruences ()8 >>:xr1(n1) xr2(n2) xrk(nk) est equivalent a l'unique congruence xkX i=1r iUiNi(kY i=1n i) avecNi=Q k j=1njn ietUitel queUiNi+uini= 1 Le principe de la preuve est identique au theoreme chinois : PosonsNi^ni= 1d'ou l'existence deuietvid'apres l'identite de Bezout satisfaisant N iUi+niui= 1. posonsR=U1N1r1+U2N2r2+:::+UkNkrk,Rri(mi),8i2[[1;k]], c'est-a-dire queRest une solution du systeme (). Soitaest une autre solution de (), alorsaR2niZ,8i2[[1;k]], donc, puisqu'ils sont premiers entre eux,aR2(Qk i=1ni)Z. Autrement dit, les solutions de () sont de la formexR(Qk i=1ni).2 Attention :par rapport au theoreme precedent,u1=U2,u2=U1,N1=n2et N 2=n1.

Application au probleme du cuisinier chinois

17, 11 et 6 sont premiers entre eux deux a deux. Posonsn

1= 17N

1= 66U

1= 8r 1= 3n

2= 11N

2= 102U

2= 4r 2= 4n 3= 6N

1= 187U

3= 1r

1= 5etR=r1U1N1+r2U2N2+r3U3N3= 4141.

La solution cherchee satisfait donc

x4141785 (1122): 8quotesdbs_dbs16.pdfusesText_22