Rhannydd cyffredin mwyaf
Mewn mathemateg, y rhannydd cyffredin mwyaf (greatest common divisor; GCD) o ddau gyfanrif neu fwy, sydd ddim yn sero, yw'r cyfanrif positif mwyaf a all rannu pob cyfanrif. Mewn geiriau eraill, y GCD o set o rifau yw'r cyfanrif positif mwyaf sy'n rhannu'r holl rifau yn y set heb adael gweddill. Dyma'r lluosrif mwyaf o'r holl rifau yn y set.[1][2]
Er enghraifft, GCD 8 a 12 ydy 4.
Caiff weithiau ei alw'n ffactor cyffredin mwyaf neu 'ffactor cyffredin uchaf'. Gellir ymestyn y cysyniad hwn i polynomialau, ac fe'i gelwir yn 'Polynomial y rhannydd cyffredin mwyaf'.
Trosolwg
golyguYn yr erthygl hon, byddwn yn dynodi'r hannydd cyffredin mwyaf o ddau gyfanrif a a 'fel chd (' 'a' ',' ').
Enghraifft
golyguBeth yw rhannydd cyffredin mwyaf y rhifau 54 a 24?
Gellir mynegi'r rhif 54 fel lluoswm (product) o ddau gyfanrif, mewn sawl ffordd:
Felly, rhanyddion 54 yw:
A, rhanyddion 24 yw:
Gelwir y rhifau sy'n gyffredin rhwng y ddwy restr yma yn rhanyddion cyffredin, sef 54 a 24:
Y mwyaf o'r rhain yw 6. Chwech, felly, yw rhannydd cyffredin mwyaf y rhifau 54 a 24. Gellir sgwennu hyn fel:
Ffracsiynau
golygu- Prif: Ffracsiwn
Mae'r dull yma'n hynod o ddefnyddiol i leihau ffracsiynau i'w termau lleiaf. Er enghraifft, gcd(42, 56) = 14, felly,
Rhifau cydgysefin
golyguGelwir dau rif yn 'gydgysefin', neu yn 'gysefin cymharol' (coprime), os yw eu rhannydd cyffredin mwyaf yn hafal i 1. Er enghraifft, mae 9 a 28 yn gydgysefin.
Cyfrifo
golyguGellir cyfrifo'r rhannydd cyffredin mwyaf trwy bennu ffactorau cysefin y ddau rif a chymharu'r ffactorau, fel yn yr enghraifft ganlynol: i gyfrifo gcd(18, 84), fe welwn y ffactorau cysefin 18 = 2 · 32 a 84 = 22 · 3 · 7 a sylwn fod gorgyffwrdd yma rhwng y ddau ymadrodd yw 2 · 3; felly gcd(18, 84) = 6.
O ddydd i ddydd, cyfyngir y defnydd o'r dull hwn i rifau bach yn unig. Mae cyfrifo ffactorau cysefin, fel arfer, yn cymryd llawer hirach!
Dyma enghraifft arall, a ddangosir gan ddiagram Venn. Yma, ceisir canfod rhannydd cyffredin mwyaf 48 a 180. Yn gyntaf, dylid darganfod ffactorau cysefin y ddau rif:
- 48 = 2 × 2 × 2 × 2 × 3,
- 180 = 2 × 2 × 3 × 3 × 5.
Mae yma dir canol (y rhan sy'n gorgyffwrdd), sef dau "2" a "3":
- Lluoswm lleiaf cyffredin (Least common multiple) = 2 × 2 × ( 2 × 2 × 3 ) × 3 × 5 = 720
- Rhannydd cyffredin mwyaf = 2 × 2 × 3 = 12.
Algorithm Ewclidaidd
golygu- Prif: Algorithm Ewclidaidd
Dull llawer mwy effeithlon yw'r Algorithm Ewclidaidd, sy'n defnyddio algorithm rhannu (e.e. rhannu hir) ar y cyd â'r ffaith bod y GCD o'r ddau rif hefyd yn rhannu eu gwahaniaeth. I gyfrifo CGD (48,18), rhannwch 48 gydag 18 i gael y cyniferydd 2 a gweddill o 12.
Yna rhannwch 18 gyda 12 i gael y cyniferydd 1 a gweddill o 6. Yna rhannwch 12 gyda 6 i gael gweddill 0, sy'n golygu mai 6 yw'r GCD. Sylwch ein bod yn anwybyddu'r cynhwysydd ym mhob cam ac eithrio i sylwi pan gyrhaeddodd y gweddill 0, gan nodi ein bod wedi cyrraedd yr ateb. Yn ffurfiol, gellir disgrifio'r algorithm fel:
Yn ffurfiol, gellir disgrifio'r algorithm fel:
- ,
ble mae
- .
Os yw'r ddau ymresymiad yn fwy na sero, yna gellir sgwennu'r algorithm mewn dull symlach, fel:
- ,
- if a > b
- if b > a