Palaa takaisin

Eukleideen algoritmi

Tehtävät on jaoteltu värin mukaan helppoihin, perus ja vaikeisiin tehtäviin.

Helppo
Perus
Vaikea

Tehtävä 1.1. Kirjoita jakoyhtälö seuraaville jakolaskuille.

a. 216\frac {21}{6}

b.12823\frac{128}{23}

c. 4810\frac{48}{10}

Jakoyhtälö on muotoa a=b∗q+ra=b*q+r eli jaettava=jakaja⋅osama¨a¨ra¨+jakoja¨a¨nno¨sjaettava = jakaja \cdot osamäärä + jakojäännös

a. 21=6⋅3+321 = 6 \cdot 3+3
b. 128=23⋅5+13128=23\cdot5+13
c. 48=10⋅4+848=10\cdot 4+8

Tehtävä 1.2. Mitkä ovat kohdan 1.1. jakoyhtälöiden kokonaisosat ja jakojäännökset?

a. kokonaisosa q=3 ja jakojäännös r=3
b. kokonaisosa q=5 ja jakojäännös r=13
c. kokonaisosa q=4 ja jakojäännös r=8

Tehtävä 2. Selvitä suurin yhteinen tekijä ilman laskutoimituksia, tarkastelemalla annettuja välivaihteita.

a. syt(99, 63)

välivaiheet

99=63⋅1+3699=63\cdot1+36
63=36⋅1+2763=36\cdot1+27
36=27⋅1+936=27\cdot1+9
27=9⋅3+027=9\cdot3+0

b. syt(187, 121)

välivaiheet

a187=121⋅1+66187=121\cdot1+66
121=66⋅1+55121=66\cdot1+55

55=11⋅5+055=11\cdot 5+0

c. syt(143,104)

välivaiheet

143=104⋅1+39143=104\cdot1+39
104=39⋅2+26104=39\cdot2+26
39=26⋅1+x39=26\cdot1+x
26=x⋅2+026=x\cdot2+0

a. Suurin yhteinen tekijä on 9

b. Suurin yhteinen tekijä on 11

c. Suurin yhteinen tekijä on 13

Tehtävä 3. Laske suurin yhteinen tekijä Eukleideen algoritmin avulla.

  1. syt(32, 18)
  2. syt(244, 56)
  3. syt(721, 679)

a. syt(32, 18)
32=18⋅1+1432=18\cdot1+14
18=14⋅1+418=14\cdot1+4
14=4⋅3+214=4\cdot3+2
4=2⋅2+04=2\cdot 2+0

vastaus: Suurin yhteinen tekijä on 2

b. syt(244,56)
244=56⋅4+20244=56\cdot 4+20
56=20⋅2+1656=20\cdot2+16
20=16⋅1+420=16\cdot1+4
16=4⋅4+016=4\cdot4+0

vastaus: Suurin yhteinen tekijä on 4

c. syt(721, 679)
721=679⋅1+42721=679\cdot 1+42
679=42⋅16+7679=42\cdot16+7
42=7⋅6+042=7\cdot6+0

vastaus: Suurin yhteinen tekijä on 7

Tehtävä 4. Selvitä suurin yhteinen tekijä alkuluku hajotelmien avulla. Kirjoita näkyviin luvun alkutekijät ja suurin yhteinen tekijä.

  1. syt(32, 18)
  2. syt(721, 679)
  3. syt(336, 99)

a.
32=16⋅2=2⋅2⋅8=2⋅2⋅2⋅4=2⋅2⋅2⋅2⋅2=2532=16\cdot2=2\cdot2\cdot8=2\cdot2\cdot2\cdot4=2\cdot2\cdot2\cdot2\cdot2=2^5
18=9⋅2=3⋅3⋅2=2⋅3218=9\cdot2=3\cdot3\cdot2=2\cdot3^2
Suurin yhteinen tekijä on 2

b.
721=7⋅103721=7\cdot103
679=7⋅97679=7\cdot 97
Suurin yhteinen tekijä on 7

c.
336=2⋅112=3⋅2⋅56=3⋅2⋅2⋅28=3⋅2⋅2⋅2⋅14=3⋅2⋅2⋅2⋅2⋅7=24⋅3⋅7336=2\cdot112=3\cdot2\cdot56=3\cdot2\cdot2\cdot28=3\cdot2\cdot2\cdot2\cdot14=3\cdot2\cdot2\cdot2\cdot2\cdot7=2^4\cdot3\cdot7
99=3⋅33=3⋅3⋅11=32⋅1199=3\cdot33=3\cdot3\cdot11=3^2\cdot11
Suurin yhteinen tekijä on 3

Tehtävä 5. Selvitä pitävätkö seuraavat laskut paikkansa, perustele vastaus Eukleideen algoritmin avulla.

  1. syt(40, 24) = 4
  2. syt(21, 14) =7
  3. syt(391, 299)=23

a. syt(40,24)
40=24⋅1+1640=24\cdot1+16
24=16⋅1+824=16\cdot1+8
16=8⋅2+016=8\cdot 2+0

vastaus: syt(40,24)≠4syt(40{,}24)\ne4 eli vastaus ei ole totta, koska syt(40,24)=8syt(40{,}24)=8 eli lukujen suurin yhteinen tekijä on 8.

b. syt(21,14)=7
21=14⋅1+721=14\cdot1+7
14=7⋅2+014=7\cdot2+0

vastaus: syt(21, 14) =7 on totta, koska lukujen suurin yhteinen tekijä on 7

c. syt(391, 299)=23
391=299⋅1+92391=299\cdot1+92
299=92⋅3+23299=92\cdot3+23
92=23⋅4+092=23\cdot4+0

vastaus: syt(391, 299)=23 on totta, koska lukujen suurin yhteinen tekijä on 23

Tehtävä 6. Ratkaise suurin yhteinen tekijä Eukleideen algoritmin avulla, kun lauseke on muotoa syt(syt(a, b), c).

  1. syt(syt(102, 170), 85)
  2. syt(syt(1144, 650), 422)

a. syt(syt(102, 170), 85)
syt(102,170)syt\left(102{,}170\right)
170=102⋅1+68170=102\cdot 1+68
102=68⋅1+34102=68\cdot1+34
68=34⋅2+068=34\cdot2+0

syt(34,85)syt\left(34{,}85\right)
85=34⋅2+1785=34\cdot 2+17
34=17⋅2+034=17\cdot2+0

vastaus: Suurin yhteinen tekijä on 17

b. syt(syt(1144, 650), 422)
syt(1144,650)syt(1144,650)
1144=650⋅1+4941144=650\cdot1+494
650=494⋅1+156650=494\cdot1+156
494=156⋅3+26494=156\cdot3+26
156=26⋅6+0156=26\cdot 6+0

syt(26, 442)syt\left(26{,}\ 442\right)
422=26⋅16+6422=26\cdot16+6
26=6⋅4+226=6\cdot4+2
6=2⋅3+06=2\cdot 3+0

vastaus: Suurin yhteinen tekijä on 2

Tehtävä 7. Ratkaise x ja y Eukleideen algoritmin avulla.

Tee Eukleideen algoritmi → löydä syt.

Kirjoita joka rivi jakojäännösyhtälönä.

Aloita yhtälöstä, jossa vasemmalla on syt.

Korvaa esiintyvät jakojäännökset niiden omilla yhtälöillä.

Jaa sulut, yhdistä termit.

Jatka kunnes kaikki on muodossa ax+byax + by.

Lue x ja y.

33x+57y=3 
syt(33,57)syt(33, 57)
57=33⋅1+2457=33\cdot1+24
33=24⋅1+933=24\cdot1+9
24=9⋅2+624=9\cdot2+6
9=6⋅1+39=6\cdot1+3
6=3⋅2+06=3\cdot2+0
syt(33,57)=3syt(33,57)=3

jakojäännös yhtälöt:
24=57−33⋅124=57-33\cdot1
9=33−24⋅19=33-24\cdot1
6=24−9⋅26=24-9\cdot2
3=9−6⋅13=9-6\cdot1

Sijoitetaan yhtälöön jakojäännösyhtälöiden arvot alhaalta ylöspäin:
3=9−6⋅13=9-6\cdot1
korvataan 6:
3=9−(24−9⋅2)3=9-(24-9\cdot2)
3=9−24+9⋅23=9-24+9\cdot2
3=3⋅9−243=3\cdot9-24
korvataan 9:
3=3⋅(33−24)−243=3\cdot(33-24)-24
3=3⋅33+3⋅(−24)−243=3\cdot33+3\cdot(-24)-24
3=3⋅33−4⋅243=3\cdot33-4\cdot24
korvataan 24:
3=3⋅33−4⋅(57−33)3=3\cdot33-4\cdot(57-33)
3=3⋅33−4⋅57−4⋅(−33)3=3\cdot33-4\cdot57-4\cdot(-33)
3=3⋅33−4⋅57+4⋅333=3\cdot33-4\cdot57+4\cdot33
3=7⋅33−4⋅573=7\cdot33-4\cdot57

vastaus: x=7 ja y=-4

Tehtävä 8. Ratkaise ohjelmallisesti Eukleideen algoritmi niin, että koodi tulostaa näkyviin jakoyhtälön kaikki välivaiheet sekä suurimman yhteisen tekijän.

Koodi:

def toteuttaa_jakoyhtalo(a, b):

    r = a % b

    jakojaannokset = []

    while r != 0:

        q = a // b

        r = a % b

        print(f”{a} = {b} * {q} + {r}”)

        a = b

        b = r

        jakojaannokset.append(r)

    return f”Suurin yhteinen tekijä on {jakojaannokset[len(jakojaannokset)-2]} eli toiseksi viimeinen jakoyhtälön jakojäännös.”

print(toteuttaa_jakoyhtalo(1819, 867))

Tuloste:

1819 = 867 * 2 + 85
867 = 85 * 10 + 17
85 = 17 * 5 + 0
Suurin yhteinen tekijä on 17 eli toiseksi viimeinen jakoyhtälön jakojäännös.