Mikä on GCD & LCM Lkysyin?
Suurin yhteinen jakaja (SUH) ja pienin yhteinen monikerta (KYM) ovat kaksi keskeisintä lukuteorian käsitettä. SUH on suurin luku, joka jakaa molemmat luvut puhtaasti. KYM on pienin positiivinen luku, joka on jaettavissa molemmilla luvuilla.
Milloin käyttää tätä laskuria
- Murtolukujen yksinkertaistaminen: jaa osoittaja ja nimittaja SKJ:lla
- Murtolukujen lisääminen tai vähentaminen eri nimittajilla: etsi nimittajien PYT
- Aikataulutusongelmat: maarita, milloin kaksi aikataulullista tapahtumaa seuraavat yhteen
- RSA-salakirjoitus: tarkista, että salaustehostin on keskenaan jaottoman phi(n):n kanssa
- Voimansiirto-suhteiden laskenta: etsy pienin hammasluku annetulle suhteelle
- Laatto-kuvioinnit: maarita pienin toistuva yksikko suorakulmaisille laatoille
Vaiheet:
- Syötä kaksi positiivista kokonaislukua a ja b.
- Käytä kokonaisjakoa: a = q×b + r.
- Korvaa a luvulla b ja b luvulla r. Toista kunnes r = 0.
- Viimeinen nollasta poikkeava jakojäkki on SYY.
- Laske PYY = |a × b| / SYY käyttäen perusidentiteettiä.
- Käytä Useita Lukuja -tilaa kolmelle tai useammalle luvulle.
Kaava
Eukleideen algoritmi:
GCD(a, b) = GCD(b, a mod b) kunnes b = 0
KYM SUH:sta:
LCM(a, b) = |a × b| ÷ GCD(a, b)
Käyttötapaukset
- Murtolukujen sieventäminen: jaa nimittäjä ja osoittaja SYY(a, b):llä
- Erien nimittäjillä olevien murtolukujen yhteenlasku: etsi nimittäjien PYY
- Aikataulutus: etsii, milloin kaksi toistuva tapahtuma seuraavan kerran koittuu samanaikaisesti
- RSA-avainten generointi: tarkistaa, että eksponentti e on yhteenkuuluva φ(n):n kanssa
- Vaihteistosuhde-ongelmat koneensuunnittelussa
- Laattakuvion suunnittelu: etsii pienimmän toistuvan yksikön
Keskeiset hyödyt
- Laske SKJ ja PYT valittomasti kahdelle tai useammalle luvulle Euklidisen algoritmin avulla
- Nae kokonais vaiheittainen jakolasku, jotta voit oppia ja tarkistaa algoritmin
- Maarita automaattisesti, ovatko kaksi lukua keskenaan jaottomia (SKJ = 1)
- Yksinkertaista murtolukujaa jakamalla osoittaja ja nimittaja niiden SKJ:lla
- Käsittele suuria lukuja tehokkaasti -- algoritmi toimii jopa kymmenien numeroiden luvuilla
- Tue useamman luvun tilaa: laske SKJ/PYT 3 tai useamman luvun listoille
Ammattilaisen vinkit
- Kayta SKJ-PYT-suhdetta: PYT(a,b) = |a x b| / SKJ(a,b) -- tama on nopeampaa kuin luetella kerrannaisuuksia
- Kaksi lukua ovat keskenaan jaottomia jos ja vain jos SKJ = 1 -- tarkista ennen modulaariaritmetiikkaa
- Murtolukujen yksinkertaistamiseksi jaa aina osoittaja ja nimittaja SKJ(osoittaja, nimittaja):lla
- Aikataulutuksessa muunna kaikki aikajaksot samaan yksikkoön ennen PYT:n laskemista
- Muista, että SKJ(0, n) = n ja PYT(0, n) = 0 -- nolla on jaettavissa kaikella
- Erittain suurilla luvuilla Euklidinen algoritmi on edelleen tehokas -- ei tarvitse päätekijöiden erottelua
Yleisiä vältettäviä virheitä
- Sekoitetaan SKJ ja PYT: SKJ on suurin yhteinen JAKAUR, PYT on pienin yhteinen KERRANNAINAISUUS
- Luullaan, että PYT on ainoa a x b -- tama paatee vain, kun SKJ(a,b) = 1
- Unohdetaan, että SKJ ja PYT laajenevat useammaksi kuin kahdeksi luvuksi: SKJ(a,b,c) = SKJ(SKJ(a,b), c)
- Oletetaan, että Euklidinen algoritmi vaatii päätekijöiden erottelua -- se ei vaadi
- Kaytetaan PYT:ä murtolukujen yksinkertaistamiseen sen sijaan, että kaytettäisiin SKJ:ä
- Ei tarkisteta keskenaan jaottomuutta avaimenluonnin ennen -- e:n on oltava keskenaan jaottoman phi(n):n kanssa
Keskeiset käsitteet selitettynä
- SYY: Suurin kokonaisluku, joka jakaa molemmat luvut ilman jakojaannosta
- PYY: Pienin positiivinen kokonaisluku, joka on jaollinen molemmilla luvuilla
- Yhteenkuuluvuus: Kaksi lukua, joiden SYY = 1, eivät jaksu yhtäkään alkulukua
- Eukleideen algoritmi: Vanha algoritmi SYY:n laskemiseen toistuvalla jakolla
- Modulo-operaatio: a mod b on jakojäkki, kun a jaetaan b:llä
- Jaollisuus: a jakaa b, jos b/a ei tuota jakojaannosta
Liittyvät käsitteet
- Paatekijöiden erottelu: Jaa luvut paaatekijöihin -- perus SKJ ja PYN ymmärtämisen perusta.
- Murtolaskuri: Yksinkertaista, lisää ja vähennä murtolukuja kayttäen SKJ:ä supistamiseen.
- Logaritmilaskuri
- Prosenttilaskuri: Muunna SKJ/PYT-tulokset prosenteiksi suhdeanalyysiin.
- Modulaariaritmetiikka: Kaytta keskenaan jaottomia moduloita RSA-salakirjoituksessa.
Esimerkki
Etsitään SYJ(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. SYJ = 6. PYM = |48×18|/6 = 864/6 = 144. Tarkistus: 144/48 = 3 ✓, 144/18 = 8 ✓.
Tulosten tulkinta
SKJ-tulos kertoo suurimman luvun, joka jakaa molemmat syotteet tasan. Jos SKJ = 1, luvut ovat keskenaan jaottomia. PYT-tulos on pienin luku, johon molemmat syotteet jakautuvat tasan. Suuri SKJ suhteessa syotteihin tarkoittaa, että luvuilla on monia yhteisia tekijöita. SKJ 1 tarkoittaa, että luvut ovat keskenaan jaottomia ja PYT = a x b. Tulo-identiteetti SKJ x PYT = |a x b| mahdollistaa tarkistuksen.