Congruenze lineari

Page 1

Notazione Per ogni a, b∈ Z, si pone: a≡ b (mod n) ⇔ n| a− b. La srittura a≡ b (mod n) si legge “ a congruo b modulo n”. Proposizione 1. Sia n∈ N∗, n̸= 1. La relazione Rn ={(a, b)∈ Z× Z : a≡ b(mod n)} ` e una relazione di equivalenza suZ, che si dice congruenza modulo n. Dimostrazione. Si deve provare che (1)Rn ` e riflessiva:∀a∈ Z, a≡ a (mod n) (2)Rn ` e simmetrica:∀a, b∈ Z, a≡ b (mod n)⇒ b≡ a (mod n) (3)Rn ` e transitiva:∀a, b, c∈ Z, ( a≡ b (mod n) ∧ b≡ c (mod n) ) ⇒ a≡ c (mod n) (1) Poich´ e per ognia∈ Z, n| a− a, sicuramente (a, a)∈R n, ovvero a≡ a (mod n). (2) Siano a, b∈ Z, con a≡ b (mod n). Questo vuol dire che n| a− b, quindi n|− (a− b), cio` en| b− a, per cui b≡ a (mod n). (3) Siano a, b, c∈ Z, con a≡ b (mod n) e b≡ c (mod n), ovvero n| a− b e n| b− c. Allora n| (a− b) + (b− c), vale a dire n| a− c e quindi a≡ c (mod n). Teorema 1. L’insieme quoziente di Z perRn ha esattamente n elementi, cio` e: Z/Rn ={[0]n, [1]n, . . . ,[n− 1]n}, dove [x]n indica la classe di equivalenza di x∈ Z. Dimostrazione. Bisogna prima dimostrare che le classi [0] n, [1]n, . . . ,[n− 1]n sono a due a due distinte. Siano i, j∈{ 0, . . . , n− 1}, per esempio con j≤ i, e si supponga che sia [ i]n = [ j]n. Questo vuol dire che i≡ j (mod n), ovvero che n| i− j; per` o da 0≤ i− j≤ n− 1, segue che deve essere i− j = 0, ovvero i = j. Quindi se [ i]n = [j]n, allora i = j, e quindi se i̸= j, allora [ i]n̸= [j]n Per completare la dimostrazione, si deve provare che per ogni [ a]n∈ Z/Rn esiste [r]n∈ Z/Rn, r∈{ 0, . . . , n− 1}, tale che [ a]n = [ r]n. Pertanto, sia [ a]n∈ Z/Rn: a∈ Z e quindi esistono e sono unici q, r∈ Z, con 0≤ r≤ n− 1, tali che a = qn + r. Segue che a− r = qn, ovvero n| a− r, cio` ea≡ r (mod n), e quindi [ a]n = [r]n. L’insieme quoziente di Z perRn si chiama insieme dei resti modulo…