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.