Kongruencija modulo n

Sa Wikipedije, slobodne enciklopedije

Relacija biti kongruentan modulo n je relacija ekvivalencije

  • refleksivna a / a ( mod n)
  • simetrija a / b ( mod n) =>b / a ( mod n)
  • tranzitivnost ( a / b ( mod n) & b /c( mod n) ) => a /c ( mod n)


Sadržaj

[uredi] Definicija 1

Skup koji dobijamo ako svaki član skupa Z pomnožimo sa n različitim od 0 označavamo sa nZ tj. nZ = (....,-3n, -2n, -n, 0, n, 2n. ....) Skup koji dobijamo ako svakom članu skupa nZ dodamo r (0 ≤ r < │n│ označavamo nZ +r

[uredi] Teorema 1

Ako je a /b ( mod n) tada za svaki cio broj x važi kongruencija(a +x) / ( b +x) ( mod n)


[uredi] Teorema 2

Ako je ac / bc ( mod n) i c relativno prim prema n onda je a /b ( mod n)


[uredi] Teorema 3

Ako je M(a,n) = 1 tada kongruencija ax /b ( mod n) ima rješenje u skupu Z


[uredi] Teorema 4

Ako su a i p relativno prim brojevi i p> 0 onda nikoja dva ostatka , što ih dobijamo dijeleći brojeve ( proizvode) ax1 , ax2 ......,a x( p-1) brojem p nisu jednaka i ni jedan od njih nije nula. Ti ostaci čine skup P = ( 1,2,......( p -1) )

Korolar Za svaki a i b iz P = ( 1,2,......( p -1) ) postoji jedan i samo jedan x iz P tako da je ax / b ( mod p)


[uredi] Teorma 5 (Fermatov teorem)

Ako je p>0 prim broj tada za svaki pozitivan cio broj a vrijedi a na p / a

Korolar a na p /a (mod p) za svako a iz Z


[uredi] Teorema 6(Eulerov teorem)

Ako je n pozitivan cio broj i a cio broj za koji važi M (a,n) /1 tada je a na q(n) /1 (mod n) gdje je q (n) broj svih pozitivnih cijelih brojeva manjh od n i relativno prim sa n.