Matek feladat: Hány olyan természetes szám van 1-től 720-ig amelyre teljesül, hogy a szám és a 720 legnagyobb közös osztója 1?

Ha két számnak 1 a legnagyobb közös osztója, akkor tulajdonképpen nincs közös osztójuk.

Tehát, olyan számokat kell kiválogatni, amelyeknek nincs közös osztójuk 720-szal.

Egy szám osztóit törzstényezőkre (prímszámokra) való bontással lehet megállapítani.

Ezt nem írom le lépésről lépésre, csak az eredményt: 720 törzstényezős alakja 2*2*2*2*3*3*5. Másképp: 2^4 * 3^2 * 5.

Az ezekből a tényezőkből kialakítható számoknak és a 720-nak vannak közös osztói (az 1-en kívül is). A maradéknak pedig nincs.

Miket lehet a 720 törzstényezőiből összeállítani?

Ezekhez a számokhoz nem kell mindent felhasználni, hisz akkor csak a 720 adódna.

Nézzük például a 3-at. Vehetünk belőle 0, 1 és 2 darabot. (2-től többet nem, mert többször nem szerepel a 720-ban és a több az nem lehetne közös.)

Ez 3-féle eset.

Az 5-öt vagy vesszük, vagy nem. Ez 2-féle eset.

Ha ezeket kombináljuk, akkor 3*2, azaz 6-féle esetet kapunk, ami 6 szám.

Pl.:

ha 5-öt használjuk, akkor

- ha 3-ból 0 darabot veszünk, akkor 5 a szám.

- ha 3-ból 1 darabot veszünk, akkor 3*5=15 a szám.

- 3-ból 2 darabot veszünk, akkor 3*3*5=45 a szám.

Ha 5-öt nem használjuk, akkor

- ha 3-ból 0 darabot veszünk, akkor 0 a szám.

- ha 3-ból 1 darabot veszünk, akkor 3 a szám.

- 3-ból 2 darabot veszünk, akkor 3*3=9 a szám.

Vagyis tényleg 6 szám: 0, 3, 5, 9, 15, 45.

Mivel a 2-ből 4 db volt, vehetünk belőle 0, 1, 2, 3, 4 darabot, azaz 5-félét.

Ha mindegyiket vesszük az előző 6 esethez, akkor 5*6=30 számot kapunk.

Ebben azonban benne van a 0 (ha semmit sem használunk), és benne van a 720 (ha mindet használjuk). Ezeket levonva 28 számot kapunk.

Azaz, 28 számnak van valódi közös osztója a 720-szal. (Ezek maguk a számok, például, 720 és 45 legnagyobb közös osztója 45.)

Így, 1-től 720-ig720-28=692 számnak nincs valódi közös osztója 720-szal. Másképp fogalmazva: 1-től 720-ig720-28=692 számnak és 720-nak csak egyetlen közös osztója van: az 1. (Mivel egyetlen, egyben a legnagyobb közös osztó is.)

Az előző teljesen rossz!

Már eleve a páros számoknak VAN 1-nél nagyobb közös osztója, ezek 360-an vannak.

Ez a feladat tipikus LOGIKAI SZITA típusú feladat.

Az alábbiak szerint kell eljárni:

Odáig rendben van, hogy a 720-nak a 2, 3 és az 5 a prímosztói.

Először kidobjuk a 2-vel osztható számokat, aztán a 3-mal oszthatókat, majd az 5-tel oszthatókat:

720-720/2-720/3-720/5=-24

ez ugye így nem jó, mivel negatív számot kaptunk,

DE!!! ez amiatt van, mert duplám dobtuk ki a 2*3-mal, a 2*5-tel és a 3*5-tel osztató számokat, ezért ezeket vissza kell tennünk:

-24+720/6+720/10+720/15=216

csak most többletünk lett a 2*3*5-tel osztható számokból, így azokat kidobjuk megint:

216-720/30=192

ennyi relatív prím van a 720-hoz