Efni.

• Skref
• Aðferð 1 af 2: Skilgreiningarreiknirit
• Aðferð 2 af 2: Prime Factors
• Ábendingar

The Greatest Common Divisor (GCD) tveggja heiltala er stærsta heiltalan sem skiptir hverri af þessum tölum. Til dæmis er gcd fyrir 20 og 16 4 (bæði 16 og 20 eru með stóra deila, en þeir eru ekki algengir - til dæmis, 8 er deilir af 16, en ekki deilir af 20). Það er til einföld og kerfisbundin aðferð til að finna GCD, kölluð „reiknirit Euclides“. Þessi grein mun sýna þér hvernig á að finna stærsta sameiginlega skipting tveggja heiltala.

Skref

Aðferð 1 af 2: Skilgreiningarreiknirit

1. 1 Slepptu öllum mínusmerkjum.
2. 2 Lærðu hugtökin: þegar deilt er 32 með 5,
   • 32 - arður
   • 5 - skiptir
   • 6 - einkaaðili
   • 2 - afgangur
3. 3 Ákveðið stærstu tölurnar. Það verður deilanlegt og minni fjöldinn verður deilirinn.
4. 4 Skrifaðu niður eftirfarandi reiknirit: (arður) = (deilir) * (kvóti) + (afgangur)
5. 5 Settu stærri tölu í stað arðgreiðslunnar og minni tölu í stað skiptingarinnar.
6. 6 Finndu hversu oft stærri tala er deilt með minni, og skrifaðu niðurstöðuna í stað kvótans.
7. 7 Finndu afganginn og skrifaðu það í viðeigandi stöðu í reikniritinu.
8. 8 Skrifaðu reikniritið aftur, en (A) skrifaðu fyrri skiptinguna sem nýjan arð, og (B) fyrri afganginn sem nýjan deila.
9. 9 Endurtaktu fyrra skrefið þar til afgangurinn er 0.
10. 10 Síðasti skiptirinn verður stærsti sameiginlegi skiptingin (GCD).
11. 11 Til dæmis, við skulum finna GCD fyrir 108 og 30:
12. 12 Taktu eftir því hvernig tölurnar 30 og 18 frá fyrstu línunni mynda seinni línuna. Þá mynda 18 og 12 þriðju röðina og 12 og 6 mynda fjórðu röðina. Margfeldi af 3, 1, 1 og 2 eru ekki notuð. Þeir tákna fjölda skipta sem arðurinn er deilanlegur með deilunni og eru því einstakir í hverri röð.

Aðferð 2 af 2: Prime Factors

1. 1 Slepptu öllum mínusmerkjum.
2. 2 Finndu frumþætti talna. Kynntu þau eins og sýnt er á myndinni.
   • Til dæmis fyrir 24 og 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Til dæmis fyrir 50 og 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 Finndu sameiginlega frumþætti.
   • Til dæmis fyrir 24 og 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Til dæmis fyrir 50 og 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Margfaldaðu sameiginlega frumþætti.
   • Fyrir 24 og 18, margfalda 2 og 3 og fá 6... 6 er stærsti samnefnari 24 og 18.
   • Það er ekkert að margfalda fyrir 50 og 35. 5 Er eini sameiginlegi frumþátturinn og það er GCD.
5. 5 Gerð!

Ábendingar

• Ein leið til að skrifa þetta er: arður> mod divider> = rest; GCD (a, b) = b ef mod b = 0 og gcd (a, b) = gcd (b, mod b) annars.
• Sem dæmi skulum við finna GCD (-77,91). Notaðu fyrst 77 í stað -77: GCD (-77.91) breytist í GCD (77.91). 77 er minna en 91, þannig að við verðum að skipta þeim, en íhugaðu hvernig reikniritið virkar ef við gerum það ekki. Við útreikning 77 mod 91 fáum við 77 (77 = 91 x 0 + 77). Þar sem þetta er ekki núll lítum við á ástandið (b, mod b), það er GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 er afgangurinn). Það er ekki núll, þannig að GCD (91,77) verður GCD (77,14). 77 mod 14 = 7. Þetta er ekki núll, þannig að GCD (77.14) verður GCD (14.7). 14 mod 7 = 0 (síðan 14/7 = 2 án afgangs). Svar: GCD (-77,91) = 7.
• Aðferðin sem lýst er er mjög gagnleg til að einfalda brot. Í dæminu hér að ofan: -77/91 = -11/13, þar sem 7 er stærsti samnefnari -77 og 91.
• Ef a og b eru jafnt og núll, þá er öll núlllaus númer deilir þeirra, þannig að í þessu tilfelli er enginn GCD (stærðfræðingar telja einfaldlega að stærsti sameiginlegi deilirinn 0 og 0 sé 0).