Saturs

• Soļi
• 1. metode no 2: dalītāja algoritms
• 2. metode no 2: primārie faktori
• Padomi

Divu veselu skaitļu lielākais kopīgais dalītājs (GCD) ir lielākais vesels skaitlis, kas dala katru no šiem skaitļiem. Piemēram, gcd 20 un 16 ir 4 (gan 16, gan 20 ir lieli dalītāji, bet tie nav izplatīti - piemēram, 8 ir 16 dalītājs, bet ne 20 dalītājs). Ir vienkārša un sistemātiska metode GCD atrašanai, ko sauc par "Eiklida algoritmu". Šis raksts parādīs, kā atrast lielāko kopējo dalītāju no diviem veseliem skaitļiem.

Soļi

1. metode no 2: dalītāja algoritms

1. 1 Izlaidiet mīnus zīmes.
2. 2 Uzziniet terminoloģiju: dalot 32 ar 5,
   • 32 - dividendes
   • 5 - dalītājs
   • 6 - privāts
   • 2 - atlikums
3. 3 Nosakiet lielāko no skaitļiem. Tas būs dalāms, un mazākais skaitlis būs dalītājs.
4. 4 Pierakstiet šādu algoritmu: (dividendes) = (dalītājs) * (koeficients) + (atlikums)
5. 5 Dividenžu vietā ievietojiet lielāku skaitli, bet dalītāja vietā - mazāku.
6. 6 Atrodiet, cik reizes lielāks skaitlis ir dalīts ar mazāko, un koeficienta vietā ierakstiet rezultātu.
7. 7 Atrodiet atlikumu un ierakstiet to atbilstošajā algoritma vietā.
8. 8 Uzrakstiet algoritmu vēlreiz, bet (A) ierakstiet iepriekšējo dalītāju kā jaunu dividendi un (B) iepriekšējo atlikumu kā jaunu dalītāju.
9. 9 Atkārtojiet iepriekšējo darbību, līdz atlikušais ir 0.
10. 10 Pēdējais dalītājs būs lielākais kopējais dalītājs (GCD).
11. 11 Piemēram, atradīsim GCD 108 un 30:
12. 12 Ievērojiet, kā skaitļi 30 un 18 no pirmās rindas veido otro rindu. Tad 18 un 12 veido trešo rindu, un 12 un 6 veido ceturto rindu. 3, 1, 1 un 2 daudzkārtņus neizmanto. Tie atspoguļo reižu skaitu, kad dividenžu dalītājs dalās ar dalītāju, un tāpēc tie ir unikāli katrai rindai.

2. metode no 2: primārie faktori

1. 1 Izlaidiet mīnus zīmes.
2. 2 Atrodiet skaitļu galvenos faktorus. Pasniedziet tos, kā parādīts attēlā.
   • Piemēram, 24 un 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Piemēram, 50 un 35:
     • 50- 2 x 5 x 5
     • 35-5x7
3. 3 Atrodiet galvenos faktorus.
   • Piemēram, 24 un 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Piemēram, 50 un 35:
     • 50 - 2 reizes 5 x 5
     • 35- 5 x 7
4. 4 Reiziniet kopējos galvenos faktorus.
   • 24 un 18 reiziniet 2 un 3 un saņemties 6... 6 ir lielākais kopsaucējs no 24 un 18.
   • Par 50 un 35 nav ko pavairot. 5 Tas ir vienīgais galvenais faktors, un tas ir GCD.
5. 5 Izgatavots!

Padomi

• Viens veids, kā to uzrakstīt, ir: dividendes> mod dalītājs> = atlikums; GCD (a, b) = b, ja mod b = 0, un gcd (a, b) = gcd (b, a mod b) citādi.
• Piemēram, atradīsim GCD (-77,91). Pirmkārt, izmantojiet 77, nevis -77: GCD (-77,91) pārvērš par GCD (77,91). 77 ir mazāks par 91, tāpēc mums tie ir jāmaina, bet apsveriet, kā algoritms darbojas, ja mēs to nedarām. Aprēķinot 77 mod 91, mēs iegūstam 77 (77 = 91 x 0 + 77). Tā kā tas nav nulle, mēs uzskatām situāciju (b, a mod b), tas ir, GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 ir atlikums). Tā nav nulle, tāpēc GCD (91,77) kļūst par GCD (77,14). 77 mod 14 = 7. Šī nav nulle, tāpēc GCD (77.14) kļūst par GCD (14.7). 14 mod 7 = 0 (kopš 14/7 = 2 bez atlikuma). Atbilde: GCD (-77,91) = 7.
• Aprakstītā metode ir ļoti noderīga frakciju vienkāršošanai. Iepriekš minētajā piemērā: -77/91 = -11/13, jo 7 ir lielākais kopsaucējs -77 un 91.
• Ja a un b ir vienādi ar nulli, tad jebkurš skaitlis, kas nav nulle, ir to dalītājs, tāpēc šajā gadījumā nav GCD (matemātiķi vienkārši uzskata, ka lielākais kopējais dalītājs no 0 un 0 ir 0).