Suurin yhteinen tekijä

Matematiikassa kahden kokonaisluvun a ja b suurin yhteinen tekijä, merkitään syt(a, b) tai pelkästään (a, b), tarkoittaa suurinta sellaista lukua, joka jakaa molemmat luvut a ja b niin, että lopputulos on kokonaisluku.^[1] Suurin yhteinen tekijä voidaan etsiä jakamalla tarkasteltavina olevat luvut alkutekijöihin. Tällöin lukujen suurin yhteinen tekijä saadaan ottamalla ne alkuluvut, jotka esiintyvät molempien lukujen alkutekijähajotelmassa korotettuna siihen potenssiin, joka on pienempi tämän kyseisen alkuluvun eksponentti lukujen alkutekijähajotelmissa. Suurin yhteinen tekijä on tällöin saatujen lukujen tulo. Siis jos

a = p_{1}^{a_{1}} p_{2}^{a_{2}} \cdot \cdot \cdot p_{n}^{a_{n}}

ja

b = p_{1}^{b_{1}} p_{2}^{b_{2}} \cdot \cdot \cdot p_{n}^{b_{n}}

,

jossa $p_{i}$ on i:s alkuluku, ja jos $p_{i}$ ei ole luvun tekijä, sitä vastaava eksponentti $a_{i}$ tai $b_{i}$ on nolla, saadaan suurin yhteinen tekijä kaavasta

s y t (a, b) = p_{1}^{m i n (a_{1}, b_{1})} p_{2}^{m i n (a_{2}, b_{2})} \cdot \cdot \cdot p_{n}^{m i n (a_{n}, b_{n})}

Suurin yhteinen tekijä voidaan löytää myös esimerkiksi Eukleideen algoritmin avulla.

Algebrallinen määritelmä

Algebrallisessa mielessä kokonaislukujen $a_{1}, a_{2}, . . ., a_{n}$ suurimmalla yhteisellä tekijällä tarkoitetaan näiden lukujen virittämän kokonaislukujen renkaan ideaalin virittäjää.

Jos luvut $a_{1}, a_{2}, . . ., a_{n}$ ovat kaikki nollia, niiden virittämä ideaali koostuu pelkästään luvusta $0$ .

Kokonaislukujen rengas $ℤ$ on kommutatiivinen eli vaihdannainen rengas. Lisäksi se on kokonaisalue, toisin sanoen siinä ei ole nollasta eroavia nollanjakajia, ja edelleen niin sanottu pääideaalialue, toisin sanoen sen jokainen ideaali on yhden alkion virittämä.

Väite, että jokainen kokonaislukujen renkaan $ℤ$ äärellisesti viritetty ideaali on yhden alkion virittämä, voidaan todistaa seuraavasti:

Olkoon $I = {c_{1} a_{1} + c_{2} a_{2} + . . . + c_{n} a_{n} | c_{i} \in Z$ kaikilla $i = 1, . . ., n}$ kokonaislukujen $a_{1}, a_{2}, . . ., a_{n}$ virittämä renkaan $ℤ$ ideaali. Olkoon $d$ tämän ideaalin pienin positiivinen alkio ja $d = d_{1} a_{1} + d_{2} a_{2} + . . . + d_{n} a_{n}$ .

Helposti todetaan, että jokainen $d$ :n monikerta sisältyy ideaaliin $I$ .

Olkoon toisaalta $c = c_{1} a_{1} + c_{2} a_{2} + . . . + c_{n} a_{n}$ ideaalin $I$ mielivaltainen alkio ja $c = e d + f$ , jossa $0 \leq f \leq d$ .

Tällöin $f = c - e d = (c_{1} a_{1} + c_{2} a_{2} + . . . + c_{n} a_{n}) - e (d_{1} a_{1} + d_{2} a_{2} + . . . + d_{n} a_{n}) = (c_{1} - e d_{1}) a_{1} + (c_{2} - e d_{2}) a_{2} + . . . + (c_{n} - e d_{n}) a_{n}$ .

Siis $f$ kuuluu ideaaliin $I$ . Jos $f$ on suurempi kuin nolla, saadaan ristiriita luvun $d$ valinnan kanssa. Siis välttämättä jokainen ideaalin $I$ alkio on luvun $d$ monikerta.

Toisin sanoen lukujen $a_{1}, a_{2}, . . . a_{n}$ virittämä ideaali on sama, kuin ko. ideaalin pienimmän positiivisen alkion $d$ virittämä ideaali. Tätä lukua $d$ kutsutaan lukujen $a_{1}, a_{2}, . . ., a_{n}$ suurimmaksi yhteiseksi tekijäksi.

Esimerkkejä

Lukujen 12 ja 15 suurin yhteinen tekijä on 3. Tämä nähdään jakamalla luvut tekijöihin: 12 = 2² · 3 ja 15 = 3 · 5.
Lukujen 132 ja 222 suurin yhteinen tekijä syt(132,222) = 6, koska 132 = 2² · 3 · 11 ja 222 = 2 · 3 · 37.

Yksinkertainen käytännön esimerkki

Olkoon tehtävänä peittää suorakaiteen muotoisen huoneen, jonka leveys a ja pituus b ovat kokonaislukuja, lattia mahdollisimman suurilla keskenään samankokoisilla neliön muotoisilla laatoilla. Miten laatan sivun pituus c on valittava?

Ratkaisun antaa lukujen a ja b suurin yhteinen tekijä suoraan. Siis valitaan c=syt(a,b).

Ominaisuuksia

Jos syt(a, b) = 1, a ja b ovat keskenään jaottomia.^[1]
syt(a, b) = syt(b, a) = syt(|a|, |b|)^[2]
syt(0, a) = a
syt(a, b) = syt(a - kb, b), jossa k on kokonaisluku
Eukleideen algoritmi: syt(a, b) = syt(b, a modulo b)

Käytännössä nopein tapa määrittää kahden luvun suurin yhteinen tekijä on käyttää Josef Steinin vuonna 1961 julkaisemaa binääristä algoritmia, mikäli lukujen alkutekijähajotelmaa ei tunneta.

Katso myös

Lähteet

Malline:Kirjaviite

Viitteet

Malline:Viitteet

Aiheesta muualla

Malline:Commonscat-rivi

↑ ^1,0 ^1,1 Rosen, s. 53
↑ Rosen, s. 54

[r53-1] 1,0 ^1,1 Rosen, s. 53

[2] Rosen, s. 54

[1]

[2]

Suurin yhteinen tekijä

Sisällys

Algebrallinen määritelmä

Esimerkkejä

Yksinkertainen käytännön esimerkki

Ominaisuuksia

Katso myös

Lähteet

Viitteet

Aiheesta muualla

Navigointivalikko

Suurin yhteinen tekijä

Algebrallinen määritelmä

Esimerkkejä

Yksinkertainen käytännön esimerkki

Ominaisuuksia

Katso myös

Lähteet

Viitteet

Aiheesta muualla

Navigointivalikko

Haku