- divizibilitate
- d|n, d divide n (d este un divizor al lui n, d este un factor al lui n, n este un multiplu al lui d), d, n ∈ Z ⇔ ∃ k ∈ Z ai n = d * k
- teorema impartirii
- a ∈ Z, b ∈ Z* at ∃ q, r ∈ Z, unici, ai a = b * q + r si 0 ≦ r < b
- a ∈ Z, b ≠ 0 at ∃ q, r ∈ Z, unici, ai a = b * q + r si 0 ≦ r < | b |
- modulo
- a mod b = { b / a ∈ Z, b ∈ Z*, a = b * q + r }
- cmmdc
- cmmdc(a, b) ⇔ a, b ∈ Z*, D = {d | d|a ∧ d|b}, cmmdc(a, b) = sup D
- proprietati
- ∀ a, b ∈ Z*, ∃ cmmdc(a, b) si 0 < cmmdc(a, b) ≦ min ( | a |, | b |)
- ∀ a ∈ Z* at cmmmdc(a, 0) = 0
- ∀ a, b ∈ Z+, cmmdc(a, b) = cmmdc (b, r) unde a = b * q +r
- Lema Bezout: ∀ a, b ∈ Z ∃ s, t ai cmmdc(a, b) = s * a + t * b
- numar prim
- p ∈ Z, p ≧ 2, se numeste prim ⇔ D = { d / d | p} contine numai pe 1 si pe p (altfel se numeste numar compozit)
- T
- n ∈ Z+ este compozit ⇔ ∃ a, b , 1 < a < n, 1 < b < n ai n = a * b
- ∀ n > 1, ∃ p, un numar prim, ai p | n
- (Euclid) exista un numar infinit de numere prime
- daca n > 1, este un numar compozit at. ∃ p, un numar prim, ai p | n si p ≦ n1/2
- π ( x )
- reprezinta cardinalul multimiii numerelor prime mai mici decat x ∈ R+
- T
- π ( x ) ~ x / ln ( x ), x ∈ R+
- Teorema fundamentala a aritmeticii (descompunerea in factori primi)
- ∀ n intreg, n > 1, poate fi scris sub forma n = p1p2...ps unde s este un intreg pozitiv si p1p2...ps sunt prime ce satisfac relatia p1≦p2≦...≦ps
descompunerea in factori primi exista si este unica
daca a si b sunt doua numere supraunitare cu descompunerile in factori primi a = p1a1p2a2...pkak si b = p1b1p2b2...pkbk at. cmmdc( a , b ) = p1min ( a1 , b1 )p2min ( a2 , b2 )...pkmin ( ak , bk )
- numere relativ prime
- a, b sunt relativ prime ⇔ cmmdc ( a , b ) = 1
- T
- fie a > 1 si n > 1
- an-1 este prim ⇒ a = 2 si n este prim
- an+1 este prim ⇒ a este impar si ∃ k > 1 ai n = 2k
- numere Mersenne
- Daca un numar este de forma Mn = 2n-1 se numeste numar Mersenne. Daca Mn este prim se numeste prim Mersenne
- numere Fermat
- Daca un numar este de forma Fn = 22n-1 se numeste numar Fermat. Daca Fn este prim se numeste prim Fermat
- T
- Daca Mn este prim at. n este prim
- (Lucas-Lehmer)
- functiile σ si τ
- fie n > 0; se noteaza
- τ ( n ) cardinalul multimii formate de divizorii pozitiv ai lui n
- σ ( n ) suma divizorilor pozitiv ai lui n
- T
- fie descompunerea in factori a lui n = p1e1p2e2...prer unde r ≧ 1 , p1≦p2≦...≦pr sunt prime si ei ≧ 0, ∀ i ∈ { 1 , 2, ... , r }. At.
- τ ( n ) = ( e1 + 1 )( e2 + 1 ) ... ( er + 1 )
- σ ( n ) = ( p1e1 + 1 - 1 ) / ( p1 - 1) ( p2e2 + 1 - 1 ) / ( p2 - 1) ... ( prer + 1 - 1 ) / ( pr - 1)
- numere perfecte
- se noteaza σ*( n ) suma divizorilor pozitivi mai mici ca n, ai lui n
- ptr n ≧ 2, σ*( n ) = σ( n ) -n
un numar este perfect daca σ*( n ) = n
- congruente
- a congruent cu b modulo m
- a ≡ b (mod m) ⇔ ptr m ≧ 0, m | a - b
- m > 0, ∀ a, b : a ≡ b (mod m) ⇔ a mod m = b mod m ptr m ≧
- proprietati relatie congruenta
- (reflexivitate) a ≡ a ( mod m)
- (simetrie) a ≡ b (mod m) ⇒ b ≡ a (mod m)
- (tranzitivitate) a ≡ b (mod m) si b ≡ c (mod m) ⇒ a ≡ c (mod m)
- element invers
- daca cmmdc( a , m ) = 1 at ∃ a', 0 < a' < m , unic, ai aa' ≡ (mod m)
- T operatii
- a ≡ b ( mod m) si a ≡ b ( mod m) ⇒
- a ± b ≡ c ± d ( mod m)
- ac ≡ bd ( mod m)
- an ≡ bn ( mod m ) ∀ n ≧ 1
- f ( a ) ≡ f ( b ) , ∀ f ( x) , polinom cu coeficienti intregi
- T
- ptr c > 0 , m > 0 : a ≡ b ( mod m) ⇔ ca ≡ cb ( mod cm)
- ptr. m > 0 si d = cmmdc ( c , m) : ca ≡ cb ( mod m) ⇒ a ≡ b ( mod m/d)
- m > 0 , a ≡ b ( mod m) ⇒ cmmdc ( a, m) = cmmdc ( b , m)
- clase de resturi
- clasa de resturi a modulo m
- pt. m > o fixat si ptr a intreg se defineste [a] = { x / x ≡ a ( mod m) }
- ptr. m > 0: [ a ] = { mq + a / q ∈ Z }
- ptr. m > 0 : [ a ] = [ b ] ⇔ a ≡ b ( mod m)
- ptr. m > 0, ∀ a, ∃ r, 0 ≦ r < m, unic, ai [ a ] = [ r ]
- ptr. m > 0 sunt exact m clase distincte de resturi, [ 0 ] , [ 1 ] , ... , [ m - 1 ]
- sisteme de resturi
m > 0- inelul intregilor modulo m
- Zm = { [ a ] / a ∈ Z}
- sistem complet de resturi modulo m
- multimea de intregi { a1 , a2 , ... , am } se numeste sistem complet de resturi modulo m daca Zm = { [ a1 ] , [ a2 ] , ... , [ am ] }
- daca m = 2k at. {0, 1, 2, ..., k-1, k, -(k-1), ..., -2, -1} este un sistem complet de resturi modulo m
- daca m = 2k + 1 at. {0, 1, 2, ..., k, -k, ..., -2, -1} este un sistem complet de resturi modulo m
- adunarea si inmultirea in Zm
- fie [ a ], [ b ] ∈ Zm, se definesc: [ a ] + [ b ] = [ a + b } si [ a ][ b ] = [ ab ]
- Jm = {0, 1, ... m - 1} cu operatiile a ⊕ b = ( a + b) mod m si a ⊙ b = ( ab ) mod m formeaza un inel izomorf cu Zm
- o clasa de resturi [ a ] ∈ Zm este unitara daca nu este inversabila ⇔ cmmdc ( a , m) = 1
- grupul unitatilor
- Um = { [ i ] / 1 ≦ i ≦ m si cmmmdc( i , m) = 1} impreuna cu inmultirea (din Zm) formeaza un grup abelian
- daca p este prim, at. ∃ a ∈ Up ai Up = <a>
- daca n ≧ 2 , at. ∃ a ∈ Up ai Up = <a> ⇔ a este de froma 2, 4, pk, 2 p k unde p ≧ 2, p este prim si k ∈ N
- functia φ Euler
- ordinul lui Um
- proprietati φ Euler
- ptr. a > 0, b > 0 si cmmdc ( a , b ) = 1 : φ( ab ) = φ( a )φ( b )
- ptr. p, prim, si n > 0 : φ( pn ) = pn - pn-1
- ptr. p1, p2, ..., pk, prime distincte, si n1, n2, ..., nk, intregi pozitivi : φ(p1n1 p2n2 ... pknk) = ( p1n1 - p1n1-1 ) ... ( pknk - pknk-1 )
- T
- fie a, b ∈ Z+, cmmdc( a , b ) = 1 si n = ab. Se defineste f ( [ x ]n ) = ( [ x ]a , [ x ]b )
- (teorema chineza a resturilor) f : Zn → Za x Zb este bijectiva
- f : Un → Ua x Ub este bijectiva
- teste primalitate
- mica teorma a lui Fermat
- daca p este prim si a, cmmdc( a , p) = 1 at. ap-1 ≡ 1 ( mod p)
- teorema lui Euler
- ptr. m > 0 si a, cmmdc( a , m ) = 1 : aφ(m) ≡ 1 ( mod m )
- ap ≡ a ( mod p), ∀ a si p prim
- ptr. m ≧ 2, ∀ a, 1 ≦ a ≦ m -1, am-1 ≡ 1 ( mod m) ⇒ m prim
- reprezentarea lui n in baza b
- ptr. b ≧ 2, n > 0 , n = [ak, ak-1, ..., a1, a0]b este reprezentarea in baza b a lui n ⇔ ∃ k ≧ 0 ai n = akbk + ak-1bk-1 + ... + a1b + a0 unde ai ∈ {0, 1, ..., b-1}, i ∈ {0, 1, ..., k}
reprezentarea este unica - metoda binara pentru calculul lui xn, x ∈ R, n ∈ Z+
- se gaseste reprezentarea binara n = [ ar , ... , a1 ,a0 ]2
- se calculeaza puterile x2 , x22 , ... , x2r
- se calculeaza produsul xn = xar2r xar-12r-1 xa12 xa0
- metoda binara pentru calculul lui xn ( mod m) , x ∈ R, n ∈ Z+
- se gaseste reprezentarea binara n = [ ar , ... , a1 ,a0 ]2
- se calculeaza redusele modulo m ale puterilor x2 , x22 , ... , x2r , m1 = x2 mod m , m2 = x22 mod m , ... , mr = x2r mod m
- se calculeaza produsul xn mod m = mrmr-1 ... m1 m0
Introducere in teoria numerelor, Edwin Clark
# posted by Sorin Badescu @ 1:54 PM