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:


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

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

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, 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":

300pxGustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", Wolfram Demonstrations Project, Cyhoeddwyd: 1 Chwefror 2013. 

 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:

,
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

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