CSOPORTOK ROGYÁSIG - PRÍMEK; ÖSSZETETT SZÁMOK 9. osztály

38. fogás

CSOPORTOK ROGYÁSIG   -   PRÍMEK; ÖSSZETETT SZÁMOK

A csoportalkotásra számos lehetőségünk nyílik. ezek más és más célokat szolgálnak. 

Ezen az órán először ún. teljesítménycsoportokat  szervezünk, mert különböző nehézségű feladatokkal állunk a gyerekek elé, majd az óra végén ún. támogatói csoportokat hozunk létre,  amelyekben segítséget kaphatnak egymástól a szöveges feladattal nehezebben boldoguló tanulók.

Tájékoztassuk az osztályt az óra elején, hogy az óra során körbejárunk és bárkit megkérhetünk a csoportból, hogy fejtse ki, miről szól a csoport munkája, miről szól a megbeszélés, hol tartanak éppen. Ha valaki nem képes erre, a  csoportja „bajba kerül” – pl. több házi feladatot kapnak...

A gyerekek általános iskolában sok mindent tanulnak a prímekről. a középiskolás anyag ezt 9. osztályban átismétli és kiegészíti egy kevés új ismerettel.

- Az óra elején az egyes feladattípusonként kapják meg a csoportok a példákat, önálló munkával oldják meg ezeket. (kb. 15 -20 perc );

- közben a táblára felírtam mindazt, amit a gyerekek „feladatlap” címen egy fénymásolt lapon megkaptak;

- s megkérdezem az önálló munka befejezése után, hogy ki ismer rá az általa oldott feladatra vagy annak esetleg részletére? Ezek a tanulók kijönnek a táblához, s ismertetik társaikkal a megoldási javaslataikat. Ezeket közösen megvitatják azután.

Feladatlap

1.)   1  2  3   4  5  6   7  8   9  10

     

11    12  13  14  15  16  17  18  19  20

21    22  23  24  25  26  27  28  29  30  31  32  33…

2.)

	Írd fel prímek szorzataként!	Osztói	Osztók száma
2
6
600

3. ) 2* 2*3=

      2*3*2 =

      3*2*2 =

Egészítsd ki kitevőkkel az egyenletet, hogy igaz legyen!

12                       =  2^⌂  * 3^⌂

Milyen kapcsolatot fedezel fel a táblázat részei között?

12 osztói :     1                                                                      2     3                       2*2    2*3                       2*2*3

6 db

(2+1) * (1+1) = 6

4.) Megfigyelés:

2;3;5 egymást követő prímek

2 │2*3*5	de         2 †2*3*5 + 1
3│2*3*5	3†2*3*5 + 1
5│2*3*5	5 †2*3*5 + 1

                                                                       Prím született!

Tétel :

Tegyük fel, hogy összesen n db prím létezik, ezek : Ekkor : pⁱ │ p¹ p² p³….pⁿ

de pⁱ │ p¹ p² p³….pⁿ + 1

, azaz tudtunk készíteni egy új prímet!!!

Tehát a prímek száma végtelen!

a)      KERESSÜNK PRÍMEKET!

Az óra elején kijelöljük a csoportokat, mégpedig most matematikából a jelenlegi teljesítményüket illetően hasonló szintű diákokat.

Ez lehetővé teszi számukra, hogy azonos szinten és ütemben dolgozzanak, a tanár pedig differenciálni tudja a feladatokat.

A csoportok egyes feladattípusonként kapják meg a feladatokat. ( A példák itt nehezednek a sorszámuk szerint.)

A gyerekek csoportban dolgozva /meg/oldják a saját feladataikat; közben a táblára a tanár felírja a példák vázát; pl. képleteket, a szita számait…

                                              

Közös megbeszélés.

Utána kapják meg a következő példákat.

b)      OSZTHATÓSÁGI SZABÁLYOK

Itt a differenciálás az átnézett szabályok számában jelenik meg.

c)      SZÁMOK OSZTÓI

A feldolgozás úgy megy, mint az a) részben.

d)      FELADATOK

Újabb csoportokat alkotunk, mégpedig ún. támogatócsoportokat.  Olyan diákok, akik jól értenek a matematikához, összejönnek olyanokkal, akik némi segítségre szorulnak. Így kapják meg a c) rész „szultános – cellás”feladatait.

a)      KERESSÜNK PRÍMEKET!

Definíció :  A prímszámok  : A prímek fogalmát Kr. e. 350-ben Eukleidész vezette be a matematikába, s azon 1-nél nagyobb számok körét alkotják, amelyek csak önmagukkal és eggyel oszthatók maradék nélkül: 2, 3, 5, 7 ,11 ... stb.

1.)    Eratoszthenész szitája a neves ókori görög matematikus, Eratoszthenész módszere, melynek segítségével egyszerű kizárásos algoritmussal megállapíthatjuk, hogy melyek a prímszámok – papíron például a legkönnyebben 1 és 100 között.

A prímszámok keresésének legegyszerűbb módja a „rosta”, avagy Eratoszthenész szitája:

-          vesszük az 2-t ezt bekarikázzunk, mert prímszám, de a többi 2-vel oszthatót(minden másodikat) kihúzzuk. A hármat is bekarikázzuk, de minden harmadikat kihúzunk. A négy ki van húzva, ezért az 5 fog jönni bekarikázzunk, de minden ötödike t(ilyenkor már csak 5-re végződő 5-tel oszthatók maradtak) kihúzunk...

Keresd meg Eratoszthenész szitájának segítségével 100-ig a prímeket!

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

2.)               Definíció :  A prímszámok  : A prímek fogalmát Kr. e. 350-ben Eukleidész vezette be a matematikába, s azon 1-nél nagyobb számok körét alkotják, amelyek csak önmagukkal és eggyel oszthatók maradék nélkül: 2, 3, 5, 7 ,11 ... stb.

Eratoszthenész szitája a neves ókori görög matematikus, Eratoszthenész módszere, melynek segítségével egyszerű kizárásos algoritmussal megállapíthatjuk, hogy melyek a prímszámok – papíron például a legkönnyebben 1 és 100 között.

A prímszámok keresésének legegyszerűbb módja a „rosta”, avagy Eratoszthenész szitája:   minden 3-nál nagyobb számot - szigorúan növekvő sorrendben - megpróbálunk elosztani az összes eddig ismert prímszámmal. Ha valamelyikkel az osztás sikerült, akkor a szám nem prím (például a 4 osztható 2-vel). Ha egyikkel sem tudjuk osztani, akkor az adott szám is prím (például az 5). Ezt a számot hozzávesszük az eddig ismert prímek listájához.    Keresd meg Eratoszthenész szitájának segítségével 100-ig a prímeket!

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

3.)              A Mersenne-prímeket az alábbi képlet állítja elő:

M_p = 2^p - 1

Az interneten ma is folyik a Mersenne-prímek keresése: The Great Internet Mersenne Prime Search. A  2003. november 17-én született eredmény  a 40. Mersenne-prím, 2^20996011 - 1 pontosan 6320430 számjegyű. 
A 41. Mersenne-prím is az előző legnagyobbként ismert prímnél közel 1 millió jeggyel hosszabb: 7 235 733 számjegyből áll, s a 2 ^{24 036 583}-1 formában lehet kifejezni.
Ma a  legnagyobb ismert prím : 2^43112609 − 1   (2008. augusztus 23-i állapot)

Készíts magad is  5 prímet a  M_p = 2^p - 1  ( p prím; Mp az új, keletkező, ún. Merse-prím) képlet segítségével!

4.)        Állíts elő a     p = n² – n + 41 képlettel  ( ahol n természetes szám) prímeket!

Ha n = 1, akkor    p = ……..

Ha n = 2, akkor    p = ……..

Ha n = 3, akkor    p = ……..

Ha n = 4, akkor    p = ……..

Minden n-re prímet kapunk?

Ha n = 41, akkor    p = …41*41 -41 + 41 =

Ha n = 42, akkor    p = …42*42-42 +41 =  41* 42 – 41 = ..

- Ismered a mondást?   „ Egy fecske nem csinál nyarat?”   Hogy’ jön ez most ide??

5.)        Végezd el a kijelölt műveleteket!

2+1

2*3 + 1 =

2*3*5 + 1 =

Régen az emberek azt hitték, hogy a prímszámok között is van legnagyobb, legutolsó. Nos tévedtek, van egy egyszerű szabály az új prímszám megállapítására:
Először is ismerned kell a alapvető prímeket: 2,3,5,7,11,13,17,...
Szorozd össze sorra a prímszámokat majd adj hozzá 1-et.
Ezzel nem tudod megállapítani az összes prímet, mint láthatjátok az 5-öt, 11-et, 13-at és még sok más prímet nem lehet ezzel a módszerrel kiszámolni, de alkossatok azért még néhányat!

2*3*5*7+1=

 2*3*5*7*11+ 1 =

Következménye : Tétel : A prímek száma végtelen.

b) TALÁLSZ-E AZ ALÁBBIAKBAN FELSOROLT OSZTHATÓSÁGI SZABÁLYOK KÖZÖTT SZÁMODRA ISMERTEKET?

Keress közöttük egy újat! Próbáld ki a 1717-es számra vonatkozóan, keresd meg, mely számok lehetnek az osztói!

2: Azok a számok oszthatók 2-vel, amelyeknek utolsó számjegye (egyes helyiértéken álló) osztható 2-vel.
3: Azok a számok oszthatók 3-mal, amelyeknek a számjegyeinek összege is osztható 3-mal.
4: Azok a számok oszthatók 4-gyel, amelyeknek az utolsó két számjegyéből képzett kétjegyű szám is osztható 4-gyel.
5: Azok a számok oszthatók 5-tel, amelyeknek utolsó számjegye is osztható 5-tel.
6: Azok a számok oszthatók 6-tal, amelyek 2-vel és 3-mal is oszthatóak.
7: 7-tel úgy vizsgálhatjuk meg az oszthatóságot, hogy a szám első számjegyétől utolsó előtti számjegyéig képzett számból kivonjuk az utolsó számjegy dupláját(2-szeresét).
Ha az így kapott szám osztható 7-tel akkor az eredeti is. Ha még az így kapott számról sem tudjuk megállapítani, hogy osztható-e 7-tel, akkor ugyanezt a tendenciát kell folytatni amíg olyan számot nem kapunk amiről biztosan meg tudjuk állapítani, hogy osztható 7-tel.
Pl.: 315 -> 31-(2*5)=21. 21 osztható 7-tel, tehát 315 is.
8: Azok a számok oszthatók 8-cal, amelyeknek az utolsó három számjegyéből képzett háromjegyű szám is osztható 8-cal.
9: Azok a számok oszthatók 9-cel, amelyeknek számjegyeinek összege is osztható 9-cel.
10: Azok a számok oszthatók 10-zel, amelyeknek utolsó számjegye is osztható 10-zel, magyarul 0-ra végződik.
11: 11-gyel úgy vizsgálhatjuk meg az oszthatóságot, hogy a szám első számjegyétől utolsó előtti számjegyéig képzett számból kivonom az utolsó számjegyet. Ha az így kapott szám osztható 11-gyel, akkor az eredeti is. Ugyanúgy, mint a 7-tel való oszthatóságnál itt is lehet ismételni ezt a folyamatot, ha még mindig megállapíthatatlan az oszthatóság.
Pl.: 5258-> 525-8=517-> 51-7=44 44 osztható 11-gyel, tehát 5258 is.
12: Azok a számok oszthatók 12-vel, amelyek 4-gyel és 3-mal is oszthatóak.
13: 13-mal úgy vizsgálhatjuk meg az oszthatóságot, hogy a szám első számjegyétől utolsó előtti számjegyéig képzett számhoz hozzáadjuk az utolsó számjegy 4-szeresét.
Ugyanúgy mint a 7-nél is a 11-nél, itt is lehet ismételni a folyamatot.
Pl.: 6175-> 617+(4*5)=637-> 63+(4*7)=91-> 9+(4*1)=13. 13 osztható 13-mal, tehát 6175 is.
14: Azok a számok oszthatók 14-gyel, amelyek 2-vel és 7-tel is oszthatóak.
15: Azok a számok oszthatók 15-tel, amelyek 3-mal és 5-tel is oszthatóak.
16: Azok a számok oszthatók 16-tal, amelyeknek utolsó négy számjegyéből képzett négyjegyű szám is osztható 16-tal.
17: 17-tel úgy vizsgálhatjuk meg az oszthatóságot, hogy a szám első számjegyétől az utolsó előtti számjegyéig képzett számból kivonjuk az utolsó számjegy ötszörösét. A folyamat itt is ismételhető.
Pl.: 132770-> 13277-(0*5)=13277-> 1327-(7*5)=1292-> 129-(2*5)=119. 119 osztható 17-tel, tehát 132770 is osztható 17-tel.
18: Azok a számok oszthatók 18-cal amelyek 2-vel és 9-cel is oszthatóak.
19: 19-cel úgy vizsgálhatjuk meg az oszthatóságot, hogy a szám első számjegyétől az utolsó előtti számjegyéig képzett számhoz hozzáadjuk az utolsó számjegy kétszeresét. A folyamat itt is ismételhető.
Pl.: 7828-> 782+(2*8)=798-> 79+(2*8)=95-> 9+(2*5)=19. 19 osztható 19-cel, tehát 7828 is osztható 19-cel.
20: Azok a számok oszthatók 20-szal, amelyeknek az utolsó két számjegyükből képzett két jegyű szám is osztható 20-szal.
21: Azok a számok oszthatók 21-gyel, amelyek 3-mal és 7-tel is oszthatóak.

C) SZÁMOK OSZTÓI

1.)   3 gyereket kiáll az osztály elé egy-egy „hangszerrel”: pl.  egyikük csettint, másikuk egy fémcipzárt húzogat, a harmadik pedig füttyent. (Lehet persze „szépen”  szóló csengőkkel, stb. is.)Az első a 2-vel, másikuk a 3-mal, a harmadik az 5-tel osztható számokra kelt zajt. Az osztály számol egyesével hangosan.  Pl.:

:

Mikor hallunk egyszerre 2 hangszert? Mikor hármat?

Két hangszer szól azokon a számokon, melyeknek 2, 3és 5 közül pontosan kettő osztója, pl.: 6, 10, 12, stb.

Három hangszert hallunk azzal a számmal, melynek mindhárom szám osztója, pl.: 0, 30, 60 stb.

2.) Keresd meg az alábbi számok összes osztóját!

2 osztói :

3 osztói:

6 osztói:

12    osztói

64 osztói:

100 osztói:

144 osztói:

600 osztói :

6000 osztói:

3.) Írd fel az alábbi számokat prímek szorzataként!

2=

3 =

6 =

            12=

            64 =

            100=

            144=

600=

6000=

4.)    Mely számok prímtényezős felbontásait láthatod itt? Végezd el a szorzást!

2*1 =

2*3=

3*2=

2*3*2=

2*2*3 =

3*2*2*=

2*5*2*5=

2*2*5*5=

5*2*2*5=

2*3*5*7*=

7*3*5*2=

5*2*7*3=

2³ · 3 · 5²=

Mit tapasztalsz?

Válaszolj az alábbi kérdésekre!

Ha egy számnak két prímosztója van (pl. a 2 és a 3), és a szám a két prím szorzata, akkor  mi lehet a szám, és mik lehetnek a szám osztói?

Összesen hány osztója van?

Ha egy számnak három prímosztója van (jelöljük a-val, b-vel és c-vel), és a szám a három prím szorzata, akkor mik lehetnek a szám osztói? Összesen hány osztója van?

Ha egy számnak a prímosztói az 2, a 2, és a 3, és a szám e három prím szorzata, akkor mi lehet a szám és mik lehetnek a szám osztói? Összesen hány osztója van?

Hány osztója van a 2²* 3¹* 5³ –nak?

Hány osztója van egy számnak?

5.)    Keresd meg az alábbi számok összes osztóját! Hány darabot találtál az egyes számoknál?

1 osztói:…………………………;           ……….. db

4 osztói:…………………………;           ……….. db

9 osztói:…………………………;           ……….. db

16 osztói:…………………………;         ……….. db

25 osztói:…………………………;         ……….. db

36 osztói:…………………………;         ……….. db

49 osztói:…………………………;         ……….. db

144 osztói:…………………………;       ……….. .db

600 osztói:…………………………        ………....db

Válaszolj az alábbi kérdésekre!

Ha egy számnak két prímosztója van (pl. a 2 és a 3), és a szám a két prím szorzata, akkor  mi lehet a szám, és mik lehetnek a szám osztói?

Összesen hány osztója van?

Ha egy számnak három prímosztója van (jelöljük a-val, b-vel és c-vel), és a szám a három prím szorzata, akkor mik lehetnek a szám osztói? Összesen hány osztója van?

Ha egy számnak a prímosztói az 2, a 2, és a 3, és a szám e három prím szorzata, akkor mi lehet a szám és mik lehetnek a szám osztói? Összesen hány osztója van?

Hány osztója van a 2²* 3¹* 5³ –nak?

Hány osztója van egy számnak?

d) FELADATOK

  1.)   A szultán börtönében száz cella van, 1-től 100-ig számozva, mindegyikben egy rab. A cellák zárja különleges, mindegyiket ugyanaz a kulcs nyitja és zárja a következőképpen: minden fordítás változtat a zár "állapotán", ha nyitva volt bezárja, ha zárva volt kinyitja. A szultán lánya esküvője alkalmából amnesztiát hirdet. Száz fogdaőrt indít útnak. Az első minden zárban fordít egyet kulcsán. A második már csak minden másodikban, tehát a 2, 4, 6,..., 100-as cellákéban. A harmadik minden harmadikban (3, 6,...). És így tovább, a 100. fogdaőrt már csak a 100-as celláéban. Akinek az ajtója nyitva maradt, az szabadul. Hányan távozhatnak?

2.)    A cellákon annyi zár van, ahányadik cella, tehát a 100. cellán 100 zár van. Az első őr kinyitja az első napon a legelső zárat az összes cellán. A második őr a második napon minden második cellán kinyitja a második zárat, és így tovább. A századik nap után kik szabadulnak ki?

3.)    A  szultán felébred egyik reggel, és mivel nagyon jó napja van, amnesztiát hirdet. De azért nem akarja az összes foglyot elengedni, mert akkor üres lenne a börtön, ezért a következő furfangos megoldást találja ki: Az őr az első nap minden cellát kinyit, a másodikon minden másodikat, a harmadikon minden harmadikat, és így tovább. De ha a zár nyitva van, ő bezárja, ha csukva van, akkor kinyitja. A börtönben 100 cella van, melyiknek az ajtaja lesz nyitva a századik nap után?

Csakhogy ez az őr nagyon nem szereti a páros számokat, így csak páratlan napokon hajlandó előjönni. Így első nap az összes cellában elfordítja a zárat, a harmadik napon minden harmadik cellában, és így tovább. 100 cella van, minden cellán egy zár. A századik nap után melyik cella lesz nyitva?

4.)            Egy szultán 100 lányból választ feleséget. Mind a 100-at bezárják 1-1 szobába. Aztán az első őrt azzal a paranccsal küldi ki, hogy minden záron fordítson egyet, majd a 2. őrt, hogy minden 2.-on fordítson egyet, a 3.őrt, hogy minden 3.-on... így tovább. A 100. őrnek a 100. ajtón kell fordítania egyet. Az a lány, akinek nyílik az ajtaja feleség lesz. Hány felesége lesz a szultánnak?

5.)    A szultán felébred egyik reggel, és mivel nagyon jó napja van, amnesztiát hirdet. De azért nem akarja az összes foglyot elengedni, mert akkor üres lenne a börtön, ezért a következő furfangos megoldást találja ki: Az őr az első nap minden cellát kinyit, a másodikon minden másodikat, a harmadikon minden harmadikat, és így tovább. De ha a zár nyitva van, ő bezárja, ha csukva van, akkor kinyitja. A börtönben 10 cella van, melyiknek az ajtaja lesz nyitva a tizedik nap után?

IDŐKITÖLTŐ

 - Az ikerprím-sejtésnek nevezik azt a sejtést, hogy végtelen sok olyan p prímszám van, amire p+2 is prím. (Mint például 3,5; 5,7; 17,19.) A sejtést először Euklidész fogalmazta meg i. e. 300 körül.
Ez egyike a matematika legreménytelenebb problémáinak.
Az ilyen tulajdonságú p, p+2 párokat hívják ikerprímeknek

-

Adott egy várbörtön, annak 400 cellája, és minden cellában egy-egy rab. A zárak működése a következő: egy fordításra zár, a következő fordításra nyit, utána ismét zár és így tovább. A várúrnak születésnapja van, ezért ezen a napon engedékeny, elküld egy őrt, hogy minden záron fordítson egyet. De így rájön, hogy rab nélkül marad a börtöne, ezért a következőt találja ki: elküldi a második őrt azzal, hogy minden második záron fordítson egyet (másodikkal kezdve), majd küldi a harmadikat, neki minden harmadik záron kell fordítania. És így tovább egészen a 400. őrig, akinek már csak a 400. ajtó zárján fordít egyet. Ezek után, amelyik cella ajtaja nyitva van, azt a rabot szabadon engedik.

Mennyire volt nagylelkű a születésnapját ünneplő várúr, vagyis hány rabot engedett szabadon?

-  - VICC : Hogyan  dönti el a nem matematikus, hogy a páratlan számok mind prímek-e?
Matematikus:
3 - prím
5 - prím
7 - prím
teljes indukció:
minden páratlan szám prím
Fizikus:
3 - prím
5 - prím
7 - prím
9- mérési hiba
11 - prím...
Bölcsész:
3 - prím
5 - prím
7 – prím

Megoldások ( hoz)

Eratoszthenész szitájához : Az algoritmus

1. Írjuk fel a számokat egymás alá 2-től ameddig a prímtesztet elvégezni kívánjuk. Ez lesz az A lista. (Az animáció bal oldalán.)

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

2. Kezdjünk egy B listát 2-vel, az első prím számmal. (Az animáció jobb oldalán.)

3. Húzzuk le 2-t és az összes többszörösét az A listáról.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

4. Az első át nem húzott szám az A listán a következő prím. Írjuk fel a B listára.

5. Húzzuk át az így megtalált következő prímet és az összes többszörösét.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

6. Ismételjük a 3–5. lépéseket, amíg az A listán nincs minden szám áthúzva.

   összetett számok is!!!!!!!

Prímszámok száma végtelen.      Már az ókorban Eukleidész bebizonyította, hogy végtelen sok prímszám. van. Mai megfogalmazással a bizonyítás menete a következő:             Tekintsük az első k darab prímszámot. p₁=2, p₂=3, p₃=5, legyen az utolsó, a k-ik p_k. Szorozzuk össze őket: p₁*p₂*p₃*....*p_k, majd adjunk hozzá 1-t. Az így kapott N= p₁*p₂*p₃*....*p_k +1 szám vagy prím, vagy összetett. Ha prím, akkor különbözik mindegyiktől, amit összeszoroztunk, tehát nem igaz, hogy az összes prímszám szerepel az N szám képzésében. Ha pedig N összetett szám, akkor van prímosztója. De az oszthatóság szabályai szerint ez nem lehet egyik sem a p_k-ig terjedő prímszámok között. Ez azt jelenti, hogy ezzel a módszerrel mindig találhatunk új prímszámot, azaz végtelen sok prímszám van.

Eukleidész ugyanezt így fogalmazta meg Elemek című művében: "Prímszámból prímszámok bármely sokaságánál több van. Legyenek az adott prímszámok a, b és c. Azt állítom, hogy több prímszám van, mint a, b és c. Vegyük ugyanis a, b és c legkisebb közös többszörösét, legyen ez DE, és adjuk hozzá DE-hez a DF egységet. Ekkor EF vagy prím, vagy nem. Legyen először prím. Találtunk tehát az a, b és c számoknál több prímet, a-t, b-t, c-t és EF-t. Ne legyen most EF prím. Ekkor osztja valamelyik prímszám. Osztja a g prím. Azt állítom, hogy g az a, b és c egyikével sem azonos. Tegyük föl ugyanis, hogy az a, b és c osztják DE-t, tehát g is osztja DE-t. Viszont EF-t is osztja, tehát a maradék DF egységet is osztja g, noha szám, ami ellentmondás. A g tehát nem azonos az a, b, c számok egyikével sem. S feltétel szerint prím, tehát találtunk az adott a, b, c prímeknél több prímet, a-t, b-t, c-t, g-t. Éppen ezt kellett megmutatni."

Éppen ezt kellett megmutatni. (Quod erat demonstrandum. Q.E

Összes osztók száma

Vizsgáljuk meg, hogy egy számnak - például 600-nak - hány darab osztója van!

Az osztók számának meghatározásában a prímtényezős felbontás segíthet: 600 = 2³ · 3 · 5²

. Természetes, hogy 600 osztóinak prímtényezős felbontásában nem lehet más prímszám, mint a 2; 3; 5. A 600 osztói között van olyan, amelyben mindhárom prímszám szerepel, van olyan, amelyben a három közül csak kettő, van olyan is, amelyben a három prímszám közül csak egy, és természetesen 600-nak osztója az 1 is. Azt mondhatjuk: az osztókat háromtényezős szorzatként írhatjuk fel. Egy-egy tényező lehet a 2, a 3 vagy az 5 pozitív egész kitevőjű hatványa (a megfelelő kitevőig ), vagy az 1. Írjuk fel ezeket áttekinthető módon:

      1   1   1       2 1       3 1       5 1         2 2          5 2         2 3             Ajánlatos olyan eljárást keresnünk, amellyel minden lehetséges kiválasztást rendre megkapunk. Hány ilyen kiválasztás lehetséges?

A kiválasztottakhoz a második oszlop két száma közül bármelyiket választhatjuk. Ez az előző lehetőségek számát kétszerezi. A harmadik oszlopból a három szám bármelyikét vehetjük harmadik tényezőnek. Ez a 4 · 2 lehetőséget háromszorozza. Ezért a kiválasztás lehetőségeinek száma 4 · 2 · 3.

Emiatt 600 összes osztóinak a száma: 4 · 2 · 3 = 24.

Ezek: 1, 5, 25, 3, 15, 75; 2, 10, 50, 6, 30, 150; 4, 20, 100, 12, 60, 300; 8, 40, 200, 24; 120, 600.

Az előző 4 · 2 · 3 szorzat tényezői 600 prímtényezős felbontásában szereplő prímszámok hatványkitevőinél 1-gyel nagyobb számok.

Ugyanilyen gondolatmenettel bármely a szám osztóinak a számát megkapjuk, ha felírjuk az a szám prímtényezős felbontását, és a prímszámok hatványkitevőinél 1-gyel nagyobb számokat összeszorozzuk. Röviden:

Ha a= p 1   α 1   ⋅ p 2   α 2   ⋅ p 3   α 3   ⋅...⋅ p n   α n    ahol  p 1 , p 2 ,..., p n  különböző prímszámok és  α 1 , α 2 ,... α n  pozitív egész kitevők, akkor az a szám osztóinak a száma: (   α 1  +1  )(   α 2  +1  )...(   α n  +1  ).

A valódi osztók száma ennél 2-vel kevesebb.

A feladatokhoz :

A szultán börtönében száz cella van, 1-től 100-ig számozva, mindegyikben egy rab. A cellák zárja különleges, mindegyiket ugyanaz a kulcs nyitja és zárja a következőképpen: minden fordítás változtat a zár "állapotán", ha nyitva volt bezárja, ha zárva volt kinyitja. A szultán lánya esküvője alkalmából amnesztiát hirdet. Száz fogdaőrt indít útnak. Az első minden zárban fordít egyet kulcsán. A második már csak minden másodikban, tehát a 2, 4, 6,..., 100-as cellákéban. A harmadik minden harmadikban (3, 6,...). És így tovább, a 100. fogdaőrt már csak a 100-as celláéban. Akinek az ajtója nyitva maradt, az szabadul. Hányan távozhatnak?

b) 10
Egy adott cella zárjához csak azok az őrök nyúlnak, amelyek "sorszáma" osztója a cellaszámnak. Ha páros számú osztója van a cellaszámnak, akkor zárva, ha páratlan számú osztója van a cellaszámnak, akkor nyitva lesz (nyit - zár - nyit - zár - stb...). Páratlan számú osztója az osztópárok miatt a négyzetszámoknak (1; 4; 9;16; 25;36; 49; 64; 81; 100) van, ezért 10 rab szabadul.

A cellákon annyi zár van, ahányadik cella, tehát a 100. cellán 100 zár van. Az első őr kinyitja az első napon a legelső zárat az összes cellán. A második őr a második napon minden második cellán kinyitja a második zárat, és így tovább. A századik nap után kik szabadulnak ki?
Megoldás:
a) Segíti a megoldást minden esetben, ha rajzot készítünk. Egy cella akkor lesz nyitva, ha rajta az összes zár nyitva lesz. A második zár melyik cellákon lesz nyitva? Amelyek oszthatóak 2-vel. A harmadik zár azokon lesz nyitva, amelyek oszthatóak 3-mal. Tehát akkor lesz egy cellán az összes zár nyitva, ha az összes „előző” szám osztója.
b) Kettő ilyen szám van: az 1 és a 2, vagyis az első két cella marad nyitva a századik nap után.

Az őrnek az lenne a feladata, mint az előző példában, csakhogy ez az őr nagyon nem szereti a páros számokat, így csak páratlan napokon hajlandó előjönni. Így első nap az összes cellában elfordítja a zárat, a harmadik napon minden harmadik cellában, és így tovább. 100 cella van, minden cellán egy zár. A századik nap után melyik cella lesz nyitva?
Megoldás:
a) nyit (1) – zár - nyit
Mivel az első nap minden cellát kinyit és utána már csak azokat a cellákat nyitja vagy zárja, amelyeknek van még páratlan osztója, azok a cellák biztosan nyitva maradnak, amelyeknek az 1-en kívül nincs más páratlan osztójuk.
Másrészt a többi maradék cellák közül azok lesznek nyitva, amelyeknek páratlan sok osztója van, ugyanúgy, ahogy az alapfeladatban is.
b) Az olyan számok, amelyeknek nincsen az 1-en kívül páratlan osztójuk, a kettőhatványok: 1, 2, 4, 8, … A másik- féle megoldás a négyzetszámok. Tehát egy cella ajtaja akkor lesz nyitva, ha a sorszáma kettőhatvány vagy négyzetszám.

1.)    2.Egy szultán 100 lányból választ feleséget. Mind a 100-at bezárják 1-1 szobába. Aztán az első őrt azzal a paranccsal küldi ki, hogy minden záron fordítson egyet, majd 0 2, őrt, hogy minden 2.-on fordítson egyet, a 3.őrt, hogy minden 3.on... így tovább. A 100, őrnek a 100.ajtón kell fordítania egyet.Az a lány, akinek nyílik az ajtaja feleség lesz. Hány felesége les a szultánnak?

A másodiknál azt kell megoldani, hogy az i-edik or pont az i-vel osztható  számú cellák zárján fordít egyet, tehát egy cella zárján pont annyit fordítanak, ahány osztója van. Azok a lányok szabadulnak ki, akiknek a zárján páratlan sokat fordítottak.
Tehát a kérdés az, hogy hány olyan szám van 1-100 között,melynek páratlan sok osztója van. Gondolkodj azon, hogy mit is jelent, ha egy számnak páratlan sok osztója van, és ha ezt megérted, akkor megvan a feladat.