Diszkrét matematikakimaradt

Prímszámok és prímtényezős felbontás

Prímszámok és összetett számok, a számelmélet alaptétele, lnko és lkkt a kanonikus alakból, az osztók száma, és miért van végtelen sok prím.

Forrás: DiMat_ea.pdf 29–31. dia · Feladatsor 3.4–3.21

Prímek és összetett számok

Minden $n > 1$ természetes számnak van két pozitív osztója: az 1 és saját maga. Ezek a triviális osztók.

Definíció

Prímszám: 1-nél nagyobb természetes szám, amelynek csak triviális osztói vannak. ( $2, 3, 5, 7, 11, 13, \dots$ )
Összetett szám: 1-nél nagyobb szám, amelynek van nem triviális osztója is. ( $4, 6, 8, 9, 10, \dots$ )
Az 1 se nem prím, se nem összetett: ő az egységelem.

Tétel · a prímek jellemzése

Egy $p > 1$ egész pontosan akkor prím, ha minden $a, b \in \Z$ -re: $p \mid ab \implies p \mid a$ vagy $p \mid b$ .

Példa

Összetett számra ez nem igaz: $6 \mid 4 \cdot 9 = 36$ , de $6 \nmid 4$ és $6 \nmid 9$ . A 6 „szétoszlik” a két tényező között ( $2 \mid 4$ , $3 \mid 9$ ). Egy prím nem tud szétoszlani.

A számelmélet alaptétele

Tétel · a számelmélet alaptétele

Minden 1-nél nagyobb természetes szám felbontható véges sok prím szorzatára, és ez a felbontás a tényezők sorrendjétől eltekintve egyértelmű.

Az egyértelmű szorzatot kanonikus vagy prímtényezős alaknak hívjuk:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r},

ahol $p_1, \dots, p_r$ különböző prímek és $\alpha_i \in \N$ .

Példa

$1260 = 2 \cdot 630 = 2^2 \cdot 315 = 2^2 \cdot 3^2 \cdot 35 = 2^2 \cdot 3^2 \cdot 5 \cdot 7$ .

Lnko és lkkt a kanonikus alakból

Legnagyobb közös osztó: a közös prímtényezők, a kisebb kitevőn.
Legkisebb közös többszörös: az összes előforduló prímtényező, a nagyobb kitevőn.

Példa · az előadásból

$1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7$ és $14850 = 2 \cdot 3^3 \cdot 5^2 \cdot 11$ .

$(1260, 14850) = 2^1 \cdot 3^2 \cdot 5^1 = 90$
$[1260, 14850] = 2^2 \cdot 3^3 \cdot 5^2 \cdot 7 \cdot 11 = 207\,900$

Tétel

$(a, b) \cdot [a, b] = |ab|$ .

Ez azért igaz, mert minden prímnél a kisebb és a nagyobb kitevő összege éppen a két kitevő összege. A példán: $90 \cdot 207\,900 = 18\,711\,000 = 1260 \cdot 14850$ . ✓

Két szám pontosan akkor relatív prím, ha nincs közös prímtényezőjük.

Az osztók száma

Tétel

Az $n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$ szám pozitív osztóinak száma

d(n) = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_r + 1).

Miért? Egy osztóban a $p_1$ prím $0, 1, \dots, \alpha_1$ -szer szerepelhet, ez $\alpha_1 + 1$ lehetőség, és így tovább minden prímre. A választások függetlenek, tehát szorzódnak.

Példa

$12 = 2^2 \cdot 3$ : $d(12) = (2+1)(1+1) = 6$ . Valóban: $1, 2, 3, 4, 6, 12$ .

Az előadás példái: $1\,455\,300 = 2^2 \cdot 3^3 \cdot 5^2 \cdot 7^2 \cdot 11$ , így $d = 3 \cdot 4 \cdot 3 \cdot 3 \cdot 2 = 216$ ; és $185\,130 = 2 \cdot 3^2 \cdot 5 \cdot 11^2 \cdot 17$ , így $d = 2 \cdot 3 \cdot 2 \cdot 3 \cdot 2 = 72$ .

Végtelen sok prím van

Tétel · Euklidesz

A prímszámok száma végtelen.

Indirekt tegyük fel, hogy csak véges sok prím van: $p_1, p_2, \dots, p_k$ .

Legyen $b = p_1 p_2 \cdots p_k + 1$ . Ez nagyobb 1-nél, és mivel minden prímnél nagyobb, nem prím, tehát összetett. Így van prímosztója, valamelyik $p_i$ .

$p_i \mid b$ és $p_i \mid p_1 \cdots p_k$ , ezért a különbségüknek is osztója: $p_i \mid 1$ . Ez lehetetlen. Ellentmondás.

Megjegyzés

A $b$ szám maga nem feltétlenül prím, a bizonyítás csak azt használja, hogy van prímosztója, ami nincs a listán. Például $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ .

Hány nullára végződik 100!?

Példa · 3.4

Minden végső nullához egy $10 = 2 \cdot 5$ tényező kell. Kettes sokkal több van, mint ötös, tehát az ötösöket kell számolni:

az 5 többszörösei $100$ -ig: $\lfloor 100/5 \rfloor = 20$ darab, mindegyik ad egy 5-öst;
a 25 többszörösei még egy-egy 5-öst adnak: $\lfloor 100/25 \rfloor = 4$ .

Összesen $20 + 4 = 24$ nulla.

Próbáld ki

Interaktív

Prímtényezős felbontás

Kanonikus alak, osztók száma, Euler-φ és az oszthatósági szabályok egyszerre.

n második szám (lnko/lkkt)

kanonikus alak: 1 455 300 = 2² · 3³ · 5² · 7² · 11
prím?: összetett
d(n): (2+1)(3+1)(2+1)(2+1)(1+1) = 216
φ(n): 1455300 · (1 − 1/2) · (1 − 1/3) · (1 − 1/5) · (1 − 1/7) · (1 − 1/11) = 302400
második szám: 185 130 = 2 · 3² · 5 · 11² · 17
(n, m): kisebb kitevők: 2 · 3² · 5 · 11 = 990
[n, m]: nagyobb kitevők: 2² · 3³ · 5² · 7² · 11² · 17 = 272 141 100

÷	a szabály ezt nézi
2	utolsó jegy: 0	igen
5	utolsó jegy: 0	igen
4	utolsó két jegy: 0	igen
25	utolsó két jegy: 0	igen
8	utolsó három jegy: 300	nem
3	számjegyösszeg: 18	igen
9	számjegyösszeg: 18	igen
11	váltakozó összeg a₀ − a₁ + a₂ − …: 0	igen

Gyakorló feladatok

Gyakorló feladat · 3.18

Hány pozitív osztója van a 252, a 600 és az 528 számnak?

Megoldás

$252 = 2^2 \cdot 3^2 \cdot 7$ : $3 \cdot 3 \cdot 2 = 18$
$600 = 2^3 \cdot 3 \cdot 5^2$ : $4 \cdot 2 \cdot 3 = 24$
$528 = 2^4 \cdot 3 \cdot 11$ : $5 \cdot 2 \cdot 2 = 20$

Gyakorló feladat · 3.19

Melyik a legkisebb természetes szám, amelynek pontosan 12 pozitív osztója van?

Megoldás

$12$ felbontásai szorzattá (a kitevők $+1$ -ei): $12$ , $6 \cdot 2$ , $4 \cdot 3$ , $3 \cdot 2 \cdot 2$ . A megfelelő legkisebb számok (a legnagyobb kitevő a legkisebb prímre): $2^{11} = 2048$ , $2^5 \cdot 3 = 96$ , $2^3 \cdot 3^2 = 72$ , $2^2 \cdot 3 \cdot 5 = 60$ . A legkisebb a 60.

Gyakorló feladat · 3.15

Legyen $p > 3$ prím. Mutasd meg, hogy $24 \mid p^2 - 1$ .

Megoldás

$p^2 - 1 = (p - 1)(p + 1)$ . Mivel $p$ páratlan, $p - 1$ és $p + 1$ két egymás utáni páros szám, közülük az egyik osztható 4-gyel: a szorzat osztható 8-cal. A $p - 1, p, p + 1$ közül az egyik osztható 3-mal, és ez nem a $p$ (mert $p > 3$ prím), tehát a szorzat osztható 3-mal is. $(8, 3) = 1$ , így $24 \mid p^2 - 1$ .

[subject]/[topic]

Prímek és összetett számok

A számelmélet alaptétele

Lnko és lkkt a kanonikus alakból

Az osztók száma

Végtelen sok prím van

Hány nullára végződik 100!?

Próbáld ki

Prímtényezős felbontás

Gyakorló feladatok