Suurin yhteinen tekijä, joka tunnetaan myös nimellä suurin yhteinen jakaja ja suurin yhteinen tekijä, tarkoittaa suurinta kahden tai useamman kokonaisluvun jakajista.
A:n, b:n suurin yhteinen jakaja on merkitty (a, b). Vastaavasti a:n, b, c:n suurin yhteinen jakaja merkitään (a, b, c). Useiden kokonaislukujen suurimmilla yhteisillä jakajilla on sama merkki.
On monia tapoja löytää suurin yhteinen jakaja. Yleisiä tekijöitä ovat alkutekijöiden jako, lyhyt jako, rullaava vaihejako ja enemmän vähennyslaskua.
Suurin yhteistä jakajaa vastaava käsite on pienin yhteinen kerrannainen, ja a:n, b:n pienin yhteinen kerrannainen kirjataan [a, b].
Jos luku a on jaollinen luvulla b, a:ta kutsutaan b:n kerrannaiseksi ja b:tä a:n jakajaksi.
Sekä jakajat että kerrannaiset edustavat yhden kokonaisluvun suhdetta toiseen, eivätkä ne voi olla olemassa yksinään. Esimerkiksi, voimme vain sanoa, että 16 on tietyn luvun kerrannainen ja 2 on tietyn luvun jakaja, mutta emme voi sanoa erikseen, että 16 on kerrannainen ja 2 on jakaja..
Kahden tai useamman kokonaisluvun suurin yhteinen jakaja (SYT), jota kutsutaan myös suurimmaksi yhteiseksi tekijäksi (SYT), on suurin positiivinen luku, joka jakaa ne kaikki täsmälleen (jättämättä jäännöstä).
Esimerkiksi lukujen 18 ja 24 SYT on 6, koska 6 on suurin luku, joka jakaa molemmat tasan.
SYT on hyödyllinen:
Murtolukujen sieventäminen alimpiin termeihinsä.
Tekijöihin jakaminen ja matemaattisten yhtälöiden ratkaiseminen.
Suhteiden pelkistäminen yksinkertaisimpaan muotoonsa.
Lukuteorian ongelmien ratkaiseminen, joihin liittyy jaollisuutta tai modulaarista aritmetiikkaa.
Yhteisten kuvioiden löytäminen kokonaisluvuista tai toistuviin rakenteisiin perustuvien algoritmien optimointi.
Se auttaa poistamaan redundanssia ja löytämään tehokkuutta matemaattisissa ja reaalimaailman sovelluksissa.
Kahden luvun SYJ:n löytämiseen on useita menetelmiä:
Tekijöiden listaaminen: Listaa kunkin luvun kaikki jakajat ja etsi suurin yhteinen tekijä.
Alkulukujen tekijöihin jakaminen: Jaa molemmat luvut alkulukutekijöihinsä ja kerro yhteisillä tekijöillä. ykkösiä.
Euklidinen algoritmi: Vähennä toistuvasti pienempi luku suuremmasta tai käytä jakolaskua jakojäännösten kanssa, kunnes jakojäännös on nolla. Viimeinen nollasta poikkeava jakojäännös on SYT.
Esimerkki euklidisesta algoritmista SYT(a, b):
SYT(48, 18):
48 ÷ 18 = 2 jakojäännöstä 12
18 ÷ 12 = 1 jakojäännös 6
12 ÷ 6 = 2 jakojäännöstä 0
→ SYT on 6
Käytä SYT:tä, kun:
Murtolukujen tai suhteiden supistaminen yksinkertaisimpaan muotoon.
Diofantoksen yhtälöiden ratkaiseminen (yhtälöt, joilla on kokonaislukuratkaisuja).
Algoritmien optimointi, jotka sisältävät syklejä, rotaatioita tai osituksia.
Sen määrittäminen, ovatko kaksi lukua relatiivisesti alkulukuja (eli niiden SYT on 1).
Kohteiden jakaminen ryhmiin, joilla on mahdollisimman suuri yhtä suuri koko (esim. jonkin jakaminen tasaisesti ihmisten tai säiliöiden kesken).
SYT on olennainen osa sekä perusaritmetiikkaa että edistyneempää lukuteoriaa tai algoritmien suunnittelua.
