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

4 993 bájt hozzáadva ,  6 évvel ezelőtt
nincs szerkesztési összefoglaló
(Átirányítás ide: Prímfelbontás)
 
Nincs szerkesztési összefoglaló
[[Image:PrimeDecompositionExample.svg|right|thumb|200px|Az ábra megmutatja a 864 szám prímtényezős felbontását. Az eredményül kapott prímtényezők röviden így írhatók fel: 2<sup>5</sup> × 3<sup>3</sup>]]
#ÁTIRÁNYÍTÁS [[Prímfelbontás]]
 
A [[számelmélet]]ben egy pozitív [[egész szám]] '''prímtényezőin''' a szám [[prímszám]] osztóinak összességét értjük.<ref>
{{cite book
| last = Jensen
| first = Gary R.
| year = 2004
| title = Arithmetic for Teachers: With Applications and Topics from Geometry
| publisher = American Mathematical Society
 
}}</ref> Egy pozitív egész szám [[prímfelbontás]]a: a szám prímtényezőinak listázása, annak figyelembe vé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
:<math> 360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5,</math>
melyben a 2, 3 és 5 prímtényezők [[multiplicitás]]a 3, 2 illetve 1.
 
Egy ''n'' szám ''p'' prímtényezőjét tekintve ''p'' multiplicitása az a legnagyobb ''a'' [[kitevő]], amire ''p<sup>a</sup>'' 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ény]]ek, melyek additívak, de nem totálisan additívak.<ref>{{cite book | title=Additive Number Theory: the Classical Bases | volume=164 | series=Graduate Texts in Mathematics | author=Melvyn B. Nathanson | publisher=Springer-Verlag | year=1996 | isbn=0-387-94656-X }}</ref>
 
==Négyzetszámok==
A [[négyzetszám]]ok arról ismerszenek 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:
:<math> 144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = (2 \times 2 \times 3) \times (2 \times 2 \times 3) = (2 \times 2 \times 3)^2 = (12)^2.</math>
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ám]]ok 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í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. Ennak 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==
A számok [[prímfelbontás]]a [[titkosítás]]i rendszerek [[kriptográfia]]i biztonságának fontos részét képezi;<ref>{{cite book
| last = Menezes | first = Alfred
| coauthors = van Oorschot, Paul C.; Vanstone, Scott A.
| url = http://www.cacr.math.uwaterloo.ca/hac/
| title = Handbook of Applied Cryptography
| publisher = CRC Press |date=October 1996
| isbn = 0-8493-8523-7 }}</ref> 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 {{math|ω(''n'')}} (omega) megmutatja az ''n'' szám ''különböző'' prímtényezőinek számát, míg a {{math|Ω(''n'')}} (nagy omega) függvény, az ''n'' szám ''összes'' prímtényezőjének a számát <ref name ="Riesel" />
Ha
:<math>n = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}</math>,
 
akkor
:<math>\Omega(n) = \sum_{i=1}^{\omega(n)} \alpha_i</math>.
 
Például {{math|1=24 = 2<sup>3</sup> × 3<sup>1</sup>}}, így {{math|1=ω(24) = 2}} és {{math|1=Ω(24) = 3 + 1 = 4}}.
*{{math|ω(''n'')}} értéke {{math|''n''}} = 1, 2, 3…-ra 0, 1, 1, 1, 1, 2, 1, 1, 1, … {{OEIS|id=A001221}}.
*{{math|Ω(''n'')}} értéke {{math|''n''}} = 1, 2, 3…-ra 0, 1, 1, 2, 1, 2, 1, 3, 2, … {{OEIS|id=A001222}}.
 
==Fordítás==
* {{fordítás|en|Prime factor|oldid=694839918|n=a|4=angol}}
 
== Kapcsolódó szócikkek ==
* [[Összetett szám]]
* [[Osztó]]
* [[Eratoszthenész szitája]]
* [[Erdős–Kac-tétel]]
* [[Számelméleti függvény]]
 
== Jegyzetek ==
{{jegyzetek}}
 
[[Kategória:Prímszámok]]
[[Kategória:Számelmélet]]
89 988

szerkesztés