Relativa Divideblo/Enkonduko

From Wikiversity

Ĉi tiu verko temas pri Numeriko kaj turnas sin al legantoj kiuj konas la elementojn de ĝis-abitura matematiko.

Signoj, Difinoj kaj Teoremoj[edit]

Dif 1: Numero estu sinonimo de natura nombro.

Dif 2: numeri signifu diri aŭ pensi 1, 2, 3, 4, 5, .....

Ja la naturaj nombroj havas la esencan econ ke ili estas vicigeblaj, kiel esprimas pli klare la numeroj. La ĝis nun uzata fakvorto estas „nombri“ kiu esprimo maltaŭgas, ĉar ĝuste NE temas pri nombroj ĝenerale sed ja NUR pri la „naturaj nombroj“ aŭ „numeroj“.

„Numero“ estas malpli longa kaj estas nur unu vorto, kio do estas avantaĝo ĉe vortformoj ne-substantivaj. Ekz. „natur-nombri“ aspektus kaj sonus malnature, „numeri“ nature. „numero“ kaj „numeri“ do estas vere sinonimoj preferindaj, kiujn mi estonte uzos.

Ĝeneralan numeron mi signos per la signo N.

Dif 3: numerilo signifas numeron en la ĝisnuna signifo, do materialo (papero), provizita per skribita numero.

Mi uzas la signojn
+
-
*
/
kaj
^
por la operacioj
adiciado,
subtrahado,
multiplikado,
dividado
kaj
potencado

Difinaro 4: En a*b=c a kaj b estas faktoroj kaj c la produto.

Nnti (notacii) c kiel produton mi nomas „faktorizi“ c:

TEO 1: Se ĉiuj faktoroj estas numeroj, do ankaŭ la produto.

Difinaro 5: Tiuj numeraj faktoroj estas Divizoroj.

La signo D(N) signifas la nombron da Divizoroj de numero N.

La notadon N = 1 * N mi nomas la triviala faktorizo kaj do 1 kaj N la trivialaj Divizoroj de N. Ĉiuj aliaj faktorizoj kaj Divizoroj estas la faktaj.

Difinaro 6: Se la NURa faktorizo de N (ne = 1) estas la triviala 1*N, N nomiĝas prim(nombr)o.

Dif 7: Faktorizi numeron N per nur prim-faktoroj nomiĝu prim-faktorizi.

La primoj estas plej gravaj numeroj, kvazaŭ la brikoj de numeroj. Ili distribuiĝas malregule interne de la numer-vico. Mi numerizas ilin, P1, P2, P3, ... , Pi, ... Jen, la unuaj 12 Primoj:

i: 1 2 3 4
5
6
7
8
9
10 11 12 ... 25 26
Pi 2 3 5 7 11 13 17 19 23 29 31 37 ... 97 101

Faktorizante, mi uzas la faktoron 1 nur unufoje, ĉar ja 1 ^ x = 1 por ĉiu x.

TEO 2:.Por ĉiu numero N validas ke ĝi estas mem primo aŭ prim-faktorizebla kaj tio nur unu-maniere (ne distigante la diversajn vicordojn de la prim-faktoroj.) La rigora pruvo de tiu teoremo ne estas simpla.

Difinaro 8: De la potenco a^b a estas la bazo kaj b la eksponento.

Potenco nomiĝu fakta se kaj a kaj b estas numeroj > 1.

Jen ekzemplaro kun la numero N = 60, kun ties faktorizoj:

60 = 1*60 = 2*30 = 3*20 = 4*15 = 5*12 = 6*10 = 2*2*15 = 2*3*10 = 2*5*6 = 3*4*5 = 2 * 2 *3* 5

60 havas do 11 diversajn faktorizojn. La unua estas la triviala. La ceteraj la faktaj, la lasta estas la prim-faktorizo. Estas 6 du-faktoraj faktorizoj el kiuj 5 faktaj. Tiuj du-faktoraj faktorizoj produktas la Divizorojn de 60, nome

1, 60 , 2, 30 , 3, 20 , 4, 15 , 5, 12 , 6, 10 , do 12 Divizorojn, 2 trivialajn kaj 10 faktajn.

Difaro 9: D(60) = 12 kaj D(60) = 10.

La Divizoroj do estas „legeblaj“ el la 2-faktoraj faktorizoj.

Tiel do troveblas la divizoroj kaj ties nombro da de ajna N.

Sed por grandaj N tiu metodo estas maloportuna, ĉar longdaŭra kaj multkalkuliga. Ekzistas pli oportuna algoritmo (= kalkul-vojo).

Unue mi enkonduku por prim-faktorizo novan signon:

60 = {2 1 1 0} kun la signifo: 60 = 2^2 * 3^1 * 5^1 * 7^0 *........

Dif 10: Ĝenerale signifu {vico de Ei} por i = 1,2,3,... j,...t la produton de la potencoj Pi^Ei, kun i<j<t kaj t la lasta vicero.

La primoj Pi, do P1 , P2 , P3 , ... estas la numerizitaj primoj 2 , 3 , 5 , 7 , ktp. Atentu ke Ei povas esti = 1 kaj = 0. Kompreneble ĉiu tia vico finiĝus per senfina vico de ciferoj nul. En la praktiko notatu Ei nur ĝiskun la lasta ne-0.

Ekzemploj:

  • 60 = 2^2 * 3^1 *5^1 * 7^0 *11^0 *13^0, ktp = {2 1 1}
  • 1000 = 2^3 * 3^0 *5^3 = {3 0 3 }
  • 99 = {0 2 0 0 1 }.

Dif 11: Tia vico estas vico de la eksponentoj de la prim-faktorizo de numero N, do Prim-Eksponent-VicoPEVa notacio (ankaŭ { }-notacio) de numero N = PEV(N). Trovu mem, leganto, la PEV-notaciojn de 17, 36, 3600, 2520.

Kiom estas {0 0 0 0 0 1 }? kaj {1 1 1 1 } ?

360 = {3 2 1} Ĉiu rezulto de {a b c } kun a = 3 aŭ 2 aŭ 1 aŭ 0 , b = 2 aŭ 1 aŭ 0 kaj c = 1 aŭ 0 estas Divizoro (triviala aŭ fakta) de 360, ĉu ne? Same klaras, ke ĉiu numero kun alia PEV(o-notaci)o nepre ne estas divizoro de 360.. Do supre indikiĝis ĉiuj divizoroj de 360. Da ili estas tiom da , kiom estas da kombinoj de 4 , 3 , 2 kaj arbitre multaj faktoroj 1, do 4*3*2 * ‚ 1*1*1*.....= 24. Do D(360) = 24 kaj D(360) = 22. Jen, pli simpla algoritmo, trovi D de pli granda numero N ,...,SE la prim-faktorizoj de N estas sufiĉe simpla.. Kaj kiel troveblas tia prim-faktorizo de arbitra numero N? Sistema algoritmo estas tlu laŭ EŬKLIDO : Ekz: ĉu 360 divideblas per P1=2? Jes, kun la rezulto 180. Ĉu tio divideblas ankaŭ per 2? jes, kun la rezulto 90. Ĉu denove? Jes, kun la rezulto 45. Ĉu denove? Ne. Ĉu tiu lasta rezulto, 45 divideblas per P2 = 3? Jes, kun rezulto 15. Kaj denove? Jes, kun rezulto 5. Kaj denove? Ne. Ja 5 estas mem primo, primo nova. Per tia esploro de sinsekvaj dividoj certiĝas ke 360 = P1 ^3 * P2 ^2 * P3 ^1 * Pi ^ 0, ktp. do ke 360 = {3 2 1 }.. Sed en ĉi tia kazo, se N estas facile (parkere) krude faktorizebla, ekz. 360 = 36 * 10 aŭ 60 * 6, , pli simplas poste primfaktorizi la faktorojn, kiuj ja estas malpli grandaj ol N mem. Tiu ĉi ekzemplo kun 360 estas ĝeneraligbla tiel ĉi: Kiel trovi D(N) de sufiĉe granda numero N?

  • 1-a paŝo : Prim-faktorizu N (sisteme laŭ EŬKLIDO aŭ, se eble, post lerta, pli kruda, antaŭ-faktorizo.)
  • 2-a paŝo : notaciu tiun rezulton PEVe, do {a b c .... }
  • 3-a paŝo : Pliigu ĉiujn tiujn Ei per 1 kaj notu tiel { (a+1) (b+1) (c+1).1 }
  • 4-a paŝo : Kalkulu la produton de ĉiuj tiuj per 1 pliigitaj Ei.

La ĉefa algoritmero estas la prim-faktorizo de N. Montriĝis du manieroj. Sed se N estas vere granda kaj eĉ la unua (plej malgranda) primbazo estas granda, tio estas vere teda kaj longegdaŭra proceso. Ekz. 912 673 ne lerte faktorizeblas krude. Kaj per EŬKLIDO oni konstatas la NE-divideblon per la primoj 2 , 3 , 5 , ...ĝis P25 = 97. Kaj tiu divido kondukas al 9409, sed ankaŭ tiu rezulto, jam malpli granda, denove kaŭzas tiom da provoj. Denove oni devas fari 25 divid(klopod-)ojn. Kaj nur tiel oni trovas la primfaktorizan rezulton, : 97^3. .Tiom da peno por tamen la relative modeste granda N=912673, eĉ malpli ol unu miliono. Kio estus pri ekz. 1357986422357 Certe, tuj videblas de ajna numero la divideblo per 2, per 5, per 10, kaj pere de konataj „divideblo-provoj“ per 9 kaj 3 kaj per 11. Sed poste povas do resti tiom da primoj per kiuj la EŬKLIDa metodo postulas dividoklopodojn. Do, jen, tiu paŝo de la algoritmo (algoritmero) estas LA taskego, eĉ por nur modeste grandaj numeroj. Tiukaze bezonatas listo de la unuaj m u l t a j primoj. kaj precipe komputoro kun taŭga, vasta matematik-programo kun ankaŭ tiu algoritmo. Bonaj ĝeneralaj komputoraj matematik-programoj kompreneble enhavas ankaŭ tiun algoritmon.Post la do ofte penega prim-faktorizo de granda, granda N, la kalkulo de D(N) estas simpla, kvankam D(N) de tre granda N estas mem ankaŭ jam granda.

Dif 12: N={ E1 E2 ...Et 0 } signifas 2^E1*3^E2*..Pt^E*1*1...

TEO 3: D(N) = F! * F2 *...* Ft kun Fi = Ei + 1

La algoritmon por trovi D(N) de arbitra N, mi enkondukis per ekzemploj (N=60 kaj N=360). Sed mi tute ne montris la pruvon por la ĝusto de tiu ĝenerala algoritmo. Ĉar:

Unuflanke jam nur la necesa notado de ĝenerala, rigore logika (matematika) pruvo estus multe pli komplika kaj kompleksa. Kaj

Aliflanke mi forte supozas, ke leganto kiu povis sekvi kaj kompreni la tekston de la ekzemploj, mem kapablas relative simple formuli matematikan pruvon, aŭ almenaŭ „sentas“ kun konvinkiĝo, ke nepre la ĝenerala formulo certe validas, ĉar pruveblas ankaŭ rigore logike. Tial mi intencas en tiu ĉi verko foje enkonduki formulojn kaj teoremojn per ekzemploj kaj ellasi ties rigoran pruvon al interesataj legantoj..