Matematika | Diszkrét Matematika » Haskó György - Oszthatóság algoritmusfelezéssel

Oszthatóság algoritmusfelezéssel Egy egyszerű algoritmus kicsi prímszámokkal való oszthatóság vizsgálatához, és egy módszer a 1012 –nél kisebb páratlan számok összetett, avagy prím voltának megállapítására az Excel táblázatkezelő segítségével Írjuk fel a következő kifejezéseket: b (-)p = (p-1)/2 + 2x c (+)p = ABS((p+1)/2-2x) b (+)p = (p+1)/2+ 2x c (-)p = ABS((p-1)/2-2x) „p” kettőnél nagyobb prímszám, a (p-1) és a (p+1) a „p” számot közrefogó páros számok, a „b (-)p ”, a „b (+)p ”, és az „x” természetes (egész) számok. (Lehetne vizsgálni a fentiekkel lényegében egyenértékű kifejezéseket is, amelyekben nincs felezés pl: f (-)p = p-1 + 2z, ahol z = x+1, de az oszthatósági szabályok felállításához azok kevésbé alkalmasak.) Keressünk meg az összes 100-nál kisebb 3≤ p ≤ 97 (24 db) páratlan prímszám mindegyikéhez azokat az „x” egész értékeket, amelyeknél vagy l.nko(b (-)p , p) = p, vagy

lnko(b (+)p , p) = p Ez a legnagyobb közös osztó vagy „p”-vel, vagy 1-gyel egyenlő. A Fermat tétel speciális esetéből: 2(p-1) ≡ 1 (mod p) átalakítások után ezt kapjuk: 2(p-1) +p -1 ≡ p (mod p) 2(p-2) + (p – 1)/2 ≡ p (mod p) A b (-)p = (p – 1)/2 + 2x ≡ p (mod p) egyenértékű azzal, hogy l.nko( b (-)p , p) = p Az „x = (p-2)” egy lehetséges érték. Határozzuk meg ezeket a kitevőket az összes 100-nál kisebb páratlan prímszámhoz. Vegyük fel az x értékek sorozatát x = 1, 2, 3, ,és számítsuk ki Euklideszi algoritmussal a legnagyobb közös osztókat. Az eredmény táblázatba foglalva: prímek a 2 kitevője, ha l.nko p = 4k+1 (b(-)p vagy b(+)p , p) = p x n = x 1 + (n-1)*d p = 4k+3 b (-)p vagy b (+)p xn n = 1, 2, 3,∞ x1 d (<) és (>) 3 b (-)p ↔ (p-1)/2 1, 3, 5, x n =1+(n-1)*2 1 2 3 b (+)p ↔(p+1)/2 0, 2, 4, 6, 8, x n =0+(n-1)*2 0 2 5 b (-)p ↔ (p-1)/2 3, 7, 11, x n =3+(n-1)*4 3 4 5 b (+)p ↔(p+1)/2 1, 5,

9, x n =1+(n-1)*4 1 4 7 b (-)p ↔ (p-1)/2 2, 5, 8, x n =2+(n-1)*3 2 3 7 b (+)p ↔(p+1)/2 11 b (-)p ↔ (p-1)/2 9, 19, 29, x n =9+(n-1)*10 9 10 11 b (+)p ↔(p+1)/2 4, 14, 24, x n =4+(n-1)*10 4 10 1 13 b (-)p ↔ (p-1)/2 11, 23, 35, x n =11+(n-1)*12 11 12 13 b (+)p ↔(p+1)/2 5, 17, 29, x n =5+(n-1)*12 5 12 17 b (-)p ↔ (p-1)/2 7, 15, 23, x n =7+(n-1)*8 7 8 17 b (+)p ↔(p+1)/2 3, 11, 19, x n =3+(n-1)*8 3 8 19 b (-)p ↔ (p-1)/2 17, 35, 53, x n =17+(n-1)*18 17 18 19 b (+)p ↔(p+1)/2 8, 26, 44, x n =8+(n-1)*18 8 18 23 b (-)p ↔ (p-1)/2 10, 21, 32,. x n =10+(n-1)*11 10 11 23 b (+)p ↔(p+1)/2 29 b (-)p ↔ (p-1)/2 27, 55, 83, x n =27+(n-1)*28 27 28 29 b (+)p ↔(p+1)/2 13, 41, 69 x n =13+(n-1)*28 13 28 31 b (-)p ↔ (p-1)/2 4, 9, 14, x n =4+(n-1)*5 4 5 31 b (+)p ↔(p+1)/2 37 b (-)p ↔ (p-1)/2 35, ? x n =35+(n-1)*36? 35 36 37 b (+)p ↔(p+1)/2 17, ? x n =17+(n-1)*36? 17 36? 41 b (-)p ↔

(p-1)/2 19, 39, 59 x n =19+(n-1)*20 19 20 41 b (+)p ↔(p+1)/2 9, 29, 49. x n =9+(n-1)*20 9 20 43 b (-)p ↔ (p-1)/2 13, 27, 41, x n =13+(n-1)*14 13 14 43 b (+)p ↔(p+1)/2 6, 20, 34, x n =6+(n-1)*14 6 14 47 b (-)p ↔ (p-1)/2 22, ? x n =22+(n-1)*23? 22 23? 47 b (+)p ↔(p+1)/2 ? ? 53 b (-)p ↔ (p-1)/2 51,? x n =51+(n-1)*52? 51 52 53 b (+)p ↔(p+1)/2 25,? x n =25+(n-1)*52? 25 52? 59 b (-)p ↔ (p-1)/2 ? ? ? ? 59 b (+)p ↔(p+1)/2 28, ? x n =28+(n-1)*58? 28 58? 61 b (-)p ↔ (p-1)/2 ? ? ? ? 61 b (+)p ↔(p+1)/2 29, ? x n =29+(n-1)*60? 29 60? 67 b (-)p ↔ (p-1)/2 ? ? ? ? 67 b (+)p ↔(p+1)/2 32, ? x n =32+(n-1)*66? 32 66? 71 b (-)p ↔ (p-1)/2 34, ? x n =34+(n-1)*35? 34 35? 71 b (+)p ↔(p+1)/2 ? ? 73 b (-)p ↔ (p-1)/2 8, 17, 26, x n =8+(n-1)*9 8 9 73 b (+)p ↔(p+1)/2 79 b (-)p ↔ (p-1)/2 38, ? x n =38+(n-1)*39? 38 39? 79 b (+)p ↔(p+1)/2 ? ? 83 b (-)p ↔ (p-1)/2 ? ? ? ? 83 b (+)p

↔(p+1)/2 40, ? x n =40+(n-1)*82? 40 82? 2 89 b (-)p ↔ (p-1)/2 10, 21, 32, 89 b (+)p ↔(p+1)/2 97 97 x n =10+(n-1)*11 10 11 b (-)p ↔ (p-1)/2 47, ? x n =47+(n-1)*48? 47 48 b (+)p ↔(p+1)/2 23, ? x n =23+(n-1)*48? 23 48? A legtöbb prímhez kettő darab x 1 érték tartozik. A kisebbiket jelölése a továbbiakban x 1(<) , a nagyobbiké x 1(>) . Első ránézésre ez a táblázat kuszának tűnhet, de tanulmányozva azt számos szabályszerűséget találhatunk. A kérdőjelek a számítás hiányát, illetőleg az adat kérdésességét jelzik (Úgy véltem, hogy x > 40 esetében a 2x túl nagy szám ahhoz, hogy megbízható legyen a számítógéppel kapott eredmény.) Megjegyzés: Ha egy „p”-hez két sorozat „x” tartozik, akkor az „x 1(>) ” számmal kezdődő sorozat nincs kiemelve. A b (-)p –hoz 9 db x 1(<) tartozik, ezek az alábbiak: p 3 7 23 31 47 71 73 79 89 x 1(<) 1 2 10 4 22 34 8 38 10 A b (+)p –hez 15 db x

1(<) tartozik, ezek az alábbiak: p 3 5 11 13 17 19 29 37 41 43 53 59 61 67 83 97 x 1(<) 0 1 4 5 3 8 13 17 9 6 25 28 29 32 40 23 Három x 1< érték mindkét táblázatban előfordul, ezek a következők: x 1(<) p p b (-)p b (+)p 1 4 8 3 31 73 5 11 19 Az x 1(<) = 4, mind a 3-at, mind a 11-et a b (+)p kifejezéssel jelzi! Az x 1(<) = 10, mind a 23-at, mind a 89-et a b (-)p kifejezéssel jelzi! Csak ez a két ilyen tulajdonságú kitevő van a vizsgált tartományban. A vizsgált intervallumhoz tartozó legnagyobb x 1(<) érték a p = 83 hoz tartozó x 1(<) = 40. A fenti táblázatból nem tűnik ki azonnal, de leellenőrizhető, hogy x 1(<) = 1 – től 40 -ig nem található olyan x 1(<) érték, amelyhez ne tartozna valamilyen törzsszám! Ha a kettő hatványkitevőihez 1-től 40-ig kigyűjtjük az összes prímet, amelyeknél a legnagyobb közös osztók: l.nko(b (-)p , a ) és a lnko( b (+)p , a) egyenlők a prímszámokkal alábbi

kiosztást kapjuk: Pirossal kiemelve, illetve vastagítva vannak azok a prímek, amelyekhez tartozó hatványkitevő a legkisebb, vagyis ezek az .x 1(<) értékek (Első előfordulás.) xn 0 „p” ↔ b (-)p - „p” ↔ b (+)p 3 xn 21 „p” ↔ b (-)p 3; 23; 89 „p” ↔ b (+)p 5; 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3 7 3; 5 31 3; 7 3; 5; 17 7; 73 3; 11; 23; 89; 3; 5; 7; 13 3; 43 7; 31 3; 5; 17; 3; 7; 19; 73 3; 5; 11; 31; 41; 7; 5 17 3; 11 5; 13 3; 43 3; 19 5; 41; 3; 17 3; 5; 29 3; 11 3; 5; 13; 37; 3; 3; 43; 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 47; 3; 5; 7; 13; 17; 31; 3; 7; 73 3; 5; 29; 43 3; 7; 11; 31; 3; 5; 17; 7; 23; 89 3; 5; 31; 71; 3; 5; 7; 13; 19; 37; 73; 3; 7; 79; 3; 5; 11; 17; 31; 41; - 3; 97; 3; 11; 5; 53; 3; 19; 17; 3; 59; 5; 13; 41; 61; 3; 3; 67; 3; 11; 43 17; 3; 5; 3; 3; 83 A vizsgált 24 db páratlan prímszám közül 11 db p = 4k+1 alakú és 13 db p = 4k+3 alakú. Mindegyik prímszámhoz található

végtelen sok olyan 2x hatvány, amelynél vagy a (b (-)p , p) vagy a (b (+)p , p), vagy mind a kettő legnagyobb közös osztó egyenlő valamelyik „p”- vel. Az „x” kitevők számtani sorozatokat alkotnak. Egy adott „p” – hez tartozó számtani sorozatok első eleme, az x 1(<) az, amelyet a további számításoknál használni fogunk, és x min – nel jelölünk. Ha egy bizonyos „p” - hez két „x” sorozat is tartozik, akkor természetesen x 1(<) < x 1(>) , és megfigyelhető, hogy a vizsgált „p” számok többségénél (5, 11, 13, 17, 19, 29, 37, 41, 43, 53, stb. ) x 1(>) = 2*x 1(<) +1 p = 3 –nál viszont x 1(>) = 3*x 1(<) +1 Megfigyelhető továbbá az is, hogy ezeknek a számtani sorozatoknak x 1(<) -hez és x 1(>) -hez tartozó differenciája „d” egy és ugyanaz az érték. A „p” számok többségénél (3, 5, 11, 13, 19, 29, stb.) ez a differencia d = p-1 Más „p” prímeknél, (például: 7, 17, 23, 41, stb)

a differencia d = (p-1)/2. p = 31-nél a d = (p-1)/6 = 5 Egyes prímeknél csak az egyik legnagyobb közös osztó, a l.nko(b (-)p , p) = p, ad az „x n ”-re sorozatot, mert a l.nko(b (+)p , p) mindig egyenlő eggyel a vizsgált intervallumban A p ↔ d párok a következőek a vizsgált tartományban: 7 ↔ 3, 23 ↔ 11, (31 ↔ 5), 47 ↔ 23, (71 ↔ 35?) , 73 ↔ 9, (79 ↔ 39?), 89 ↔ 11. Ezeknél, ha (p-1)/2 prímszám, akkor ez a prím lesz a differencia, vagyis d = (p-1)/2, ha (p-1) osztható 8-cal, akkor d = (p-1)/8, a p = 31 kivételes, ennél a számnál d = 5. Az x 1(<) = d - 1 a szóban forgó prímeknél, vagyis, ha p = 7, 23, 31, 47, 71, 73, 79, 89. A legtöbb p-nél x 1(<) = (d/2)-2 (például a p= 11, 13, 17, 19, 29, 41, 43, ) 4 Rendezzük a p ↔ x 1(<) és p ↔ x 1(>) párokat csoportokba: Nézzük először a p ↔ x 1(<) csoportokat! 1. p 3 x 1(<) 0 5 1 7 11 13 19 23 2 4 5 8 10 29 13 37 17 47 22 53 59 61 67 71 79 83 25 28 29 32 34

38 40 Itt x 1(<) = (p-3)/2 illetve átrendezve p = 2* x 1(<) + 3 Erre a képzeletbeli egyenesre a 3 ≤ p ≤ 97 intervallumban 17 pont illeszkedik. 2. p x 1(<) 17 41 97 3 9 23 Itt x 1(<) = (p-5)/4 illetve p = 4* x 1(<) + 5 Erre az egyenesre a 5 ≤ p ≤ 97 intervallumban 3 pont illeszkedik. 3. p 31 43 x 1(<) 4 6 Itt x 1(<) = (p-7)/6 illetve p = 6* x 1(<) + 7 Erre az egyenesre a 5 ≤ p ≤ 97 intervallumban 2 pont illeszkedik. 4. p x 1(<) 73 89 8 10 Itt x 1(<) = (p-9)/8 illetve p = 8* x 1(<) + 9 Erre az egyenesre a 5 ≤ p ≤ 97 intervallumban 2 pont illeszkedik. Láthatjuk, hogy a vizsgált tartományban, ha „p” > 3 a p ↔ x 1(<) számpárok olyan egyenesekre illeszkedő pontok, amelyeknek általános képlete p = (2*j) x 1(<) + (2j+1) ahol j = 1, 2, 3 A 3 ≤ p ≤ 97 intervallumhoz egy pont és négy egyenes tartozik. Feltételezhető, hogy a 97-nél nagyobb prímszámoknál újabb és újabb p = (2*j) x 1(<) + (2j+1)

képletű egyenesekre illeszkednek a számpárok, és ezeknek az egyeneseknek a száma feltehetően végtelen. Az egy egyenesre illeszkedő p ↔ x 1(<) számpárok száma valószínűleg szintén végtelen, bár egyre jobban megritkulnak. Az y = 2j x 1(<) +2j+1 általános képlettel és „j” paraméterrel megadott egyenesek egy közös pontban metszik egymást, azaz sugárszerűen innen indulnak ki a pozitív koordináták irányába. Ez a pont a x = -1 , y = 1 pont, amelyhez természetesen prímszám nem tartozhat, mert az „egy” a definíció szerint nem prím. Mindegyik egyeneshez tartozik egy legkisebb prímszám, amit p kezdő –nek nevezünk el. Felállítható egy táblázat, amely a j növekvő értékeihez rendeli a p kezdő –ket. 5 j p kezdő 1 5 2 17 3 31 4 73 Vizsgáljuk meg azt, hogy az összetartozó p és x értékek összege s = p +x értékek hogyan függnek külön – külön a p-től illetve az x-től. Természetesen lineáris

összefüggéseket kapunk itt is. 1. 5 7 11 13 19 23 29 37 47 53 59 61 67 71 79 83 17 db p 3 x 0 1 2 (3) s 3 6 9 15 18 27 33 42 54 69 78 87 90 99 105 117 123 b (-)p 5 db b (+)p 5 8 10 13 17 22 25 28 29 32 34 38 40 7 23 47 71 79 p 12 db 4 p 3 5 11 13 19 29 37 53 59 61 67 83 s = 3*(p-1)/2 s = 3*(x+1) 2. b (+)p b (+)p b (+)p 17 41 97 3 db p x (5) s 3 20 9 50 23 120 s = 5*(p-1)/4 s = 5*(x+1) 3. 2 db p x (7) s b (-)p b (+)p 31 43 4 35 6 49 s = 7*(p-1)/6 s = 7*(x+1) 4. 2 db p x (9) s b (-)p 73 b (-)p 89 8 81 10 99 s = 9*(p-1)/8 s = 9*(x+1) 6 Látható, hogy az „s” mindig összetett szám, és a jellegzetes együttható páratlan szám. Most állítsuk csoportokba a p ↔ x 1(>) számpárokat: 1. p 3 5 11 13 19 29 37 9 11 17 27 35 x 1(>) 1 3 Itt p = x 1(>) + 2 Erre a képzeletbeli egyenesre 7 db számpár illeszkedik a vizsgált intervallumban. 2. p 17 41 x 1(>) 7 19 p = 2* x 1(>) + 3 3. p x 1(>) 43 13 Ez a pont a vizsgált

intervallumban egymagában áll, de minden valószínűség szerint a p = 3* x 1(>) + 4 egyenesre illeszkedő pont. Az egyenesek paraméteres egyenlete: p = j* x 1(>) + (j+1) ahol j = 1, 2, 3 Ezek a képzeletbeli egyenesek is a p = 1; x = -1 pontból indulnak ki. A sorozatokhoz tartózó kezdő prímszám: j p kezdő 1 3 2 17 3 43 Természetesen abból a tényből, hogy a 100-ig előforduló prímszámokra ezek a szabályszerűségek igazak nem vonható le az a következtetés, hogy ezek a szabályszerűségek általános érvényűek, és az összes prímszámra érvényben vannak! Úgy tűnik, hogy a sok szabályszerűség ellenére sem lehet kiszámítani, hogy egy bizonyos prímszámhoz milyen x 1(<) tartozik. * 7 A 2k – 1 és a 2k + 1 alakú prímszámokhoz tartozó „x” kitevő egyenlő (k-1) – gyel. Példák: Az x = 1 – 40 intervallumban 1. k 2 3 5 7 11 13 17 19 23 p = 2^k-1 2^2-1 2^3-1 2^5-1 2^7-1 2^11-1 2^13-1 2^17-1 2^19-1 2^23-1 p 3 7 31 127 2047

8191 131071 524287 8388607 x 1 2 4 6 10 12 16 18 22 k p = 2^k-1 p x 29 31 37 2^29-1 2^31-1 2^37-1 536870911 2147483647 137438953471 28 30 36 Az összes ilyen típusú prímet a „b (-)p ” kifejezéssel lehet megtalálni. Itt a „k” értékek prímszámok, minden más páratlan „k” érték összetett számot állít elő. 2. A b (+)p kifejezéssel a 2k + 1 alakú prímek találhatóak meg. Az x = 1 – 40 intervallumban k p= 2^k+1 p x 2 2^2+1 5 1 4 2^4+1 17 3 8 16 32 2^8+1 2^16+1 2^32+1 257 65537 4294967297 7 15 31 A „k” értékek a kettő hatványai, minden más páros „k” érték összetett számot állít elő a vizsgált intervallumban. Egy egyszerű algoritmus a 1012 –nél kisebb számok összetett illetve prím voltának megállapítására Legyen „a” a vizsgált páratlan egész szám. Ha az „a” szám összetett, akkor a = p 1 *p 2 p 3 p i p m alakú, ha prím, akkor a = p. Állítás: Ha az „a” összetett szám, akkor mindig van az

„x” értékeknek legalább egy olyan számtani sorozata, amelynek bármely eleméhez tartozó l.nko(b (-)a ,a) és lnko(b (+)a ,a) legnagyobb közös osztók közül az egyik, vagy mindkettő egyenlő az „a” szám törzstényezői közül valamelyikkel, vagy az „a” szám néhány (min. kettő darab) törzstényezőjének szorzatával, vagy magával az „a” számmal. 8 A vizsgálatot az összes olyan x min értékre el kell végezni, amelyek az „a” szám négyzetgyökénél kisebb prímszámokhoz tartoznak. Ha az összes említett x min re lnko(b (-)a , a) és l.nko(b (+)a , a) egyenlő 1-gyel, akkor a vizsgált szám prímszám Azoknál az x n értékeknél, amelyek több törzstényezőt is jeleznek, és a vizsgált számnak éppen ezek a törzstényezői, akkor a legnagyobb közös osztó a törzstényezők szorzata. pl: 255 = 3*517 Az összes törzstényezőt jelző x = 7-hez tartozó l.nko(b 255 , 255) = lnko(((2551)/2+128), 255) = 255 A 255-ről mégis

kiderül, hogy összetett, mert más x értékeknél pl: x = 1 – nél nincs ilyen átfedés. Az l.nko(b (-)a , a), és/vagy a lnko(b (+)a ,a) legnagyobb közös osztók segítségével 1012 = 10201-nél kisebb számok összetett, vagy prím voltát megbízhatóan megállapíthatjuk, ha 1-től 40-ig minden x értékre meghatározzuk a l.nko(b (-)a , a) és lnko(b (+)a ,a) legnagyobb közös osztókat. Csak egyetlen számnál kapunk hamis eredményt, és ez a szám a 23*89 = 2047, mert az x = 10 mind 23 -at, mind a 89-et ugyanazzal a l.nko(b (-)a , a) –val jelzi, és ezért a közös osztó 2047- lesz, vagyis éppen a vizsgált számmal a 2047-tel lesz azonos, és ez csak a prímszámoknál szokott így lenni. A módszer mindegyik olyan 10201 nél nagyobb„a” összetett számnál is helyes eredményt ad, amelynek van legalább egy 101-nél kisebb törzstényezője. Vannak természetesen olyan 97-nél nagyobb prímek, amelyekhez tartozó x min kisebb 40-nél. Nézzünk erre

példákat a p = 101 –től p = 307 –ig tartó egész számok között! b (-)p - vel jelzettek: p 127 151 223 x min 6 14 36 és b (+)p -vel jelzettek: p 109 113 137 157 229 233 241 251 257 281 x min 17 13 33 25 37 28 11 24 7 34 (Elképzelhető, hogy 307-nél nagyobb prímszámok között is vannak ilyenek, de nem vizsgáltam.) Ha egy „a” számnak a legkisebb prímtényezője mondjuk 281, akkor a vizsgált kitevő tartomány x min = 1 – 40 jelzi az „a” szám összetett voltát. PrintScreen példák a Microsoft Excel alkalmazásból: 9 10 Az algoritmushoz minimálisan szükséges „x” értékek sorozata: Az „a” szám nagysága egyértelműen behatárolja a minimálisan szükséges különböző „x” értékek számát, amelyekkel elegendő kiszámolni az említett l.nko-kat ahhoz, hogy az „a” számról kiderüljön összetett szám-e, avagy prím. Ezeket az x, értékeket úgy kaphatjuk meg, hogy megkeressük azt a legnagyobb prímszám négyzetet (p

k 2), amely kisebb, mint „a”. Ennek a négyzetszámnak a négyzetgyökéhez tartozó „x min ” érték lesz a 3-tól (p (k+1) 2 -2) -ig tartó intervallumhoz tartozó utolsó x érték, amely értékét tekintve nem biztos, hogy a legnagyobb az „x” értékek sorozatában. Például: x = 23 p = 97-nél, és x = 40 p = 83 –nál A fenti példát illusztráló ábrán nincsenek az excel tábla elrejtett sorai és oszlopai. Az b (-)a és b (+)a számításhoz tartozó x értékek „a”törzst ényezője „p i ” p i+1 2 intervallum 3 ↔ (p i+1 22) a 3 ↔ (p i+1 2-2) –ben a b (-)a kifejezésben a 2x-hez használandó legkisebb kitevő értékek: x min a 3 ↔ (p i+1 2-2) –ben a b (+)a kifejezésben 2x-hez használandó legkisebb kitevő értékek: x min 3 5 7 11 13 17 19 23 29 31 37 41 25 49 121 169 289 361 529 841 961 1369 1681 1849 3↔23 3 ↔ 47 3 ↔ 119 3 ↔ 167 3 ↔ 287 3 ↔359 3 ↔ 527 3 ↔ 839 3 ↔ 959 3 ↔ 1367 3 ↔ 1679 3 ↔ 1847 1 1 1; 2 1;

2; 1; 2; 1; 2; 1; 2; 1; 2; 10 1; 2; 10; 1; 2; 10; 4 1; 2; 10; 4; 1; 2; 10; 4; 1 1; 1; 4 1; 4; 5 1; 4; 5; 3; 1; 4; 5; 3; 8; 1; 4; 5; 3; 8; 1; 4; 5; 3; 8; 13; 1; 4; 5; 3; 8; 13; 1; 4; 5; 3; 8; 13; 17; 1; 4; 5; 3; 8; 13; 17; 9; b (-)a , és b (+)a –hez szükséges kitevők darabszáma együttesen: 1 1 2 3 4 5 6 7 8 8 9 10 A x-ek sorozatában a legnagyobb x érték. 1 1 2 4 5 5 8 10 13 13 17 17 11 43 2209 3 ↔ 2207 1; 2; 10; 4; 47 2809 3 ↔ 2807 1; 2; 10; 4; 22; 53 3481 3 ↔ 3479 1; 2; 10; 4; 22; 59 3721 3 ↔ 3719 1; 2; 10; 4; 22; 61 4489 3 ↔ 4487 1; 2; 10; 4; 22; 67 5041 3 ↔ 5039 1; 2; 10; 4; 22; 71 5329 3 ↔ 5327 73 6241 3 ↔ 6239 79 6889 3 ↔ 6887 83 7921 3 ↔ 7919 1; 2; 10; 4; 22; 34; 1; 2; 10; 4; 22; 34; 8 1; 2; 10; 4; 22; 34; 8; 38 1; 2; 10; 4; 22; 34; 8; 38 89 9409 3 ↔ 9407 1; 2; 10; 4; 22; 34; 8; 38; 97 10201 3↔ 10199 1; 2; 10; 4; 22; 34; 8; 38; 1; 4; 5; 3; 8; 13; 17; 9; 6 1; 4; 5; 3; 8; 13; 17; 9; 6; 1; 4; 5;

3; 8; 13; 17; 9; 6; 25 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29; 32 1; 4; 5; 3; 8;13; 17; 9; 6; 25; 28; 29; 32; 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29; 32; 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29; 32; 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29; 32; 40 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29; 32; 40; 1; 4; 5; 3; 8; 13; 17; 9; 6; 25; 28; 29; 32; 40; 23 11 17 12 22 13 25 14 28 15 29 16 32 17 34 17 34 18 38 19 40 20 40 21 40 Eddig csak a b (-)p és a b (+)p kifejezésekkel végeztük a vizsgálatot most nézzük meg mi a helyzet a c (+)p és a c (-)p kifejezésekkel. Ha a c (+)p = ABS((p+1)/2-2x), és a c (-)p = ABS((p-1)/2-2x) kifejezésekkel az l.nko(c (-)p , p) = p, és az lnko(c (+)p , p) = p egyenletekből meghatározzuk az „x min ” hatványkitevőket, akkor az összes vizsgált prímszámhoz tartozó hatványkitevők azonosak lesznek a b (-)p = (p-1)/2 + 2x és a b (+)p = (p+1)/2+ 2x

kifejezésekkel kapott értékekkel. c (+)p - vel p 3 x min 1 7 23 31 47 71 73 79 89 2 10 4 22 34 8 38 10 c (-)p - vel p x min 5 11 13 17 19 29 37 41 43 53 59 61 67 83 97 1 4 5 3 8 13 17 9 6 25 28 29 32 40 23 A kapott „x min ” értékek egyezését nézve megállapítható, hogy a b (-)p -nek a c (+)p felel meg, a b (+)p -nek pedig a c (-)p . 12 Kicsi prímszámokkal 7, 13, 17, 19 való oszthatóság. A 3-mal, 5-tel, 11-gyel való oszthatóság szabályai közismertek. Az oszthatósági szabállyal szemben támasztott követelmény: egy egyszerű, könnyen megjegyezhető iteráció legyen. Például a 3-mal való oszthatóság. Ha a vizsgált szám számjegyeinek összege osztható 3-mal, akkor a szám is osztható 3-mal. Ha a számjegyek összege is nagy szám, akkor megismételjük az eljárást, mindaddig, amíg elég kicsi számot kapunk. A 7-tel való oszthatósági szabály nem szerepel az általános iskolai tananyagban, mert nem elég egyszerű. A prímszámokhoz

tartozó x min értékek ismerete viszont könnyen megjegyezhető algoritmust szolgáltat ahhoz, hogy megállapíthassuk, hogy a vizsgált szám vajon osztható-e a kicsi prímszámmal. Ha „a” osztható 7-tel, akkor b a is osztható. A vizsgálatot b a -ból kiindulva folytathatjuk, vagyis a 1 = b a és a 1 –re is meghatározhatunk egy újabb b a értéket, ami legyen b a1 és így iterálva egyre kisebb számokat kapunk. Ha páros számot kapunk az algoritmus valamelyik lépésében, akkor azt oszthatjuk kettővel, mert a felezés az eredeti szám héttel való oszthatóságát nem befolyásolja. Példa: Osztható-e 2093 maradék nélkül héttel? [x min = 2], [2x = 4] b (-)a = (a-1)/2 + 4 = (a +7)/2 b a / 2 = 525; b a1 = 266; b a1 / 2 = 133; b a2 = 70; a = 2093; b a = 1050; b a2 / 2 = 35; b a3 = 21; b a4 = 14; b a4 / 2 = 7; Az utolsó b a érték egyenlő héttel, tehát a vizsgált számnak is osztója a 7. A módszer előnye, hogy csak összeadást és felezést használ, nem

szükséges hozzá a szorzótábla ismerete! A módszer természetesen alkalmazható a 3-mal, 5-tel, 11-gyel való oszthatóság megállapítására is. 3-nál [x min = 1], [2x = 2], b (-)a = (a-1)/2 + 2 = (a+3)/2 Példa: 1089↔546↔273↔138↔69↔36↔18↔9↔6↔3↔3↔3↔3↔3 5-nél [x min = 1], [2x = 2], b (+)a = (a+1)/2 + 2 = (a+5)/2 Példa: 1045 ↔ 525 ↔ 265 ↔ 135 ↔ 70 ↔ 35 ↔ 20 ↔ 10 ↔ 5 ↔ 5 ↔ 5 ↔ 5 ↔ 5 ↔ 5 11-nél [x min = 4], [2x = 16], b (+)a = (a+1)/2 + 16 = (a + 33)/2 Példa: 1078 ↔ 539 ↔ 286 ↔ 143 ↔ 88 ↔ 44 ↔ 22 ↔ 11 ↔ 22 ↔ 11 ↔ 22 ↔ 11 ↔ 22 ↔ 11 Ha a vizsgált szám 3-mal is osztható és 11-gyel is, akkor a sorozat csak 33-ra redukálódik le. Példa: 1089 ↔ 561 ↔ 297 ↔ 165 ↔ 99 ↔ 66 ↔ 33 ↔ 33 ↔ 33 ↔ 33 ↔ 33 ↔ 33 ↔ 33 ↔ 33 Példa: Osztható-e 1339 maradék nélkül 13-mal? [x min = 5], [2x = 32], 13 b (+)a = (a+1)/2 + 32 = (a+65)/2 A következő számsorozatot kapjuk az iteráció

során: 1339 ↔ 702 ↔ 351 ↔ 208 ↔ 104 ↔ 52 ↔ 26 ↔ 13 Példa: Osztható-e 1343 maradék nélkül 17-tel? (x min = 3), (2x = 8), b (+)a = (a+1)/2 + 8 = (a+17)/2 A következő számsorozatot kapjuk az iteráció során: 1343 ↔ 680 ↔ 340 ↔ 170 ↔ 85 ↔ 51 ↔ 34 ↔ 17 Példa: Osztható-e 2759 maradék nélkül 31-tel? (x min = 4), (2x = 16), b (-)a = (a-1)/2 + 16 = (a+31)/2 A következő számsorozatot kapjuk az iteráció során: 2759 ↔ 1395 ↔ 713 ↔ 372 ↔ 186 ↔ 93 ↔ 62 ↔ 31 Ha x min ≥ 5, és 2x ≥ 32 a b a illetve b f értékek túl nagyok lesznek a prímosztóhoz viszonyítva, a számsorozat nem redukálódik le a prímosztóra. Ezen úgy segíthetünk, hogy nem csak a „b”, hanem a „c” kifejezéseket is felhasználjuk a vizsgálathoz. Példa: 13-mal [x min = 5], [2x = 32], b (+)a = (a+1)/2 + 32 = (a+65)/2 és c (-)a = abs((a-1)/2 – 32) = abs((a-65)/2) Csak „c”-vel 151619 ↔ 75777 ↔ 37856 ↔ 18928 ↔ 9464 ↔ 4732 ↔ 2366 ↔ 1183

↔ 559 ↔ 247 ↔ 91 ↔ 13 A módszer elvileg alkalmas maradékszámításra is bizonyos osztóknál! Példa: Mennyi 36, 37, 38, 39, 40, 41, 42 számok 7-tel való osztásának maradéka: Alkalmazva 7-es osztóra a fenti algoritmust az alábbi számsorozatokat kapjuk: i=1 a = 36 a = 37 a = 38 a = 39 a = 40 a = 41 a = 42 2 18 22 19 23 20 24 21 3 9 11 13 15 10 12 14 4 8 9 10 11 5 6 7 5 4 8 5 9 6 3 7 6 2 4 6 8 3 5 7 7 1 2 3 4 5 6 7 8 4 1 5 2 6 3 7 9 2 4 6 1 3 5 7 10 1 2 3 4 5 6 7 11 4 1 5 2 6 3 7 12 2 4 6 1 3 5 7 13 1 2 3 4 5 6 7 14 4 1 5 2 6 3 7 Látható, hogy mindegyik sorozat végén 3 elemből álló szakaszok ismétlődnek a végtelenségig. A 7-es osztó esetében kétféle szakasz létezik: az 1, 4, 2 és az 5, 6, 3. A három elem egyike a vizsgált szám maradéka 7-re. Ha a fenti táblában az oszlopokat „i” sorszámmal látjuk el és a 14 vizsgált szám kapja az egyes sorszámot, akkor a maradék a 7, 10, 13, oszlopban lesz. Tehát a vizsgált szám

nagyságától függően az osztási maradék a 7-ik, 10-ik, 13-ik, vagy a (3*i +7)-ik szám a sorozatban, ha a vizsgált szám sorszáma az egyes. Az i = 0, 1, 2, 3, stb A sorozat hányadik eleme a maradék a 3, 5, 7, 11, 17, 31 prímosztók esetében? 2x Osztó 3 5 7 2 2 4 11 16 17 8 31 16 állandósuló szakasz 2, 1 3, 4, 2, 1 1, 4, 2 vagy 5, 6, 3 7, 20, 10, 5, 19, 26, 13, 23, 28, 14, 1, 9, 13, 15, 16, 8, 4, 2 6 féle 10 elemű szakasz létezik hányadik elem a maradék 2*i+3 ha i = 0, 1, 2, 4*i+5 3*i+7 10*i+11 8*i+17 ha i = -1, 0, 1, 2, 3, 10*i+11 Bár kisebb vizsgált számoknál fejben is leellenőrizhető a 7-tel való oszthatóság, de Excel táblában csak egy autókitöltő húzással egy pillanat alatt megkapjuk az eredményt. Példa: Egy példa a maradék meghatározásra: Az algoritmusban előállított számsorozat csökkenésének üteme: 15 7-tel való oszthatóság vizsgálata esetén Fordítsuk meg az iteráció irányát 0 –ből, vagy 7-ből

kiindulva. Rendezzük át a c (+)7 = (a+1)/2 -4 képletet kifejezve belőle „a”-t. a = 2*(c (+)7 +4) -1. c (+)7 kiindulási értéke legyen 0. A kapott „a” lesz az új c (+)7, és így tovább A következő sorozatot kapjuk: Index: „j” „a” „a” 0 0 0 1*7 1 7 (1+2)*7 2 21 3 4 5 6 49 105 217 441 (2^0+2^1+2^2)*7 (1+2+4+8)7 (1+2+4+8+16)*7 stb. Látható, hogy az „a” –ra kapott számsorozat elemeit a kettő hatványaiból előállított mértani sorozat részösszegeinek héttel való szorzatai alkotják. A mértani sorozat összegképletét felhasználva a „j”-dik elem a j = (2j – 1)*7, vagyis egy hatványfüggvény, amely meglehetősen gyorsan növekszik. A mértani sorozat első eleme egyenlő eggyel Ha az oszthatóságot vizsgáljuk a számok csökkenése is exponenciális jellegű. 13-mal való oszthatóság vizsgálata esetén A c (-)13 = (a-1)/2 -32 –ből a = (c (-)13 +32)*2+1 A c (-)13 kezdőértéke legyen 0. A következő sorozatot kapjuk:

Index: „j” „a” „a” 0 0 0 1 2 3 4 5 65 195 455 975 2015 1*513 (1+2)*513 (2^0+2^1+2^2)513 (1+2+4+8)513 (1+2+4+8+16)513 Itt azt kapjuk, hogy a „j”-dik elem a j = (2j – 1)*513 A növekedés itt is exponenciális. A 13-as osztónál megjelenik egy ötös szorzó, ezért nehéz egyszerű szabályt alkotni a számsorozatból való maradék meghatározására! 2x Osztó 13 32 43 64 állandósuló szakasz 6 féle 12 elemű szakasz létezik 14 elemű szakaszok hányadik elem a maradék a szakasz egyik eleme sem tartalmazza explicit módon a maradékot (a 13 szerencsétlen szám) a szakaszokból a maradék nem olvasható ki Készítette: Haskó György mérnök-tanár 16