1. Számelméleti alapismeretek, a számelmélet alaptétele. A prímszámelmélet elemei. A kongruencia fogalma, maradékosztályok, Euler−Fermat-tétel. Lineáris és magasabb fokú algebrai kongruenciák. Binom kongruenciák, kvadratikus kongruenciák.
Oszthatóság Definíció: (oszthatóság Z-ben) A 𝒃 egész szám osztható az 𝒂 egész számmal, ha az 𝒂𝒙 = 𝒃 egyenletek Z-ben megoldható, azaz 𝒂|𝒃 ⟺ ∃ 𝒙 ∈ 𝒁 ∶ 𝒂𝒙 = 𝒃 Definíció: Ha egy szám minden számnak osztója, akkor egységnek nevezzük. Tétel: Az egész számok körében két egység van, az 1 és a -1. Tétel: Ha 𝜀 é𝑠 𝛿 𝑒𝑔𝑦𝑠é𝑔𝑒𝑘 é𝑠 𝑏 𝑎, 𝑎𝑘𝑘𝑜𝑟 𝜀𝑏 𝛿𝑎 𝑖𝑠 𝑡𝑒𝑙𝑗𝑒𝑠ü𝑙. Tétel: (oszthatóság tulajdonságai) 1) reflexív, ∀ 𝑎, 𝑎|𝑎 2) nem szimmetrikus, ℸ∀𝑎∀𝑏, 𝑎|𝑏 ⟹ 𝑏|𝑎 3) tranzitív, ∀𝑎∀𝑏∀𝑐, 𝑎 𝑏⋀𝑏 𝑐 ⇒ 𝑎|𝑐 4) oszthatóság additív tulajdonsága, 𝑎|𝑏⋀𝑎|𝑐 ⟹ 𝑎|𝑏 + 𝑐 5) oszthatóság multiplikatív tulajdonsága, 𝑎|𝑏⋀𝑐|𝑑 ⟹ 𝑎𝑐|𝑏𝑑 6) ∀ 𝑎, 𝑎|0 7) 0|𝑎 ⟺ 𝑎 = 0 8) ∀ 𝑎, 1|𝑎 9) 𝑎|𝑏⋀𝑎|𝑐 ⟹ 𝑎|𝑏 − 𝑐 10) 𝑎|𝑏⋀𝑎 ∤ 𝑐 ⟹ 𝑎 ∤ 𝑏 ∓ 𝑐 11) 𝑎 𝑏 ⟹ 𝑎 𝑏𝑐 12) 𝑎 𝑏 ⟹ 𝑎𝑐 𝑏𝑐
Maradékos osztás Tétel: (Euklidészi osztás tétele, maradékos osztás tétele) ∀𝑎, 𝑏 ∈ 𝑍, 𝑏 ≠ 0 , ∃! 𝑞, 𝑟 ∈ 𝑍, 𝑎 = 𝑏𝑞 + 𝑟, 0 ≤ 𝑟 < 𝑏 Tétel: Tetszőleges 𝑎 é𝑠 𝑏 ≠ 0 𝑒𝑔é𝑠𝑧 𝑠𝑧á𝑚𝑜𝑘𝑜𝑧 léteznek olyan egyértelműen meghatározott 𝑞 é𝑠 𝑟 egész számok, melyekre |𝑏| |𝑏| 𝑎 = 𝑏𝑞 + 𝑟 é𝑠 − <𝑟≤ 2 2 Tétel: Legyen 𝑡 > 1 rögzített egész. Ekkor bármely 𝐴 pozitív egész egyértelműen felírható az alábbi alakban: 𝐴 = 𝑎𝑛 𝑡 𝑛 + 𝑎𝑛−1 𝑡 𝑛 −1 + ⋯ + 𝑎1 𝑡1 + 𝑎0 , 𝑎𝑜𝑙 0 ≤ 𝑎𝑖 < 𝑡 é𝑠 𝑎𝑛 ≠ 0. Tétel: (Euklidészi algoritmus) Euklidészi osztások sorozatát Euklidészi algoritmusnak nevezzük az 𝑎 é𝑠 𝑏 𝑏 ≠ 0 𝑒𝑔é𝑠𝑧 𝑠𝑧á𝑚𝑜𝑘𝑜𝑛 𝑎 = 𝑏𝑞 + 𝑟, 0 ≤ 𝑟 < 𝑏 ; 𝑏 = 𝑟𝑞1 + 𝑟1 , 0 ≤ 𝑟1 < 𝑟 … … . 𝑟𝑛−2 = 𝑟𝑛−1 𝑞𝑛 + 𝑟𝑛 𝑟𝑛 𝑙𝑛𝑘𝑜 𝑟𝑛−1 = 𝑟𝑛 𝑞𝑛+1 Mivel |𝑏| > 𝑟 > 𝑟1 … . >= 0 ezért az algoritmus véges, a maradék bizonyos számú lépés után 0 lesz.
Legnagyobb közös osztó Definíció: ! 𝑎, 𝑏 ∈ 𝑍, és legalább az egyik zérustól különböző. Az a, b legnagyobb közös osztójának nevezünk egy 𝑑 ∈ 𝑍 elemet, amelyre i) 𝑑 𝑘ö𝑧ö𝑠 𝑜𝑠𝑧𝑡ó, 𝑑|𝑎 ⋀ 𝑑|𝑏 ii) d a többi közös osztó többszöröse; (𝑑´|𝑎 ∧ 𝑑´|𝑏) ⟹ 𝑑´|𝑑 Jelölés (a,b)=d 1
Definíció: Ha (a,b)=1, akkor az a és b egész számokat relatív prímeknek nevezzük. Definíció: Az 𝑛1 , 𝑛2 , … . . 𝑛𝑘 nem mind zérus egész számokat relatív prímeknek nevezzük, ha lnko-jut 1 (𝑛1 , 𝑛2 , … . . 𝑛𝑘 ) = 1, ha továbbá bármely két eleme különböző relatív prím, akkor páronként relatív prímek, azaz 𝑛𝑖 , 𝑛𝑗 = 1, 𝑚𝑖𝑛𝑑𝑒𝑛 1 ≤ 𝑖 ≠ 𝑗 ≤ 𝑘. Definíció: 𝐴𝑧 𝑎 é𝑠 𝑏 számok kitüntetett közös osztója 𝛿, ha 𝛿 𝑎, 𝛿 𝑏 𝑎 𝑒𝑔𝑦 𝑐 − 𝑟𝑒 𝑐|𝑎, 𝑐|𝑏 𝑡𝑒𝑙𝑗𝑒𝑠ü𝑙, 𝑎𝑘𝑘𝑜𝑟 𝑐|𝛿 Tétel: Bármely egész számnak létezik kitüntetett közös osztója. Tétel: 𝐻𝑎 𝑐 > 0, 𝑎𝑘𝑘𝑜𝑟 (𝑐𝑎, 𝑐𝑏) = 𝑐(𝑎, 𝑏) Tétel: Az a,b b≠0 egész számok lnko-ját a rajtuk végrehajtott Euklidészi algoritmusban az utolsó osztó (𝑟𝑛 ) adja. Tétel: (lnko tulajdonságai) ∀ 𝑎, 𝑏, 𝑐, 𝑑 ∈ 𝑍 1) a, b , c = a, b, c assz. 2) 𝑎, 𝑏 = 𝑏, 𝑎 kom. 3) (𝑎, 𝑎) = 𝑎 4) (𝑎, 𝑏) = (𝑎 + 𝑏𝑐, 𝑏) 5) (𝑎, 𝑏)𝑐 = (𝑎𝑐, 𝑏𝑐) 𝑎 𝑏 6) 𝑎 ,𝑏 , 𝑎,𝑏 = 1
7) ∃𝑥, 𝑦 ∈ 𝑍: 𝑎𝑥 + 𝑏𝑦 = 𝑎, 𝑏 , az lnko mindig előállítható a két egész szám lineáris kombinációjaként 8) (𝑎, 𝑏) = 1 é𝑠 (𝑎, 𝑐) = 1, 𝑎𝑘𝑘𝑜𝑟 (𝑎, 𝑏, 𝑐) = 1 9) (𝑎|𝑏𝑐 é𝑠 𝑎𝑏 = 1) 𝑎𝑘𝑘𝑜𝑟 𝑎|𝑐 , á𝑙𝑡𝑎𝑙á𝑛𝑜𝑠 𝑝𝑟í𝑚𝑡𝑢𝑙𝑎𝑗𝑑𝑜𝑛𝑠á𝑔 10) (𝑎, 𝑏) = |𝑎| ⟺ 𝑎|𝑏 Definíció: ! 𝑎, 𝑏 ∈ 𝑍, és legalább az egyik zérustól különböző. Az a, b legkisebb közös többszörösének nevezünk azt az m ∈ 𝑍 számot, amelyre i) m 𝑘ö𝑧ö𝑠 𝑡ö𝑏𝑏𝑠𝑧ö𝑟ö𝑠, 𝑎|𝑚 ⋀ 𝑏|𝑚 ii) a többi közös többszörös osztója; (𝑎|𝑚´ ∧ 𝑏|𝑚´) ⟹ 𝑚|𝑚´ Jelölés [a,b]=m Tétel: (lkkt tulajdonságai) ∀ 𝑎, 𝑏, 𝑐, 𝑑 ∈ 𝑍 1) a, b , c = a, b, c assz. 2) [a,b] = [𝑏, 𝑎] kom. 3) [a,a] = a 4) [a,b]c = [ac,bc] 𝑎𝑏 5) 𝑎, 𝑏 = (𝑎,𝑏) Definíció: (valódi osztó) A b egész szám egységtől és +- b –től különböző osztóit valódi osztóknak nevezzük. 𝑎 𝑏 ⋀ℸ 𝑎~𝑎 ⋀ 𝑎~𝑏 ⟹ 𝒂 𝑣𝑎𝑙ó𝑑𝑖 𝑜𝑠𝑧𝑡ó𝑗𝑎 𝑏 − 𝑛𝑒𝑘 Definíció: (faktorizáció) Ha egy nem zérus b egész számot felírunk 𝒃 = 𝒂𝒄 (𝑎, 𝑐 ∈ 𝑍) alakban, akkor 𝒃 egy faktorizációját kapjuk. Ha itt 𝒂 é𝑠 𝒄 egyike sem egység (±1), 𝑎𝑘𝑘𝑜𝑟 𝑏 = 𝑎𝑐 valódi faktorizáció. Definíció: (törzsszám) A zérustól és egységtől különböző q egész számot törzsszámnak vagy irreducibilis (felbonthatlan) számnak nevezzük, ha nincs valódi faktorizációja. Ellenkező esetben a összetett szám. 2
Definíció: (prímszám) A zérustól és egységtől különböző b egész számot prímszámnak nevezzük, ha prímtulajdonságú, azaz valahányszor osztója egy szorzatnak mindannyiszor osztója a szorzat legalább egy tényezőjének. 𝑝 ∈ 𝑍 𝑝 ≠ 0, ∓1 𝑝𝑟í𝑚𝑠𝑧á𝑚 ⟺ [𝑝|𝑎𝑏 ⟹ 𝑝|𝑎 ⋁ 𝑝|𝑏] Tétel: Egy p egész szám akkor és csakis akkor prímszám, ha törzsszám. Tétel: (számelmélet alaptétele) Minden összetett egész szám sorrendtől eltekintve egyértelműen bontható fel prímszámok szorzatára.
Kanonikus alak Tétel: Minden n>1 egész szám felírható 𝒏=
𝒓 𝜶 𝜶 𝜶 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓
𝜶
=
𝒑𝒊 𝒊 𝒊=𝟏
𝜶
alakban, ahol 𝑝1 , … 𝑝𝑟 különböző (pozitív) prímek és 𝛼𝑖 > 0 egész. Ez a felírás a 𝒑𝒊 𝒊 prímhatványtényezők sorrendjétől eltekintve egyértelmű. Ezt az előállítást az 𝒏 szám kanonikus alakjának nevezzük. 𝜶
𝜶
𝜶
Tétel: Az 𝒏 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓 kanonikus alakú n számnak egy d pozitív egész akkor és csak akkor 𝜷 𝜷 𝜷 osztója, ha d kanonikus alakja 𝒅 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓 , ahol 0≤ 𝛽𝑖 ≤ 𝛼𝑖 , 𝑖 = 1,2, … 𝑟. Tétel: Legyen az 𝒂 é𝒔 𝒃 pozitív egészek kanonikus alakja 𝜶
𝜶
𝜷
𝜶
𝜷
𝜷
𝒂 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓 é𝒔 𝒃 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓 𝒂𝒉𝒐𝒍 𝜶𝒊 ≥ 𝟎, 𝜷𝒊 ≥ 𝟎. 𝑬𝒌𝒌𝒐𝒓 𝒎𝒊𝒏(𝜶𝟏 𝜷𝟏 ) 𝒎𝒊𝒏(𝜶𝟐 𝜷𝟐 ) 𝒎𝒊𝒏(𝜶𝒓 𝜷𝒓 ) 𝒑𝟐 . . 𝒑𝒓
(𝒂, 𝒃) = 𝒑𝟏
Tétel: Legyen az 𝒂 é𝒔 𝒃 pozitív egészek kanonikus alakja 𝜶
𝜶
𝜷
𝜶
𝜷
𝜷
𝒂 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓 é𝒔 𝒃 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 . . 𝒑𝒓 𝒓 𝒂𝒉𝒐𝒍 𝜶𝒊 ≥ 𝟎, 𝜷𝒊 ≥ 𝟎. 𝑬𝒌𝒌𝒐𝒓 𝒎𝒂𝒙(𝜶𝟏 𝜷𝟏 ) 𝒎𝒂𝒙(𝜶𝟐 𝜷𝟐 ) 𝒎𝒂𝒙(𝜶𝒓 𝜷𝒓 ) 𝒑𝟐 . . 𝒑𝒓
[𝒂, 𝒃] = 𝒑𝟏
Tétel: Végtelen sok prímszám van. A prímszámok keresésére szolgál a eratoszthenészi szita. Tétel: Bármely n-re van egymást követő összetett szám. Definíció: Ikerprímek azok a prímek, amelyeknek kettő a különbsége. Pl.: 3,5 29,31 101,103 Tétel-Sejtés: Végtelen sok ikerprím van. (Top7 milen.prob.) Tétel: Legyen n>=2 tetszés szerinti természetes szám. A prímszámok sorozatában mindig található két olyan szomszédos prímszám, amelyeknek egymástól való eltérése legalább n. 𝑘
Sejtés: (Fermat sejtés) 22 + 1 alakú számok minden k értékére prímszámokat kapunk. Ez k=1,2,3,4 re igaz, de k=5-re már nem (Euler mutatta meg). {pl : n=0-ra 3, 1-re 5, 2-re 17, 3-ra 257, 4-re 65537} Tétel: Ha 2𝑚 + 1 prímszám, akkor 𝑚 = 2𝑛 Tétel: Az N oldalú szabályos sokszög pontosan akkor szerkeszthető meg, ha 𝑁 = 2𝑛 𝑝1 𝑝2 … 𝑝𝑘 , akkor a 𝑝𝑖 számok különböző Fermat prímek. 3
Definíció: Mersenne-féle prím 2𝑝 − 1 𝑎𝑙𝑎𝑘ú𝑎𝑘. {pl : n=2-re 3, 3-ra 7, 5-re 31, 7-re 127} Tétel: 2𝑝 − 1 prímszám, akkor p prím. Tétel: Ha n összetett szám, akkor 2𝑝 − 1 összetett. Tétel: Végtelen sok 𝟒𝒌 − 𝟏 alakú prímszám van. Tétel: (Dirichlet tétel) Ha 𝑎 é𝑠 𝑏 egymáshoz relatív prímszámok, akkor az 𝒂𝒌 + 𝒃 (k=1,2,…) végtelen számtani sorozatban végtelen sok prímszám van. 1 1 1 1 1 Tétel: A prímszámok reciprokaiból képezett 2 + 3 + 5 + 7 + ⋯ + 𝑝 + ⋯ végtelen sor minden határon túl nő, azaz divergens.
Eloszlással kapcsolatos tételek. Tétel: (Csebisev tétel) Ha 𝑛 ≥ 1, akkor n és 2n között biztos van prímszám. Tétel: Ha 𝑛 ≥ 2, akkor van 𝑛 − 1 utáni természetes szám, amelyek egyike sem prím. Tétel: 𝑝𝑛 n-edik prímszám 𝑝1 = 2, 𝑝2 = 3, 𝑝3 = 5, 𝑝𝑛 ~𝑛𝑙𝑛𝑛 Definíció: Legyen 𝝅 𝒙 𝑎𝑧 𝑥 𝑣𝑎𝑙ó𝑠 𝑠𝑧á𝑚𝑜𝑘𝑛á𝑙 𝑛𝑒𝑚 𝑛𝑎𝑔𝑦𝑜𝑏𝑏 𝑝𝑟í𝑚𝑠𝑧á𝑚𝑜𝑘 𝑠𝑧á𝑚𝑎. 𝑥
𝑥
Tétel: Található olyan 𝑐1 é𝑠 𝑐2 𝑝𝑜𝑧𝑖𝑡í𝑣 𝑣𝑎𝑙ó𝑠 𝑠𝑧á𝑚, 𝑎𝑚𝑒𝑙𝑦𝑟𝑒 𝑐1 𝑙𝑛𝑥 < 𝝅 𝒙 < 𝑐2 𝑙𝑛𝑥 𝑥
𝝅 𝒙
Vagyis 𝝅 𝒙 ~ 𝑙𝑛𝑥 (nagy prímszámtétel). Továbbá 𝐥𝐢𝐦𝒙⟶∞ 𝒙
𝒍𝒏𝒙
= 𝟏 (prímszámtétel).
Goldbach sejtés: Minden 2-nél nagyobb páros szám két prímszám összegére bontható. Minden 5-nél nagyobb páratlan szám három prímszám összegére bontható. Riemann sejtés: 𝜁 𝑠 =
1 ∞ 𝑛=1 𝑛 3
1
, 𝜁 𝑠 = 0 𝑒𝑔𝑦𝑒𝑛𝑙𝑒𝑡 𝑔𝑦ö𝑘𝑒𝑖 𝑎𝑧 𝑠 = 2 + 𝑖𝑡 𝑒𝑔𝑦𝑒𝑛𝑒𝑠𝑒𝑛 𝑣𝑎𝑛𝑛𝑎𝑘.
Kongruenciák Definíció: Legyenek 𝒂 é𝒔 𝒃 𝒆𝒈é𝒔𝒛 számok és 𝒎 𝒑𝒐𝒛𝒊𝒕í𝒗 𝒆𝒈é𝒔𝒛. Azt mondjuk, hogy a kongruens b-vel modulo m, ha 𝑚|𝑎 − 𝑏 . Vagyis: 𝑎 ≡ 𝑏 𝑚 : ⟺ 𝑚|𝑎 − 𝑏. m-et a reláció modulusának nevezzük. (m) helyett (mod m)-et is szokás írni. Tétel: ∀𝑎, 𝑏, 𝑐, 𝑑 ∈ 𝑍 𝑒𝑙𝑒𝑚𝑟𝑒 𝑡𝑒𝑙𝑗𝑒𝑠ü𝑙𝑛𝑒𝑘 𝑎 𝑘ö𝑣𝑒𝑡𝑘𝑒𝑧ő𝑘: 1) 𝑎 ≡ 𝑎 𝑚 , reflexív 2) 𝑎 ≡ 𝑏 𝑚 ⟹ 𝑏 ≡ 𝑎 𝑚 , szimmetria 3) [𝑎 ≡ 𝑏 𝑚 ⋀𝑏 ≡ 𝑐 𝑚 ] ⇒ 𝑎 ≡ 𝑐 𝑚 tranzitivitás 4) kompatibilitás mindkét művelettel 𝑎 ≡ 𝑏 𝑚 ⋀𝑐 ≡ 𝑑 𝑚
⇒𝑎+𝑐 ≡𝑏+𝑑 𝑚
[𝑎 ≡ 𝑏 𝑚 ⋀𝑐 ≡ 𝑑 𝑚 ] ⇒ 𝑎𝑐 ≡ 𝑏𝑑 𝑚 5) 𝑎 ≡ 𝑏 𝑚 ⟹ 𝑎 ± 𝑐 ≡ 𝑏 ± 𝑐 𝑚 6) 𝑎 ≡ 𝑏 𝑚 ⟹ 𝑎𝑐 ≡ 𝑏𝑐 𝑚 4
7) 𝑎 ≡ 𝑏 𝑚 ⟹ 𝑎𝑘 ≡ 𝑏 𝑘 𝑚 8) 𝑎𝑐 ≡ 𝑏𝑐 𝑚 ⟹ 𝑎 ≡ 𝑏
𝑚 (𝑚 ,𝑐)
Tétel: Ha 𝑎𝑐 ≡ 𝑏𝑐 𝑚 é𝑠 𝑎, 𝑐 = 1 ⟹ 𝑎 ≡ 𝑏 𝑚 Tétel:
(1) 𝑎 − 𝑏|𝑎𝑛 − 𝑏 𝑛 (2) 𝑎 + 𝑏|𝑎2𝑛+1 + 𝑏 2𝑛+1 (3) 𝑎 + 𝑏|𝑎2𝑛 − 𝑏 2𝑛
Definíció: A moduló m maradékos osztályok 0, 1, … 𝑚 − 1. Másképpen: Rögzített m modulus mellett az a-val kongruens elemek halmazát az a által reprezentált maradékosztálynak nevezzük. Definíció: Azokat a maradékosztályokat, amelyeknek az elemei m-hez relatív prímek, prímmaradékosztályoknak nevezzük. Definíció: Ha rögzített m modulus mellett minden maradékosztályból egy és csak egy elemet kiveszünk, az így kapott számokat modulo m teljes maradékrendszernek nevezzük. {jel.: TMR} Példa: A 7,12,21,30 TMR, mert (mod 4) 7~3,12~0, 21~1, 30~2 Tétel: Az 𝑎1 , 𝑎2 , 𝑎3 , … 𝑎𝑘 számok akkor és csakis akkor alkotnak teljes maradékrendszert (mod m), ha (1) 𝑘 = 𝑚 (2) 𝑎𝑖 ≢ 𝑎𝑗 (m) Tétel: Legyen 𝑟1 , 𝑟2 , 𝑟3 , … 𝑟𝑚 TMR modulo m, (a,m)=1 és b tetszőleges. Ekkor 𝑎𝑟1 + 𝑏, 𝑎𝑟2 + 𝑏, 𝑎𝑟3 + 𝑏, … 𝑎𝑟𝑚 + 𝑏 , 𝑖𝑠 𝑇𝑀𝑅 𝑚𝑜𝑑𝑢𝑙𝑜 𝑚. Tétel: 𝑎 ≡ 𝑏 𝑚 ⟹ 𝑎, 𝑚 = (𝑏, 𝑚) Definíció: Az (𝑎)𝑚 maradékosztályt modulo m redukált maradékosztálynak nevezzük, ha (𝑎, 𝑚) = 1 Definíció: Ha rögzített m modulus mellett minden redukált maradékosztályból egy és csak egy elemet kiveszünk, az így kapott számokat modulo m redukált maradékrendszernek nevezzük. {jel.: RMR} Példa:A {17,-5, 11,-11} RMR modulo 12 Definíció: Az 𝑎1 , 𝑎2 , 𝑎3 , … 𝑎𝑘 számok akkor és csakis akkor alkotnak redukált maradékrendszert (mod m), ha (1) 𝑘 = 𝜑(𝑚) (2) 𝑎𝑖 ≢ 𝑎𝑗 (m) (3) (𝑎𝑖 , 𝑚) = 1 Tétel: Legyen 𝑟1 , 𝑟2 , 𝑟3 , … 𝑟𝜑(𝑚 ) RMR modulo m, (a,m)=1 és b tetszőleges. Ekkor 𝑎𝑟1 ,
𝑎𝑟2 ,
𝑎𝑟3 , … 𝑎𝑟𝜑(𝑚 ) , 𝑖𝑠 𝑅𝑀𝑅 𝑚𝑜𝑑𝑢𝑙𝑜 𝑚.
Tétel: Az 𝑎1 , 𝑎2 , 𝑎3 , … 𝑎𝑘 (𝑚)teljes maradékrendszer, akkor 𝑎1 + 𝑐, 𝑎2 + 𝑐, 𝑎3 + 𝑐, … 𝑎𝑘 + 𝑐 (m) is TMR.
5
Tétel: 𝑎1 , 𝑎2 , 𝑎3 , … 𝑎𝑘 (𝑚) TMR (RMR) és (c,m)=1, akkor 𝑎1 𝑐, 𝑎2 𝑐, 𝑎3 𝑐, … 𝑎𝑘 𝑐 (m) is TMR (RMR). Definíció: (Euler-féle 𝝋 függvény) A 𝜑(𝑛)jelöli a 0,1,…n-1 sorozatban az n-hez relatív prímek számát. 𝑡 𝑡 Tétel: Az 𝝋(𝒏)számelméleti függvény multiplikatív. Továbbá, ha 𝑛 = 𝑝11 … 𝑝𝑘𝑘 , 1
akkor 𝜑 𝑛 = 𝑛 1 − 𝑝
1
1
… 1−𝑝
!a többit lásd a másik tételben
𝑘
Tétel: (Euler-Fermat tétel) Ha 𝑎, 𝑚 = 1, 𝑎𝑘𝑘𝑜𝑟 𝑎𝜑(𝑚 ) ≡ 1 (𝑚) Tétel: Ha 𝑎, 𝑝 ~1, 𝑎𝑧𝑎𝑧 𝑝 ∤ 𝑎, 𝑎𝑘𝑘𝑜𝑟 𝒂𝒑−𝟏 ≡ 𝟏 (𝒑) („kis” Fermat tétel egyik alakja), mindkét oldalt a-val szorozva: 𝐚𝐩 ≡ 𝐚 𝐩 („𝒌𝒊𝒔” 𝑭𝒆𝒓𝒎𝒂𝒕 𝒕é𝒕𝒆𝒍 𝒎á𝒔𝒊𝒌 𝒂𝒍𝒂𝒌𝒋𝒂). Tétel: (Nagy Fermat tétel) 𝑥 𝑛 + 𝑦 𝑛 = 𝑧 𝑛 n>2 nincs megoldása Z-ben. (n=1,2 esetén van).
Lineáris kongruenciák Definíció: Legyenek 𝑎 é𝑠 𝑏 egészek és 𝑚 pozitív egész. Ekkor az 𝒂𝒙 ≡ 𝒃(𝒎) kongruenciát lineáris kongruenciának nevezzük, és ennek egy megoldásán egy olyan 𝒔 egész számot értünk, amelyet az 𝒙 helyére beírva a kongruencia fennáll. Definíció: Legyen 𝒇 egy egész együtthatós polinom. Ekkor az 𝒇 𝒙 ≡ 𝟎 (m) kongruencia megoldásszámán egy modulo m TMR azon s elemeinek a számát értjük, amelyekre 𝑓 𝑠 ≡ 0 𝑚 . Tétel: Ha az 𝒂𝒙 ≡ 𝒃 𝒎 kongruencia akkor és csak akkor létezik megoldása, ha (𝒂, 𝒎)|𝒃 Tétel: Ha az 𝒂𝒙 ≡ 𝒃 𝒎 kongruencia megoldható, akkor a megoldásszáma (𝒂, 𝒎) Tétel: Legyen (𝑎, 𝑚) = 𝑑, 𝑚 = 𝑑𝑚1 és tegyük fel, hogy az s egész szám megoldása az 𝒂𝒙 ≡ 𝒃 𝒎 kongruenciának. Ekkor az 𝒔, 𝒔 + 𝒎𝟏 , 𝒔 + 𝟐𝒎𝟏 , … 𝒔 + 𝒅 − 𝟏 𝒎𝟏 számok páronként inkongruensek (modulo m), kielégítik a kongruenciát, és az összes megoldás ezek valamelyikével kongruens modulo m. Tétel: Ha (𝒂, 𝒎) = 𝟏, akkor az 𝒂𝒙 ≡ 𝒃 𝒎 kongruencia bármely 𝒃 esetén megoldható és a megoldásszáma 1. Megoldási módok: Végigpróbálgatás, Diofantikus egyenlettel, Euler-Fermat-tétellel, Ügyeskedések
Szimultán kongruencia rendszerek1 Definíció: Szimultán kongruenciarendszernek azt nevezzük, amikor ugyanarra az ismeretlenre egyidejűleg több, különböző modulus szerinti kongruencia feltételt is előírunk. 𝒇𝟏 𝒙 ≡ 𝟎 𝒎𝟏 , 𝒇𝟐 𝒙 ≡ 𝟎 𝒎𝟐 , … 𝒇𝒌 (𝒙) ≡ 𝟎 𝒎𝒌 ahol 𝒇𝟏 , 𝒇𝟐 , … 𝒇𝒌 egész együtthatós polinomok. Tétel: Az 𝒙 ≡ 𝒄𝟏 𝒎𝒐𝒅 𝒎𝟏 𝒙 ≡ 𝒄𝟐 𝒎𝒐𝒅 𝒎𝟐 szimultán kongruenciarendszer akkor és csak akkor oldható meg, ha (𝒎𝟏 , 𝒎𝟐 )|𝒄𝟏 − 𝒄𝟐
1
Ezt szerintem nem kell megtanulni, de jó, ha egyszer elolvassuk a Wilson tétellel bezárólag.
6
Tétel: Megoldhatóság esetén az összes megoldás egy maradékosztályt alkot modulo [𝒎𝟏 , 𝒎𝟐 ]. Ez más megfogalmazásban azt jelenti, hogy ha az s egész szám a szimultán kongruenciarendszer egy megoldása, akkor az alábbi t értékek adják az összes megoldást: 𝑡 ≡ 𝑚𝑜𝑑 𝒎𝟏 , 𝒎𝟐 , azaz t = s + k 𝒎𝟏 , 𝒎𝟐 , ahol k egész. Tétel: Ha 𝑚1 , 𝑚2 = 1, 𝑎𝑘𝑘𝑜𝑟 𝑎𝑧
𝒙 ≡ 𝒄𝟏 𝒎𝒐𝒅 𝒎𝟏 𝒙 ≡ 𝒄𝟐 𝒎𝒐𝒅 𝒎𝟐 szimultán kongruenciarendszer bármilyen 𝑐1 é𝑠 𝑐2 egész szám esetén megoldható, és a megoldások egyetlen maradékosztályt alkotnak modulo 𝑚1 𝑚2 Tétel: (Kínai maradéktétel) Legyen az 𝒎𝟏 , … 𝒎𝒌 modulusok páronként relatív prímek. Ekkor az 𝒙 ≡ 𝒄𝟏 𝒎𝒐𝒅 𝒎𝟏 𝒙 ≡ 𝒄𝟐 𝒎𝒐𝒅 𝒎𝟐 . . 𝒙 ≡ 𝒄𝒌 𝒎𝒐𝒅 𝒎𝒌 szimultán kongruenciarendszer bármilyen 𝑐1 … 𝑐𝑘 egészek esetén megoldható, és a megoldások egyetlen maradékosztályt alkotnak modulo 𝑚1 𝑚2 ⋯ 𝑚𝑘 Tétel: (Wilson tétel) 𝐻𝑎 𝑝 𝑝𝑜𝑧𝑖𝑡í𝑣 𝑝𝑟í𝑚, 𝑎𝑘𝑘𝑜𝑟 𝑝 − 1 ! ≡ −1 (𝑚𝑜𝑑𝑢𝑙𝑜 𝑝)
Magasabb fokú kongruenciák
Definíció: Az 𝑓 = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑛 𝑥 𝑛 polinom modulo m vett fokszáma (vagy foka) 𝒌, ha 𝑎𝑘 ≢ 0 𝑚𝑜𝑑 𝑚 , 𝑑𝑒 𝑚𝑖𝑛𝑑𝑒𝑛 𝑖 > 𝑘 𝑒𝑠𝑒𝑡é𝑛 𝑎𝑖 ≡ 0 𝑚𝑜𝑑 𝑚 . Ha minden i-re 𝑎𝑖 ≡ 0 𝑚𝑜𝑑 𝑚 , 𝑎𝑧𝑎𝑧 𝑓 𝑚𝑖𝑛𝑑𝑒𝑛 𝑒𝑔𝑦ü𝑡𝑡𝑎𝑡ü𝑗𝑎 0 𝑚𝑜𝑑 𝑚, 𝑎𝑘𝑘𝑜𝑟 𝑓 − 𝑛𝑒𝑘 𝑚𝑜𝑑𝑢𝑙𝑜 𝑚 nincs foka. Tétel: Ha 𝒑 prím és az 𝒇 polinom modulo 𝑝 vett foka 𝑘, akkor az 𝒇 𝒙 ≡ 𝟎 (m) kongruencia megoldásszáma legfeljebb k. 𝑻é𝒕𝒆𝒍: Bármely p prím és 𝑓 egész együtthatós polinom esetén létezik olyan 𝑔 egész együtthatós polinom, hogy a 𝑔 modulo 𝑝 vett foka legfeljebb 𝑝 − 1 − 𝑣𝑎𝑔𝑦 𝑔 minden együtthatója 0 𝑚𝑜𝑑𝑢𝑙𝑜 𝑝 és minden 𝑐 egész számra 𝑓 𝑐 ≡ 𝑔 𝑐 (𝑚𝑜𝑑 𝑝)
Binom kongruenciák
Definíció: Az 𝑥 𝑘 ≡ 𝑎 𝑚𝑜𝑑 𝑝 𝑘𝑜𝑛𝑔𝑟𝑢𝑒𝑛𝑐𝑖á𝑘𝑎𝑡 kéttagú vagy binom kongruenciának nevezzük. Az általános alakja: c𝑥 𝑘 ≡ 𝑎 𝑚𝑜𝑑 𝑝 Tétel: Legyen 𝑝 prím és (𝑎, 𝑝) = 1. Az akkor és csakis akkor oldható meg, ha
𝑥 𝑘 ≡ 𝑎 𝑚𝑜𝑑 𝑝 𝑝−1
𝑎(𝑘,𝑝−1) ≡ 1 𝑚𝑜𝑑 𝑝 Megoldhatóság esetén a megoldások száma 𝑘, 𝑝 − 1 . Definíció: Legyen p prím és (a,p)=1. Az 𝒂 számot 𝒌 − 𝒂𝒅𝒊𝒌 hatványmardéknak nevezzük, ha az 𝑥 𝑘 ≡ 𝑎 𝑚𝑜𝑑 𝑝 kongruencia megoldható, és 𝒌 − 𝒂𝒅𝒊𝒌 hatvány-nemmaradéknak nevezzük, ha az 𝑥 𝑘 ≡ 𝑎 𝑚𝑜𝑑 𝑝 kongruencia nem oldható meg. Tétel: Legyen 𝑝 prím és (𝑎, 𝑝) = 1. Az a szám akkor és csak akkor k-adik hatványmaradék, ha 𝑝 −1
𝑎(𝑘 ,𝑝 −1) ≡ 1 𝑚𝑜𝑑 𝑝 . 𝑯𝒂𝒔𝒛𝒏𝒐𝒔: 𝒂𝒙 ≡ 𝒃(𝒎) ⟺ 𝑚|𝑎𝑥 − 𝑏 ⟹ 𝑎𝑥 − 𝑏 = 𝑚𝑦 ⟺ 𝒂𝒙 − 𝒎𝒚 = 𝒃 7
Kvadratikus kongruenciák Definíció: Legyen 𝑝 > 2 prím és (𝑎, 𝑝) = 1. Az a számot aszerint nevezzük kvadratikus maradéknak, illetve kvadratikus nemmaradéknak modulo p, hogy az 𝒙𝟐 ≡ 𝒂 𝒎𝒐𝒅 𝒑 kongruencia megoldható-e, vagy sem. Tétel: Az 𝒂 szám ⟺ kvadratikus maradék modulo p, ha 𝒂(𝒑−𝟏)/𝟐 ≡ 𝟏 𝒎𝒐𝒅 𝒑
Az 𝒂 szám ⟺ kvadratikus nemmaradék modulo p, ha 𝒂(𝒑−𝟏)/𝟐 ≡ −𝟏 𝒎𝒐𝒅 𝒑
A kvadratikus maradékok szám, illetve kvadratikus nemmaradékok száma egyaránt (𝑝 − 1)/2
Ha a kvadratikus maradék, akkor 𝒙𝟐 ≡ 𝒂 𝒎𝒐𝒅 𝒑 kongruenciának két megoldása van
Definíció: Az
𝑎
𝑳𝒆𝒈𝒆𝒏𝒅𝒓𝒆 − 𝒔𝒛𝒊𝒎𝒃ó𝒍𝒖𝒎𝒐𝒕a következőképpen értelmezzük: 𝑎 1, 𝑎 𝑎 𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘𝑢𝑠 𝑚𝑎𝑟𝑎𝑑é𝑘 𝑚𝑜𝑑𝑢𝑙𝑜 𝑚 = −1, 𝑎 𝑎 𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘𝑢𝑠 𝑛𝑒𝑚𝑚𝑎𝑟𝑎𝑑é𝑘 𝑚𝑜𝑑𝑢𝑙𝑜 𝑚 𝑝
𝑝
Tétel: 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑝 ⟹
𝑎𝑏 𝑝 −1 𝑝
=
𝑎
𝑏
𝑝
𝑝
𝑎
=
𝑝
𝑏 𝑝
1, 𝑎 𝑝 ≡ 1 (𝑚𝑜𝑑𝑢𝑙𝑜 4) = −1, 𝑎 𝑝 ≡ −1(𝑚𝑜𝑑𝑢𝑙𝑜 4)
Tétel: (Kvadratikus reciprocitási tétel) Ha 𝑝 > 2 é𝑠 𝑞 > 2 𝑘é𝑡 𝑘ü𝑙ö𝑛𝑏ö𝑧ő 𝑝𝑟í𝑚, 𝑎𝑘𝑘𝑜𝑟 𝑝−1 𝑞−1 𝑞 𝑝 = (−1) 2 ∙ 2 𝑝 𝑞 𝑎𝑧𝑎𝑧 𝑝 − , 𝑎 𝑝 ≡ 𝑞 ≡ −1 (𝑚𝑜𝑑𝑢𝑙𝑜 4) 𝑞 𝑞 = 𝑝 𝑝 , 𝑒𝑔𝑦é𝑏𝑘é𝑛𝑡 𝑞 Definíció: 𝐿𝑒𝑔𝑦𝑒𝑛 𝑚 > 1 páratlan szám, 𝑚 = 𝑝1 … 𝑝𝑟 , 𝑎𝑜𝑙 a 𝑝𝑖 számok pozitív prímek. Legyen 𝑎 𝑎 (𝑎, 𝑚) = 1. Ekkor az 𝑚 Jacobi-szimbólumot mint az 𝑝 Legendre –szimbólumának sorozatát értjük
𝑎
𝑚
=
𝑎
𝑝1
…
𝑝𝑟
Tétel: 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) ⟹
𝑎𝑏 𝑚
=
𝑖
𝑎
𝑎
𝑏
𝑚
𝑚
𝑎 𝑚
𝑏
= 𝑎
𝑚𝑛
𝑚
=
𝑎
𝑎
𝑛
𝑚
8
