RaSol: Memento teoria numerelor

Tuesday, November 29, 2005

Memento teoria numerelor

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 ≦ n^1/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 = p₁p₂...p_s unde s este un intreg pozitiv si p₁p₂...p_s sunt prime ce satisfac relatia p₁≦p₂≦...≦p_s
descompunerea in factori primi exista si este unica
daca a si b sunt doua numere supraunitare cu descompunerile in factori primi a = p₁^a₁p₂^a₂...p_k^a_k si b = p₁^b₁p₂^b₂...p_k^b_k at. cmmdc( a , b ) = p₁^{min ( a₁ , b₁ )}p₂^{min ( a₂ , b₂ )}...p_k^{min ( a_k , b_k )}
numere relativ prime: a, b sunt relativ prime ⇔ cmmdc ( a , b ) = 1
T: fie a > 1 si n > 1
aⁿ-1 este prim ⇒ a = 2 si n este prim
aⁿ+1 este prim ⇒ a este impar si ∃ k > 1 ai n = 2^k
numere Mersenne: Daca un numar este de forma M_n = 2ⁿ-1 se numeste numar Mersenne. Daca M_n este prim se numeste prim Mersenne
numere Fermat: Daca un numar este de forma F_n = 2^2ⁿ-1 se numeste numar Fermat. Daca F_n este prim se numeste prim Fermat
T: Daca M_n 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 = p₁^e₁p₂^e₂...p_r^e_r unde r ≧ 1 , p₁≦p₂≦...≦p_r sunt prime si e_i ≧ 0, ∀ i ∈ { 1 , 2, ... , r }. At.
τ ( n ) = ( e₁ + 1 )( e₂ + 1 ) ... ( e_r + 1 )
σ ( n ) = ( p₁^{e₁ + 1} - 1 ) / ( p₁ - 1) ( p₂^{e₂ + 1} - 1 ) / ( p₂ - 1) ... ( p_r^{e_r + 1} - 1 ) / ( p_r - 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)
aⁿ ≡ bⁿ ( 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
Z_m = { [ a ] / a ∈ Z}
sistem complet de resturi modulo m
multimea de intregi { a₁ , a₂ , ... , a_m } se numeste sistem complet de resturi modulo m daca Z_m = { [ a₁ ] , [ a₂ ] , ... , [ a_m ] }
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 Z_m
fie [ a ], [ b ] ∈ Z_m, se definesc: [ a ] + [ b ] = [ a + b } si [ a ][ b ] = [ ab ]
J_m = {0, 1, ... m - 1} cu operatiile a ⊕ b = ( a + b) mod m si a ⊙ b = ( ab ) mod m formeaza un inel izomorf cu Z_m
o clasa de resturi [ a ] ∈ Z_m este unitara daca nu este inversabila ⇔ cmmdc ( a , m) = 1
grupul unitatilor
U_m = { [ i ] / 1 ≦ i ≦ m si cmmmdc( i , m) = 1} impreuna cu inmultirea (din Z_m) formeaza un grup abelian
daca p este prim, at. ∃ a ∈ U_p ai U_p = <a>
daca n ≧ 2 , at. ∃ a ∈ U_p ai U_p = <a> ⇔ a este de froma 2, 4, p^k, 2 p ^k unde p ≧ 2, p este prim si k ∈ N
functia φ Euler
ordinul lui U_m
proprietati φ Euler
ptr. a > 0, b > 0 si cmmdc ( a , b ) = 1 : φ( ab ) = φ( a )φ( b )
ptr. p, prim, si n > 0 : φ( pⁿ ) = pⁿ - p^n-1
ptr. p₁, p₂, ..., p_k, prime distincte, si n₁, n₂, ..., n_k, intregi pozitivi : φ(p₁^n₁ p₂^n₂ ... p_k^n_k) = ( p₁^n₁ - p₁^n₁-1 ) ... ( p_k^n_k - p_k^n_k-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 : Z_n → Z_a x Z_b este bijectiva
f : U_n → U_a x U_b este bijectiva
teste primalitate: mica teorma a lui Fermat
daca p este prim si a, cmmdc( a , p) = 1 at. a^p-1 ≡ 1 ( mod p)
teorema lui Euler
ptr. m > 0 si a, cmmdc( a , m ) = 1 : a^φ(m) ≡ 1 ( mod m )
a^p ≡ a ( mod p), ∀ a si p prim
ptr. m ≧ 2, ∀ a, 1 ≦ a ≦ m -1, a^m-1 ≡ 1 ( mod m) ⇒ m prim
reprezentarea lui n in baza b
ptr. b ≧ 2, n > 0 , n = [a_k, a_k-1, ..., a₁, a₀]_b este reprezentarea in baza b a lui n ⇔ ∃ k ≧ 0 ai n = a_kb^k + a_k-1b^k-1 + ... + a₁b + a₀ unde a_i ∈ {0, 1, ..., b-1}, i ∈ {0, 1, ..., k}
reprezentarea este unica
metoda binara pentru calculul lui xⁿ, x ∈ R, n ∈ Z⁺
se gaseste reprezentarea binara n = [ a_r , ... , a₁ ,a₀ ]₂
se calculeaza puterile x² , x^2² , ... , x^{2^r}
se calculeaza produsul xⁿ = x^{a_r2^r} x^{a_r-12^r-1} x^a₁2 x^a₀
metoda binara pentru calculul lui xⁿ ( mod m) , x ∈ R, n ∈ Z⁺
se gaseste reprezentarea binara n = [ a_r , ... , a₁ ,a₀ ]₂
se calculeaza redusele modulo m ale puterilor x² , x^2² , ... , x^{2^r} , m₁ = x² mod m , m₂ = x^2² mod m , ... , m_r = x^{2^r} mod m
se calculeaza produsul xⁿ mod m = m_rm_r-1 ... m₁ m₀

Introducere in teoria numerelor, Edwin Clark

# posted by Sorin Badescu @ 1:54 PM

Comments:

mul?umiri foarte interesant,

# posted by

Anonymous : 9:39 AM

RaSol

Tuesday, November 29, 2005

Memento teoria numerelor

About Me

Links

archives