Lukuteoria: Eukleideen algoritmi
Kysymys 1 / 1
Ratkaise tehtävä.
Ratkaise Eukleideen algoritmilla syt(59619,5117).
Eukleideen algoritmi
Ratkaise Eukleideen algoritmilla syt(59619,5117).
Eukleideen algoritmi
Question Popup:
Eukleideen algoritmi on menetelmä löytää kahden positiivisen kokonaisluvun a ja b suurin yhteinen tekijä. Algoritmi toimii niin, että luku a jaetaan luvulla b. Jos jako ei mene tasan, jaetaan luku b jakojäännöksellä. Jos tämäkään ei mene tasan, jaetaan alkuperäinen jakojäännös uudella jakojäännöksellä jne. Tätä jatketaan kunnes jako menee tasan ja löydetään suurin yhteinen tekijä. Ratkaistaan esimerkiksi syt(902,374) Eukleideen algoritmilla.
Lukujen 902 ja 374 suurin yhteinen tekijä on 22.
Lukujen 902 ja 374 suurin yhteinen tekijä on 22.
Solution Popup:
Lukujen 59619 ja 5117 suurin yhteinen tekijä on siis 119.