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.

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
Yn yr erthygl hon, byddwn yn dynodi'r hannydd cyffredin mwyaf o ddau gyfanrif * a * a '' 'fel chd (' 'a' ',' '' ').

### Enghraifft
Beth yw rhannydd cyffredin mwyaf y rhifau 54 a 24?

Gellir mynegi'r rhif 54 fel lluoswm (*product*) o ddau gyfanrif, mewn sawl ffordd:
:  54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. \, 

Felly, **rhanyddion 54** yw:   1, 2, 3, 6, 9, 18, 27, 54. \, 

A, **rhanyddion 24** yw:   1, 2, 3, 4, 6, 8, 12, 24. \, 

Gelwir y rhifau sy'n gyffredin rhwng y ddwy restr yma yn **rhanyddion cyffredin**, sef 54 a 24:

:  1, 2, 3, 6. \, 

Y mwyaf o'r rhain yw 6. Chwech, felly, yw rhannydd cyffredin mwyaf y rhifau 54 a 24.
Gellir sgwennu hyn fel:

:  \gcd(54,24) = 6. \, 

### Ffracsiynau
Mae'r dull yma'n hynod o ddefnyddiol i leihau ffracsiynau i'w termau lleiaf. Er enghraifft, gcd(42,&nbsp;56)&nbsp;=&nbsp;14, felly,

:\frac{42}{56}=\frac{3 \cdot 14 }{ 4 \cdot 14}=\frac{3 }{ 4}.

### Rhifau cydgysefin
Gelwir 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
Gellir 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,&nbsp;84), fe welwn y ffactorau cysefin 18&nbsp;=&nbsp;2&nbsp;·&nbsp;32 a 84&nbsp;=&nbsp;22&nbsp;·&nbsp;3&nbsp;·&nbsp;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&nbsp;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":

:300px

: Lluoswm lleiaf cyffredin (*Least common multiple*) = 2 × 2 × ( 2 × 2 × 3 ) × 3 × 5 = 720
: Rhannydd cyffredin mwyaf = 2 × 2 × 3 = 12.

## 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:

:\gcd(a,0) = a
:\gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b),
ble mae
: a \,\mathrm{mod}\, b = a - b \left\lfloor {a \over b} \right\rfloor .

Os yw'r ddau ymresymiad yn fwy na sero, yna gellir sgwennu'r algorithm mewn dull symlach, fel:

:\gcd(a,a) = a, 
:\gcd(a,b) = \gcd(a - b,b)\quad,  if *a* > *b*
:\gcd(a,b) = \gcd(a, b-a)\quad, if *b* > *a*

[bawd|Animeiddiad sy'n dangos y dull o gymhwyso [Algorithm Ewclidaidd er mwyn canfod rhannydd cyffredin mwyaf 62 a 36 (sef 2).]]

## Cyfeiriadau
Categori:Damcaniaethau rhif