Prímtényező
A számelméletben egy pozitív egész szám prímtényezőin vagy törzstényezőin a szám prímszám osztóinak összességét értjük. Egy pozitív egész szám  prímfelbontása: a szám prímtényezőinek listázása, annak figyelembevételével, hogy hányszor szerepelnek a szám osztói között. A számelmélet alaptétele kimondja, hogy minden pozitív egész szám egyféleképpen bontható fel prímtényezők szorzatára.

A prímtényezős felbontást a rövidség érdekében hatványformában szokás felírni. Például

melyben a 2, 3 és 5 prímtényezők multiplicitása 3, 2 illetve 1.

A  felbontást a szám kanonikus alakjának is nevezik (pl. ).

Egy n szám p prímtényezőjét tekintve p multiplicitása az a legnagyobb a kitevő, amire pa osztója n-nek.

Egy n pozitív egész számra a prímtényezők száma és a prímtényezők összege (a multiplicitást nem tekintve) olyan számelméleti függvények, melyek additívak, de nem totálisan additívak.

Négyzetszámok
A négyzetszámok arról ismerhetőek meg, hogy minden prímtényezőjük páros multiplicitással rendelkezik. Például a 144 (a 12 négyzete) prímtényezői:

Ezeket átrendezve: 

Mivel minden prímtényező páros számúszor jelenik meg, az eredeti szám kifejezhető valamely kisebb szám négyzeteként. Hasonlóan, a köbszámok prímtényezőinek multiplicitása a 3 többszöröse s.í.t.

Relatív prímek
A közös prímtényezővel nem rendelkező pozitív egész számokat relatív prímeknek (angolul: coprime) nevezik. Ha a és b pozitív egész számok relatív prímek, ha legnagyobb közös osztójuk lnko(a, b) = 1. Az euklideszi algoritmussal meghatározható, hogy két szám relatív prím-e prímtényezőik ismerete nélkül is; az algoritmus a számjegyek száma szerint polinomiális időben fut le.

Az 1 szám minden pozitív egésszel és önmagával is relatív prím. Ennek oka, hogy nincsenek prímtényezői, ő az üres szorzat. Tehát lnko(1, b) = 1 bármely b ≥ 1.

Kriptográfiai alkalmazásai
A számok prímfelbontása titkosítási rendszerek kriptográfiai biztonságának fontos részét képezi; a probléma ismereteink szerint a polinomiálisnál hosszabb időt vesz igénybe; viszonylag könnyű olyan problémát megalkotni, aminek megoldása az univerzum életkoránál hosszabb időt venne igénybe jelenlegi algoritmusainkkal.

Omega-függvények 
Az  (omega) megmutatja az n szám különböző prímtényezőinek számát, míg a  (nagy omega) függvény, az n szám összes prímtényezőjének a számát
Ha
,

akkor
.

Például , így  és .
 értéke  = 1, 2, 3…-ra  0, 1, 1, 1, 1, 2, 1, 1, 1, … .
 értéke  = 1, 2, 3…-ra 0, 1, 1, 2, 1, 2, 1, 3, 2, … .

Fordítás

Kapcsolódó szócikkek 
 Összetett szám
 Oszthatóság
 Eratoszthenész szitája
 Erdős–Kac-tétel
 Számelméleti függvény

További információk 
 Alice és Bob - 16. rész: Alice és Bob alaptétele

Jegyzetek 

Prímszámok
Számelmélet
A számelméletben egy pozitív egész szám prímtényezőin vagy törzstényezőin a szám prímszám osztóinak összességét értjük . Egy pozitív egész szám prímfelbontása : a szám prímtényezőinek listázása , annak figyelembevételével , hogy hányszor szerepelnek a szám osztói között . A számelmélet alaptétele kimondja , hogy minden pozitív egész szám egyféleképpen bontható fel prímtényezők szorzatára . A prímtényezős felbontást a rövidség érdekében hatványformában szokás felírni . Például melyben aésprímtényezők multiplicitásailletve A felbontást a szám kanonikus alakjának is nevezik ( pl . ) . Egy n szám p prímtényezőjét tekintve p multiplicitása az a legnagyobb a kitevő , amire pa osztója n-nek . Egy n pozitív egész számra a prímtényezők száma és a prímtényezők összege ( a multiplicitást nem tekintve ) olyan számelméleti függvények , melyek additívak , de nem totálisan additívak . Négyzetszámok A négyzetszámok arról ismerhetőek meg , hogy minden prímtényezőjük páros multiplicitással rendelkezik . Például a( anégyzete ) prímtényezői : Ezeket átrendezve : Mivel minden prímtényező páros számúszor jelenik meg , az eredeti szám kifejezhető valamely kisebb szám négyzeteként . Hasonlóan , a köbszámok prímtényezőinek multiplicitása atöbbszöröse s.í.t . Relatív prímek A közös prímtényezővel nem rendelkező pozitív egész számokat relatív prímeknek ( angolul : coprime ) nevezik . Ha a és b pozitív egész számok relatív prímek , ha legnagyobb közös osztójuk lnko ( a , b ) = 1. Az euklideszi algoritmussal meghatározható , hogy két szám relatív prím-e prímtényezőik ismerete nélkül is ; az algoritmus a számjegyek száma szerint polinomiális időben fut le . Azszám minden pozitív egésszel és önmagával is relatív prím . Ennek oka , hogy nincsenek prímtényezői , ő az üres szorzat . Tehát lnko ( 1 , b ) = 1 bármely b ≥ 1. Kriptográfiai alkalmazásai A számok prímfelbontása titkosítási rendszerek kriptográfiai biztonságának fontos részét képezi ; a probléma ismereteink szerint a polinomiálisnál hosszabb időt vesz igénybe ; viszonylag könnyű olyan problémát megalkotni , aminek megoldása az univerzum életkoránál hosszabb időt venne igénybe jelenlegi algoritmusainkkal . Omega-függvények Az ( omega ) megmutatja az n szám különböző prímtényezőinek számát , míg a ( nagy omega ) függvény , az n szám összes prímtényezőjének a számát Ha akkor . Például , így és\. értéke =-ra …\. értéke =-ra …\ . Fordítás Kapcsolódó szócikkek Összetett szám Oszthatóság Eratoszthenész szitája Erdős–Kac-tétel Számelméleti függvény További információk Alice és Bob - rész : Alice és Bob alaptétele Jegyzetek Prímszámok Számelmélet