Prima faktoro
En nombroteorio, prima faktoro de pozitiva entjero estas primo, kiu dividas la entjeron sen resto. La procezo de trovado de ĉi tiuj nombroj estas entjera faktorado, aŭ prima faktorado.
Por prima faktoro p de n, la obleco de p estas la plej granda eksponento a por kiu pa dividas na n.
Du pozitivaj entjeroj estas reciproke primaj, se kaj nur se ili ne havas komunajn primajn faktorojn. La entjero 1 estas reciproke prima kun ĉiu pozitiva entjero, inkluzivante sin. Ĉi tiel estas, ĉar ĝi ne havas primajn faktorojn. Ĉi tio ankaŭ sekvas el difino de a kaj b kiel reciproke primaj, se PGKD(a, b)=1, Tiel PGKD(1, b)=1 por ĉiu b>=1. Eŭklida algoritmo povas esti uzita por determini, ĉu du entjeroj estas reciproke primaj, sen scio de iliaj primaj faktoroj; la algoriritmo plenumiĝas en polinoma tempo kiel funkcio de la kvanto de ciferoj.
La prima faktorado de pozitiva entjero estas listo de la entjeraj primaj faktoroj, kun ankaŭ iliaj oblecoj. La fundamenta teoremo de aritmetiko diras, ke ĉiu pozitiva entjero havas la solan priman faktoradon.
Por pozitiva entjero n, la kvanto de primaj faktoroj de n kaj la sumo de la primaj faktoroj de n (ne kalkulante la obleco) estas ekzemploj de aritmetikaj funkcioj de n kiuj estas adiciaj sed ne plene adiciaj.
La funkcio Ω Ω(n) estas la tuteca kvanto de primaj faktoroj de nenegativa entjero n, kalkulante ilin kun oblecoj. La ω(n) estas kvanto de malsamaj primaj faktoroj de n.
Difino de primaj faktoroj de nombro estas ekzemplo de problemo ofte uzata por certiĝi en ĉifrika sekureco en ĉifradaj sistemoj; ĉi tiu problemo postulas pli ol polinoman tempon de la kvanto de ciferoj; estas relative facile konstrui tian problemon, kiu devus preni pli longan tempon ol la sciata aĝo de la Universo por kalkuli per nuntenpaj komputiloj.
Ekzemploj[redakti | redakti fonton]
- La primaj faktoroj de 6 estas 2 kaj 3 (6 = 2 × 3). Ambaŭ havas oblecon 1.
- 5 havas nur unu priman faktoron 5 (5 estas primo). Ĝi havas oblecon 1.
- 100 havas du primajn faktorojn: 2 kaj 5 (100 = 22 × 52). Ambaŭ havas oblecon 2.
- 2, 4, 8, 16, kaj tiel plu ĉiu havas nur unu priman faktoron 2. (2 estas primo, 4 = 22, 8 = 23, kaj tiel plu)
- 1 havas ne primajn faktorojn.