Mathematics | Higher education » Bécsi László - Számelmélet tételsor

i Számelmélet tételsor Bácsi László lackac@math.bmehu 2002. december 10 ii Tartalomjegyzék 1 . . . . . 1 1 1 1 3 3 . . . . 4 5 6 7 7 3 Lineáris kongruenciák 3.1 Lineáris kongruenciák megoldása 3.2 Lineáris kongruenciarendszerek 8 8 8 4 Magasabb fokú kongruenciák 4.1 Magasabb fokú kongruenciák megoldása 4.2 Polinomok modulo prím 9 9 10 5 Rend, hatványmaradékok 5.1 Rend 5.2 Négyzetes (kvadratikus) maradékok 10 10 11 6 Számelméleti függvények 6.1 Függvénydefiníciók, multiplikativitás, additivitás 6.2 Összegzések 6.3 Minimális univerzális kitevő (exponens) 13 13 15 17 2 Elemi számelmélet 1.1 Oszthatósag 1.2 Maradékos osztás 1.3 LegNagyobb Közös Osztó 1.4 Lineáris diofantoszi egyenletek 1.5 Prímszámok . . . . . . . . .

. . . . . . . . . . . . . . . . Kongruenciák 2.1 Kongruenciák tulajdonságai 2.2 Maradékosztályok, maradékrendszerek 2.3 Euler- és Fermat-tételek 2.4 Moduláris aritmetika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Elemi számelmélet 1.1 Oszthatósag D EFINÍCIÓ 1.11 a, b ∈ Z, a osztója b-nek, ha ∃q ∈ Z : b = qa. T ÉTEL 1.12 Az oszthatóság N-en részbenrendezés T ÉTEL 1.13 a, b, c, m, n ∈ Z : c | a, c | b ⇒ c | (am + bn) k Általanosítva: ai , mi , c ∈ Z : c | ai , 1 ≤ i ≤ k ⇒ c | ∑ ai mi i=1 T ÉTEL 1.14 a | b, b 6= 0 : a, b ∈ Z ⇒ 0 < |a| ≤ |b| T ÉTEL 1.15 n 6= 0, a | b ⇔ na | nb 1.2 Maradékos osztás T ÉTEL 1.21 ( MARADÉKOS OSZTÁS ) a, b ∈ N+ , b 6= 0 : ∃!q, r ∈ N : a =

bq + r és 0 ≤ r < b Általánosítva: a, b ∈ Z, b 6= 0 : ∃!q, Z : a = bq + r és 0 ≤ r < b  r ∈ a ha b > 0 Megjegyzés: a = bq + r-nél: q =  ba  ha b < 0 b T ÉTEL 1.22 t > 1,t, n ∈ Z+ , ∃!a1 , . , am ∈ Z, am 6= 0, 0 ≤ ai < t, (1 ≤ i ≤ m) n = amt m + am−1t m−1 + . + a1t + a0 1.3 LegNagyobb Közös Osztó D EFINÍCIÓ 1.31 Legyen a, b ∈ Z, nem mindkettö 0, a és b legnagyobb közös osztója c, ha c > 0, közös osztó, és ∀d közös osztóra d ≤ c Jelölés: (a, b), gcd(a, b), lnko(a, b) 1.3 LegNagyobb Közös Osztó 2 D EFINÍCIÓ 1.32 a, b ∈ Z relatív prímek, ha (a, b) = 1 Általánosítva: a1 , . , an relatív prímek, ha (a1 , , an ) = 1 páronként relatív prímek, ha ∀i < j : (ai , a j ) = 1 (1 ≤ i, j ≤ n) T ÉTEL 1.33 d = (a, b) ⇒ ∃m, n ∈ Z : d = am + bn T ÉTEL 1.34 d ∈ N+ , a, b, ∈ Z nem mindkettö 0. Az alábbi állítasok ekvivalensek: 1. d = (a, b) 2. d = min {ax +

by : x, y ∈ Z, ax + by > 0} 3. d közös osztó és ∀c közös osztóra c | d T ÉTEL 1.35 (LNKO TULAJDONSÁGAI ). 1. ∀c ∈ N+ : (ca, cb) = c(a, b) 2. (a, c) = (b, c) = 1 ⇒ (ab, c) = 1 3. a, b, c ∈ Z : (a, b) = (b, a) = (a, −b) = (a, b + ac) 4. c | ab, (a, c) = 1 ⇒ c | b T ÉTEL 1.36 a, b ∈ N+ a = bq1 + r1 b = r1 q2 + r2 r1 = r2 q3 + r3 . . rk−2 = rk−1 qk + rk rk−1 = rk qk+1 0 < r1 < b 0 < r2 < r1 0 < r3 < r2 . . 0 < rk < rk−1 A fenti egyenletek sorozata véges és rk = (a, b) 1.4 1.4 Lineáris diofantoszi egyenletek 3 Lineáris diofantoszi egyenletek T ÉTEL 1.41 Az ax + by = m egyenlet 1. megoldható ⇔ (a, b) | m 2. ha x0 , y0 jó megoldás ⇒ az összes megoldás: x = x0 + b k, (a, b) y = y0 − a k (a, b) T ÉTEL 1.42 a, b > 0, ax + by = m pozitív megoldásainak száma egyenlő azon k értékek számával, melyekre −(a, b) xb0 < k < (a, b) ya0 1.5 Prímszámok D EFINÍCIÓ 1.51 A p > 1

egészt felbonthatatlannak (irreducibilisnek) nevezzük, ha p = ab ⇒ a vagy b egység. Megjegyzés: ezzel ekvivalens: p > 1 felbonthatatlan, ha 1-en és önmagán kívül nincs pozitív osztója. D EFINÍCIÓ 1.52 A p > 1 egész prím, ha p | ab ⇒ p | a vagy p | b. T ÉTEL 1.53 p ∈ N prím ⇔ p felbonthatatlan. L EMMA 1.54 n > 1 ⇒ van felbonthatatlan osztója. T ÉTEL 1.55 (S ZÁMELMÉLET ALAPTÉTELE ) ∀n > 1 egész egyértelműen előáll prímek nem csökkenő sorozatának szorzataként. D EFINÍCIÓ 1.56 n > 1, n kanonikus alakja: n = pα1 1 · . · pαr r , ahol αi > 0 (i = 1, , r) (p1 < p2 < · · · < pr ) T ÉTEL 1.57 ( KANONIKUS ALAKRÓL ) β β 1. a = pα1 1 · · pαr r -nek d osztója ⇔ d = p1 1 · · pr r 0 ≤ βi ≤ αi 4 2. a osztóinak száma: δ(a) = (α1 + 1)(α2 + 1) · · (αr + 1) β β 3. a = pα1 1 · · pαr r (αi ≥ 0), b = p1 1 · · pr r (βi ≥ 0) r (a, b) = ∏ pi min(αi ,βi )

i=1 r [a, b] = ∏ pi max(αi ,βi ) i=1 T ÉTEL 1.58 (n! KANONIKUS ALAKJA )  ∞  n ⇒ pe k n! (pe | n!, de pe+1 - n!) 1. p prím e = ∑ k p k=1  ∞  n ep 2. n! = ∏ p , ahol e p = ∑ k p≤n k=1 p D EFINÍCIÓ 1.59 a, b ∈ Z legkisebb közös többszöröse az a legkisebb c ≥ 0, c ∈ Z, melyre a | c, b | c Jelölés: [a, b] = c T ÉTEL 1.510 (LKKT TULAJDONSÁGAI ). 1. [0, 0] = 0, [a, 0] = 0, [a, a] = |a| 2. a | b ⇒ [a, b] = |b| 3. [a, b] = n ∈ N: • a | n, b | n • a | m, b | m ⇒ n | m 4. [a, b] (a, b) = |a, b| T ÉTEL 1.511 (L AME ) A legnagyobb közös osztó megtalálásában az euklidészi algoritmusban szükséges lépések száma ≤ 5· a kisebbik szám számjegyeinek a száma. 2 Kongruenciák D EFINÍCIÓ 2.012 Ha a ∈ Z és m ∈ Z {0}, akkor a-nak m-mel vett (legkisebb nemnegatív) osztási maradékát a mod m jelöli. 2.1 Kongruenciák tulajdonságai 5 D EFINÍCIÓ 2.013 j k x x, y ∈ R, y 6= 0 x mod y := x − |y| |y| D EFINÍCIÓ

2.014 m 6= 0, m ∈ Z Azt mondjuk, hogy a kongruens b-vel modulo m, ha a mod m = b mod m Jelölés: a ≡ b (mod m), a ≡ b (m) 2.1 Kongruenciák tulajdonságai T ÉTEL 2.11 1. a ≡ b (mod m) ⇔ a ≡ b (mod − m) 2. ∀a, b ∈ Z : a ≡ b (mod 1) 3. a ≡ b (mod m), b ≡ a (mod m), a − b ≡ 0 (mod m), m | b − a ekvivalensek 4. a ≡ b (mod m), b ≡ c (mod m) ⇒ a ≡ c (mod m) ⇒ a "≡" (mod m) ekvivalenciareláció (reflexív, szimmetrikus, tranzitív) 5. a ≡ b (mod m) ⇔ a ≡ b + mq (mod m) (q ∈ Z) 6. a ≡ b (mod m), c ≡ d (mod m) ⇒ • a ± c ≡ b ± d (mod m) • ac ≡ bd (mod m) ⇒ a ≡ b (mod m) ⇒ • a + c ≡ b + c (mod m) • ac ≡ bc (mod m) • an ≡ bn (mod m) (n ∈ N+ ) ⇒ f tetszőleges egész együtthatós polinom ( f ∈ Z [x]), és a ≡ b (mod m) ⇒ f (a) ≡ f (b) (mod m) T ÉTEL 2.12 ( KONGRUENCIÁK KAPCSOLATA ) 1. a ≡ b (mod m), d | m ⇒ a ≡ b (mod d) 2. a ≡ b (mod m), c 6= 0 ⇒ ac ≡ bc (mod mc) 2.2

Maradékosztályok, maradékrendszerek 3. ax ≡ bx (mod m) ⇔ a ≡ b (mod 6 m (x,m) ) 4. ax ≡ bx (mod m), (x, m) = 1 ⇒ a ≡ b (mod m) 5. a ≡ b (mod mi ), i = 1, 2, , r ⇔ a ≡ b (mod [m1 , , mr ]) 2.2 Maradékosztályok, maradékrendszerek D EFINÍCIÓ 2.21 Az a-val kongruens (mod m) számok halmazát az a által reprezentált maradékosztálynak nevezzük. Jelölés: [a]m , [a] (mod m), (a)m , (a) (mod m), [a] , (a), a D EFINÍCIÓ 2.22 modulo m teljes maradékrendszer m szám halmaza, melyben minden maradékosztályból van reprezentáns. L EMMA 2.23 a ≡ b (mod m) ⇒ (a, m) = (b, m) D EFINÍCIÓ 2.24 modulo m redukált maradékrendszer m-hez relatív prím, (mod m) inkongruens egészek olyan halmaza, mely ϕ(m) elemű. Á LLÍTÁS 2.25 1. T ⊆ Z tmrsz (mod m) ⇔ • |T | = m • ri , r j ∈ T : ri 6≡ r j (mod m) 2. R ⊆ Z rmrsz (mod m) ⇔ • |R| = ϕ(m) • ri , r j ∈ R : ri 6≡ r j (mod m) • (ri , r j ) = 1 (∀i ∈ R) T ÉTEL 2.26 (a, m) =

1 és {r1 , . , rk } teljes/redukált mrsz (mod m) ⇒ {ar1 , . , ark } is teljes/redukált mrsz (mod m) 2.3 Euler- és Fermat-tételek 2.3 7 Euler- és Fermat-tételek T ÉTEL 2.31 ( KIS -F ERMAT- TÉTEL ) • p prím ⇒ a p ≡ a (mod p) • p prím , (a, p) = 1 ⇒ a p−1 ≡ 1 (mod p) T ÉTEL 2.32 (E ULER -F ERMAT- TÉTEL ) (a, m) = 1 ⇒ aϕ(m) ≡ 1 (mod m) Á LLÍTÁS 2.33 (m, n) = 1 ⇒ ϕ(m, n) = ϕ(m)ϕ(n) Á LLÍTÁS 2.34 ϕ(pα ) = pα − pα−1 = pα (1 − 1p ) ⇒ n = pα1 1 · . · pαr r ⇒ ϕ(n) = n ∏ri=1 (1 − 1p ) 2.4 Moduláris aritmetika D EFINÍCIÓ 2.41 • [a]m + [b]m := [a + b]m • [a]m · [b]m := [ab]m P ÉLDA 2.42 (mod 5) művelettáblák + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 és ∗ 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 Á LLÍTÁS 2.43 A (mod m) maradékosztályok a fenti két művelettel kommutatív egységelemes gyűrűt adnak. Ha m prím ⇒ a

mardékosztályok testet adnak. 8 D EFINÍCIÓ 2.44 [a]m inverze [ā]m : [a]m · [ā]m = [1]m ([a]m invertálható, ha ∃ inverze) −1 (mod m) Jelölés: [a]−1 m , a aā ≡ 1 (mod m) T ÉTEL 2.45 1. a invertálható (mod m) ⇔ (a, m) = 1 2. a invertálható (mod m) ⇒ (mod m) egyértelmű 3 Lineáris kongruenciák 3.1 Lineáris kongruenciák megoldása T ÉTEL 3.11 1. ax ≡ b (mod m) megoldható ⇔ (a, m) | b 2. a megoldások száma: (a, m) Megjegyzés: ax ≡ b (mod m) ⇔ ax + my = b T ÉTEL 3.12 (W ILSON ) 1. p prím ⇒ (p − 1)! ≡ −1 (mod p) 2. m = 4 ⇒ (m − 1)! ≡ 2 (mod m) 3. m > 4 ⇒ (m − 1)! ≡ 0 (mod m) ⇒ m > 1 prím ⇔ (m − 1)! ≡ −1 (mod m) 3.2 Lineáris kongruenciarendszerek T ÉTEL 3.21 1. x ≡ c1 (mod m1 ) x ≡ c2 (mod m2 ) 2. ∃! (mod [m1 , m2 ])  megoldható ⇔ (m1 , m2 ) | c2 − c1 9 T ÉTEL 3.22 (K ÍNAI MARADÉKTÉTEL ) m1 , . , mr > 0 páronként relatív prímek, a1 , . , ar ∈ Z ekkor az

x ≡ a1 x ≡ a2 x ≡ ar  (mod m1 )    (mod m2 )  szimultán lineáris kongruenciarendszer megoldható .  .   ∃! mo. (mod [m1 , , mr ]) (mod mr )  azaz ∀ mo. x = x0 + km1 · · mr 4 (k ∈ Z) alakú Magasabb fokú kongruenciák 4.1 Magasabb fokú kongruenciák megoldása T ÉTEL 4.11 Tetszőleges n-edfokú polinom kongruens egy legfeljebb p−1-edfokú polinommal (mod p), ha p prím. D EFINÍCIÓ 4.12 A k egész az f (x) ≡ 0 (mod m) polinom kongruencia egy megoldása, ha f (k) ≡ 0 (mod m). T ÉTEL 4.13 f (x) = an xn + an−1 xn−1 + . + a1 x + a0 egészegyütthatós ⇒ f (x + y) = f (x) + y f 0 (x) + y2 g(x, y) Ezt felhasználva: f (a + t p) = f (a) + t p f 0 (a) + t 2 p2 g(a,t p) ≡ f (a) + t p f 0 (a) (mod p2 ) Ha f (a) ≡ 0 (mod p) és f (a + t p) ≡ 0 (mod p2 ), akkor p-vel osztva: t f 0 (a) ≡ −( f (a)/p) (mod p) és ennek a lineáris kongruenciának egyetlen megoldása van. T ÉTEL 4.14 Legyen a az f (x) ≡ 0 (mod pr

) egy megoldása. 1. p - f 0 (a) ⇒ f (x) ≡ 0 (mod pr+1 ) egyetlen megoldása x = a + pr t, ahol t az egyetlen megoldása a pr t f 0 (a) ≡ − f (a) (mod pr+1 ) kongruenciának. 2. p | f 0 (a) és pr+1 | f (a) ⇒ f (x) ≡ 0 (mod pr+1 ) megoldásainak száma p, és ezek alakja x ≡ a + pr t (mod pr+1 ), t tetszőleges. 4.2 Polinomok modulo prím 10 3. p | f 0 (a) és pr+1 - f (a) ⇒ f (x) ≡ 0 (mod pr+1 ) nem oldható meg úgy, hogy x ≡ a (mod pr ) legyen. 4.2 Polinomok modulo prím T ÉTEL 4.21 Ha f n-edfokú polinom, p prím és f nem mindegyik együtthatója osztható pvel, akkor az f (x) ≡ 0 (mod p) kongruenciának legfeljebb n megoldása van (mod p). T ÉTEL 4.22 F : Z p Z p ⇒ ∃ f max(p − 1)-edfokú polinom : F(x) ≡ f (x) (mod p) ∀x T ÉTEL 4.23 f (x) ≡ 0 (mod p), f n-edfokú, főegyütthatója 1 f -nek pontosan n különböző megoldása van ⇔ f (x) az x p − x tényezője. x p − x = f (x) · q(x) + p · s(x), deg q = p − n, deg s

< n Követekezmény: d | p − 1 ⇒ xd ≡ 1 (mod p) kongruenciának d különböző megoldása van. 5 Rend, hatványmaradékok 5.1 Rend D EFINÍCIÓ 5.11 m > 0, m, a ∈ Z, (a, m) = 1 Azt mondjuk, hogy a rendje h, ha ah ≡ 1 (mod m), de ak 6≡ 1 (mod m), ha 0 < k < h Jelölés: ordm a = h, om (a) = h T ÉTEL 5.12 (R END TULAJDONSÁGAI ) 1. ordm a = h ⇒ ak ≡ 1 (mod m) ⇔ h | k ⇒ (a, m) = 1 ⇒ ordm a | ϕ(m) ⇒ (a, m) = 1, ai ≡ a j (mod m) ⇔ i ≡ j (mod ordm a) 2. ordm a = h ⇒ ordm ak = h (h,k) D EFINÍCIÓ 5.13 g primitív gyök (mod m), ha ordm g = ϕ(m) 5.2 Négyzetes (kvadratikus) maradékok 11 T ÉTEL 5.14 m-nek (m > 1) pontosan akkor van primitív gyöke, ha m = 2 vagy m = 4 vagy m = pα vagy m = 2 · pα , ahol p páratlan prím és α > 0. T ÉTEL 5.15 a (mod m) primitív gyökök száma ϕ(ϕ(m)). D EFINÍCIÓ 5.16 p prím , (a, p) = 1 és xn ≡ a (mod p)-nek van megoldása, akkor a n. hatványmaradék D EFINÍCIÓ 5.17 g

primitív gyök (mod m), (a, m) = 1 és gn ≡ a (mod m) ⇒ indg a = n (n a-nak g alapú indexe) (1 ≤ n ≤ ϕ(m)). Megjegyzés: az index ugyanúgy működik, mint a logaritmus. T ÉTEL 5.18 p prím (a, p) = 1 a xn ≡ a (mod p) kongruenciának p−1 (n, p − 1) | indg a (n, p − 1) megoldása van a (n,p−1) ≡ 1 (mod p) ⇔ ⇔ p−1 0 megoldása van (n, p − 1) - indg a a (n,p−1) 6≡ 1 (mod p) 5.2 Négyzetes (kvadratikus) maradékok D EFINÍCIÓ 5.21 (a, m) = 1, a négyzetes (kvadratikus) maradék/nemmaradék, ha x2 ≡ a (mod m)nek van/nincs megoldása. D EFINÍCIÓ 5.22   p páratlan prím, ekkor ap -t Legendre-jelnek (Legendre-szimbólumnak) nevezzük és a következőképp definiáljuk:     1, akvadratikus maradék a −1, akvadratikus nemmaradék =  p 0 a ≡ 0 (mod p) T ÉTEL 5.23 (A L EGENDRE - JEL TULAJDONSÁGAI ) p páratlan prím   p−1 1. ap ≡ a 2 (mod p) 2. a kvadratikus maradékok száma (mod p) p−1 2 5.2 3. Négyzetes

(kvadratikus) maradékok       b ab a p · p = p ,   a1 p 4. a ≡ b (mod p) ⇒   a p =  2 = 1,  5. (a, p) = 1 ⇒ 6.   1 p = 1,  a p −1 p  = (−1) ·.·   ak p 12 =  a1 ,. ,ak p    b p  =   =  1, p = 4k + 1 −1, p = 4k − 1 a2 b p p−1 2 b p ⇒ x2 + 1 ≡ 0 (mod p) megoldható, ha p = 4k + 1, nem megoldható ha p =   p−1 4k − 1, a megoldás ± 2 ! T ÉTEL 5.24 (G AUSS - LEMMA ) (a, p) = 1, tekintsük a, 2a, . , p−1 2 a számok legkisebb abszolútértékű maradékát (mod p)  és  legyen m a negatívak száma. a Ekkor p = (−1)m T ÉTEL 5.25 p páratlan prím p−1 2 1. (a, 2p) = 1 ⇒ 2.   2 p = (−1)   a p = (−1)   ai ∑ p i=1 p2 −1 8 L EMMA 5.26 a, b páratlanok, (a, b) = 1 b−1   a−1   2 2 a−1 b−1 ai bj · =∑ +∑ 2 2 i=1 b j=1 a T ÉTEL 5.27 (G AUSS - FÉLE KVADRATIKUS RECIPROCITÁSI TÉTEL ).     p−1 q−1 q p p, q páratlan prím (p 6= q) ⇒ q · p = (−1)

2 · 2 ⇒   p q p q =   q p = − q p  ⇔ p vagy q 4k + 1 alakú p és q 4k + 3 alakúak 13 D EFINÍCIÓ 5.28
m > 1 páratlan, m = pk11 · . · pkr r , (a, m) = 1 ekkor ma -t Jacobi-jelnek (Jacobiszimbólumnak) nevezzük és a következőképp definiáljuk: a m =  a p1 k1 ·.·  a pr kr Megjegyzések: • m prím ⇒ a Jacobi-jel azonos a Legendre-jellel
• ma  = 1 nem jelenti, hogy x2 ≡ a (mod m) megoldható, csak ha ∀p | m-re a p =1 T ÉTEL 5.29 (A JACOBI - JEL TULAJDONSÁGAI ) n, m > 1, (a, m) = (b, m) = 1


1. ma · mb = ab m


a 2. ma · na = mn 3. 2 m
= (−1) m2 −1 8 4. a ≡ b (mod m) ⇒
m−1 2 5. −1 m = (−1) a m
= b m
6. m, n páratlanok, (m, n) = 1 ⇒ m n
· n m
= (−1) m−1 n−1 2 · 2 Á LLÍTÁS 5.210 (M ODULÁRIS NÉGYZETGYÖKVONÁS ) n = pq, p, q páratlan prímek x2 ≡ a (mod n) megoldható ⇒ 4 különböző megoldás van 6 6.1 Számelméleti függvények

Függvénydefiníciók, multiplikativitás, additivitás D EFINÍCIÓ 6.11 f függvény számelméleti függvény, ha Z+ ⊆ D f D EFINÍCIÓ 6.12 f számelméleti függvény 6.1 Függvénydefiníciók, multiplikativitás, additivitás 14 • multiplikatív, ha f (nm) = f (n) f (m) ∀(n, m) = 1 • additív, ha f (nm) = f (n) + f (m) ∀(n, m) = 1 • teljesen multiplikatív, ha f (nm) = f (n) f (m) ∀n, m • teljesen additív, ha f (nm) = f (n) + f (m) ∀n, m Á LLÍTÁS 6.13 1. ∃n : f (n) 6= 0 és f multiplikatív ⇒ f (1) = 1 2. g additív ⇒ g(1) = 0 T ÉTEL 6.14 Multiplikatív és additív függvényeket elég csak prímhatványokra, teljesen multiplikatív és teljesen additív függvényeket pedig csak prímekre ismerni: ! f mult. ha f ∏ pαi i = ∏ f (pαi i ) ∀i ft t. mult ha ft ∏ pαi i ∀i g add. ha g ∏ pαi i ! ∀i gt t. add ha gt ∏ pαi i ∀i ! ∀i = ∏ ft (pi )αi ∀i = ∑ g(pαi i ) ! ∀i = ∑ gt (pi )αi ∀i T

ÉTEL 6.15 Két multiplikatív függvény szorzata és hányadosa is multiplikatív. D EFINÍCIÓ 6.16 • d(n) := n osztóinak száma • σ(n) := n osztóinak összege • ν(n) := n prímtényezőinek száma • κ(n) := n különböző prímtényezőinek száma • ϕ(n) := n-nél kisebb n-hez relatív prímek száma 6.2 Összegzések 15  n=1  1, r (−1) , n = p1 , . , pr pi 6= p j , ha i 6= j • µ(n) :=  0, egyébként Á LLÍTÁS 6.17 d, σ, ϕ, µ multiplikatív függvények T ÉTEL 6.18 n = pα1 1 · . · pαr r r 1. d(n) = ∏(αi + 1) i=1 pαi i +1 − 1 2. σ(n) = ∏ i=1 pi − 1 r r 3. ϕ(n) = ∏(pαi i − pαi i −1 ) i=1 6.2 Összegzések T ÉTEL 6.21 ∑ ϕ(d) = n d|n D EFINÍCIÓ 6.22 • f számelméleti függvény összegzési függvénye f + , melyre: f + (n) = ∑ f (d) d|n • f számelméleti függvény megfordítási függvénye f − , melyre: f (n) = ∑ f − (d) (( f − )+ = d|n f) Á LLÍTÁS 6.23 f −

egyértelműen létezik Á LLÍTÁS 6.24 f multiplikatív ⇔ f + is multiplikatív Á LLÍTÁS 6.25 + µ (n) = e(n) :=  1, ha n = 1 0, ha n > 1 6.2 Összegzések 16 T ÉTEL 6.26 (M ÖBIUS - FÉLE INVERZIÓS / MEGFORDÍTÁSI FORMULA ) n g(n) = ∑ f (d) ⇔ f (n) = ∑ µ · g(d) d d|n d|n D EFINÍCIÓ 6.27 f és g számelméleti függvények konvolúcióját a következőképpen definiáljuk: n ( f ? g)(n) := ∑ f (d) · g d d|n Megjegyzés: • f+ = f ?1 • f− = f ?µ T ÉTEL 6.28 A ? reláció kommutatív, asszociatív, egységelemes: e(n) =  1, ha n = 1 0, ha n > 1 D EFINÍCIÓ 6.29 (D IRICHLET- SOR ) ∞ f (n) ∑ ns (azon s helyeken, ahol konvergens) n=1 D EFINÍCIÓ 6.210 (R IEMANN - FÉLE ZETA ∞ 1 ζ(s) = ∑ s (abszolót konvergens, s > 1) n=1 n FÜGGVÉNY ). T ÉTEL 6.211 (E ULER - FÉLE SZORZATALAK )   ∞ 1 1 −1 ζ(s) = ∑ s = ∏ 1 − s p n=1 n p prím T ÉTEL 6.212 f , g, h számelméleti függvények és F, G, H

Dirichlet-soraik abszolút konvergensek, ekkor h = f ?g ⇒ H = F ·G T ÉTEL 6.213 (VÖLGYTÉTEL ) ∀K ∈ N+ : ∃∞ sok n : d(n − 1) − d(n) > K, d(n + 1) − d(n) > K 6.3 Minimális univerzális kitevő (exponens) 17 T ÉTEL 6.214 (H EGYTÉTEL ) ∀K ∈ N+ : ∃∞ sok n : d(n) − d(n − 1) > K, d(n) − d(n + 1) > K T ÉTEL 6.215 n ∑ d(i) i=1 n − ln n < 1 6.3 Minimális univerzális kitevő (exponens) D EFINÍCIÓ 6.31 λ > 0 minimális univerzális kitevő (mod n), ha λ a legkisebb olyan egész, hogy aλ ≡ 1 (mod n) ∀(a, n) = 1 esetén (szokás λ(n) függvényként írni) Megjegyzés: • ha ∃ primitív gyök ⇒ λ(n) = ϕ(n) • ha ordn a = k ⇒ k | λ(n) L EMMA 6.32 ordn a = k, ordn b = l ⇒ ∃g : ordn g = [k, l] L EMMA 6.33 M a maximális rend ⇒ M = λ(n), ∃λ(n) rendű elem. T ÉTEL 6.34 p prím ⇒ ∃ primitív gyök (mod p)