Ingegneria Energetica - Analisi e Geometria 1

Congruenze lineari

Divided by topic

Notazione Per ognia; b2Z, si pone: ab(modn),njab: La sritturaab(modn) si legge \acongruobmodulo n". Proposizione 1.Sian2N ,n6 = 1. La relazione Rn= f(a; b)2ZZ:ab(modn)g e una relazione di equivalenza suZ, che si dicecongruenza modulon. Dimostrazione.Si deve provare che (1)R ne ri essiva: 8a2Z,aa(modn) (2)R ne simmetrica: 8a; b2Z,ab(modn))ba(modn) (3)R ne transitiva: 8a; b; c2Z, ab(modn)^bc(modn)
)ac(modn) (1) Poiche per ognia2Z,njaa, sicuramente (a; a)2 R n, ovvero aa(modn). (2) Sianoa; b2Z, conab(modn). Questo vuol dire chenjab, quindinj (ab), cioenjba, per cuiba(modn). (3) Sianoa; b; c2Z, conab(modn) ebc(modn), ovveronjabenjbc. Alloranj(ab) + (bc), vale a direnjace quindiac(modn). Teorema 1.L'insieme quoziente diZperR nha esattamente nelementi, cioe: Z=R n= f[0] n; [1] n; : : : ; [n1] ng ; dove [x] nindica la classe di equivalenza di x2Z. Dimostrazione.Bisogna prima dimostrare che le classi [0] n; [1] n; : : : ; [n1] nsono a due a due distinte. Sianoi; j2 f0; : : : ; n1g, per esempio conji, e si supponga che sia [i] n= [ j] n. Questo vuol dire che ij(modn), ovvero chenjij; pero da 0ijn1, segue che deve essereij= 0, ovveroi=j. Quindi se [i] n= [ j] n, allorai=j, e quindi sei6 =j, allora [i] n6 = [j] n Per completare la dimostrazione, si deve provare che per ogni [a] n2 Z=R nesiste [ r] n2 Z=R n, r2 f0; : : : ; n1g, tale che [a] n= [ r] n. Pertanto, sia [ a] n2 Z=R n: a2Ze quindi esistono e sono uniciq; r2Z, con 0rn1, tali chea=qn+r. Segue che ar=qn, ovveronjar, cioear(modn), e quindi [a] n= [ r] n. L'insieme quoziente diZperR nsi chiama insieme dei resti modulone si indica con il simboloZ n. Denizione 1.Sianoa; b2Z,a6 = 0,n2N ,n6 = 1. Si dicecongruenza lineare l'espressione (1)axb(modn): Si dice soluzione di (1) ogni interox 0tale che ax 0 b(modn);ovvero tale chenjax 0 b: Teorema 2.Sianoa; b2Z,a6 = 0,n2N ,n6 = 1. 1.La congruenza lineare(1)ammette soluzioni se e solo seM :C:D:(a; n)jb. 2.Sex 0e una soluzione di (1), postod=M :C:D:(a; n), n=nd 2 Z, tutte e sole le altre soluzioni di(1)sono x0+ k n; k2Z: 3.Inne ci sono esattamentedsoluzioni non congrue tra loromodn, che sono (ad esempio) x0; x 0+  n; : : : ; x 0+ ( d1)n: 1 2 Dimostrazione.Il punto 1. e una conseguenza del teorema sulle equazioni Diofantee. Infatti dire che (1) ha soluzione, equivale a dire che esistex 02 Ztale chenjax 0 b, ovvero che esistonox 0; y 02 Ztali cheax 0 b=ny 0, cioe ax 0 ny 0= b: questo vuol dire che esiste (x 0; y 0) 2ZZsoluzione dell'equazione Diofantea ax+ny=b ed e noto che cio accade se e solo seM :C:D:(a; n)jb. Per quanto riguarda 2., si prova soltanto che sex 0e una soluzione di (1), allora per ogni k2Z,x 0+ k ne ancora una soluzione di (1). Siax 0una soluzione di (1). Allora esiste h2Ztale cheax o b=hn. Posto a=ad 2 Z, per ognik2Zsi ha: a(x 0+ k n)b=ax 0+ kand b=ax 0 b+k an=hn+k an= (h+k a)n; ovvero esistek=h+k a2Ztale chea(x 0+ k n)b=kn, cioenj(a(x 0+ k n)b) e quindi a(x 0+ k n)b(modn): La dimostrazione di 3. viene omessa. Teorema 3.(Teorema cinese del resto) Un sistema si congruenze lineari del la forma: (2)8 > > > > < > > > > :x b 1( modn 1) xb 2( modn 2) . . . xb h( modn h) dove8i; j= 1; : : : ; h; M :C:D:(n i; n j) = 1 , ha sempre soluzioni. Inoltre c'e un'unica soluzione moduloR=n 1
: : :
n h. Dimostrazione.Si da soltanto un cenno della dimostrazione: si prova che una soluzione del sistema (2) e data da: x0= R 1
 x 1+ R 2
 x 2+


+R h
 x h dove per ognii= 1; : : : ; h Ri=n 1
n 2
: : :
n hn i; mentre x ie una soluzione della congruenza lineare Rix b i( modn i) : Esempio 1.8 > > > < > > > :x 3(mod5) x4(mod3) x2(mod7) x5(mod2) Si vede facilmente cheR1= 42 ; R 2= 70 ; R 3= 30 ; R 4= 105 : Si cercano le soluzioni delle congruenze lineari previste nel teorema: 42x3(mod5) ha soluzionex 1= 6, (si trova eseguendo l'algoritmo delle divisioni successive) 70x4(mod3) 3 ha soluzionex 2= 1 (70 4 = 66 che e multiplo di 3) 30x2(mod7) ha soluzionex 3= 1 (30 2 = 28 che e multiplo di 4) 105x5(mod2) ha soluzionex 4= 1 (105 5 = 100 che e multiplo di 2). Allora una soluzione e  x= 42
(6) + 70 + 30 + 105 =47; mentre la piu piccola soluzione positiva e 163 e tutte le soluzioni del sistema sono163 + 210h; h2Z: