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

Prif: Ffracsiwn

Mae'r dull yma'n hynod o ddefnyddiol i leihau ffracsiynau i'w termau lleiaf. Er enghraifft, gcd(42, 56) = 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, 84), fe welwn y ffactorau cysefin 18 = 2 · 3² a 84 = 2² · 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

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:

$\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

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