„Prímtényező” változatai közötti eltérés

a
Pár elírás javítása
a (Pár elírás javítása)
| publisher = American Mathematical Society
 
}}</ref> Egy pozitív egész szám [[prímfelbontás]]a: a szám prímtényezőinakprímtényezőinek listázása, annak figyelembe vételévelfigyelembevé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.<ref name="Riesel">{{Citation | last1=Riesel | first1=Hans | title=Prime numbers and computer methods for factorization | publisher=Birkhäuser | location=Basel, Switzerland | isbn=978-0-8176-3743-9 | year=1994}}</ref>
 
A prímtényezős felbontást a rövidség érdekében hatványformában szokás felírni. Például
 
==Négyzetszámok==
A [[négyzetszám]]ok arról ismerszenekismerhető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:
:<math> 144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2.</math>
Ezeket átrendezve:
A közös prímtényezővel nem rendelkező pozitív egész számokat [[relatív prímek]]nek (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'',&nbsp;''b'')&nbsp;=&nbsp;1. Az [[euklideszi algoritmus]]sal 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. EnnakEnnek oka, hogy nincsenek prímtényezői, ő az [[üres szorzat]]. Tehát lnko(1,&nbsp;''b'')&nbsp;=&nbsp;1 bármely ''b''&nbsp;≥&nbsp;1.
 
==Kriptográfiai alkalmazásai==
1

szerkesztés