greatest common divisor

greatest common divisor

1. (informatika) legnagyobb közös osztó

A legnagyobb közös osztó (röviden LNKO angolul: GCD – Greatest Common Divisor) két vagy több egész szám esetén az a legnagyobb pozitív egész szám, amely maradék nélkül osztja mindegyik számot.

Ha adott két egész szám: ${\textstyle a}$ és ${\textstyle b}$, akkor a legnagyobb közös osztójuk ${\textstyle d}$, ha:

$${\displaystyle d\mid a\quad {\text{és}}\quad d\mid b}$$

Példa:

• ${\textstyle {\text{LNKO}}(12,18)=6}$
  • Mert a 6 osztja mind a 12-t, mind a 18-at.

• ${\textstyle {\text{LNKO}}(a,0)=|a|}$

• Szimmetrikus: ${\textstyle {\text{LNKO}}(a,b)={\text{LNKO}}(b,a)}$

• Több számra is alkalmazható: ${\textstyle {\text{LNKO}}(a,b,c)={\text{LNKO}}({\text{LNKO}}(a,b),c)}$

• Összefüggés a legkisebb közös többszörössel:

  $${\displaystyle {\text{LNKO}}(a,b)\cdot {\text{LNKO}}(a,b)=|a\cdot b|}$$

Egy gyors módszer a legnagyobb közös osztó kiszámítására:

function lnko(a, b):
    amíg b ≠ 0:
        a, b = b, a mod b
    visszatérés: a

• ${\textstyle {\text{LNKO}}(48,18)}$
  • ${\textstyle 48\mod 18=12}$
  • ${\textstyle 18\mod 12=6}$
  • ${\textstyle 12\mod 6=0}$
  • → LNKO = 6

1. Bontsd a számokat prímtényezőkre.
2. Vedd a közös prímeket a legkisebb kitevőikkel, és szorozd össze őket.

Példa:

• ${\textstyle 60=2^{2}\cdot 3\cdot 5}$
• ${\textstyle 36=2^{2}\cdot 3^{2}}$
• Közös: ${\textstyle 2^{2}\cdot 3=12}$
• → ${\textstyle {\text{LNKO}}(60,36)=12}$

⚠️ Nagy számokra nem hatékony.

import math
print(math.gcd(48, 18))  # Kimenet: 6

Több szám esetén:

from functools import reduce
from math import gcd

szamok = 
eredmeny = reduce(gcd, szamok)
print(eredmeny)

• Tört egyszerűsítése: ${\textstyle {\frac {60}{36}}={\frac {5}{3}}}$
• Kriptográfia (pl. RSA)
• Moduláris aritmetika
• Lineáris egyenletek megoldása egész számokkal
• Legkisebb közös többszörös (LKKT) számítása

• greatest common divisor - Szótár.net (en-hu)
• greatest common divisor - Sztaki (en-hu)
• greatest common divisor - Merriam–Webster
• greatest common divisor - Cambridge
• greatest common divisor - WordNet
• greatest common divisor - Яндекс (en-ru)
• greatest common divisor - Google (en-hu)
• greatest common divisor - Wikidata
• greatest common divisor - Wikipédia (angol)