老当益壮！新疆军区用八一杠步枪打靶

百度 总之，公平游戏联盟的成立，无论是对玩家还是对游戏业界来说，都是一件好事。

Matematiikassa kahden kokonaisluvun a ja b suurin yhteinen tekij?, merkit??n syt(a, b) tai pelk?st??n (a, b), tarkoittaa suurinta sellaista lukua, joka jakaa molemmat luvut a ja b niin, ett? lopputulos on kokonaisluku. Suurin yhteinen tekij? voidaan etsi? jakamalla tarkasteltavina olevat luvut alkutekij?ihin. T?ll?in lukujen suurin yhteinen tekij? saadaan ottamalla ne alkuluvut, jotka esiintyv?t molempien lukujen alkutekij?hajotelmassa korotettuna siihen potenssiin, joka on pienempi t?m?n kyseisen alkuluvun eksponentti lukujen alkutekij?hajotelmissa. Suurin yhteinen tekij? on t?ll?in saatujen lukujen tulo. Siis jos

$a=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdot \cdot \cdot p_{n}^{a_{n}}$ ja

$b=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdot \cdot \cdot p_{n}^{b_{n}}$,

jossa $p_{i}$ on i:s alkuluku, ja jos $p_{i}$ ei ole luvun tekij?, sit? vastaava eksponentti $a_{i}$ tai $b_{i}$ on nolla, saadaan suurin yhteinen tekij? kaavasta

$\mathrm {syt} (a,b)=p_{1}^{min(a_{1},b_{1})}p_{2}^{min(a_{2},b_{2})}\cdot \cdot \cdot p_{n}^{min(a_{n},b_{n})}$

Suurin yhteinen tekij? voidaan l?yt?? my?s esimerkiksi Eukleideen algoritmin avulla.

Algebrallinen m??ritelm?

Algebrallisessa mieless? kokonaislukujen $a_{1},a_{2},...,a_{n}$ suurimmalla yhteisell? tekij?ll? tarkoitetaan n?iden lukujen viritt?m?n kokonaislukujen renkaan ideaalin viritt?j??.

Jos luvut $a_{1},a_{2},...,a_{n}$ ovat kaikki nollia, niiden viritt?m? ideaali koostuu pelk?st??n luvusta $0$.

Kokonaislukujen rengas $\mathbb {Z}$ on kommutatiivinen eli vaihdannainen rengas. Lis?ksi se on kokonaisalue, toisin sanoen siin? ei ole nollasta eroavia nollanjakajia, ja edelleen niin sanottu p??ideaalialue, toisin sanoen sen jokainen ideaali on yhden alkion viritt?m?.

V?ite, ett? jokainen kokonaislukujen renkaan $\mathbb {Z}$ ??rellisesti viritetty ideaali on yhden alkion viritt?m?, voidaan todistaa seuraavasti:

Olkoon $I=\lbrace c_{1}a_{1}+c_{2}a_{2}+...+c_{n}a_{n}\vert c_{i}\in Z$ kaikilla $i=1,...,n\rbrace$ kokonaislukujen $a_{1},a_{2},...,a_{n}$ viritt?m? renkaan $\mathbb {Z}$ ideaali. Olkoon $d$ t?m?n ideaalin pienin positiivinen alkio ja $d=d_{1}a_{1}+d_{2}a_{2}+...+d_{n}a_{n}$.

Helposti todetaan, ett? jokainen $d$:n monikerta sis?ltyy ideaaliin $I$.

Olkoon toisaalta $c=c_{1}a_{1}+c_{2}a_{2}+...+c_{n}a_{n}$ ideaalin $I$ mielivaltainen alkio ja $c=ed+f$, jossa $0\leq f\leq d$.

T?ll?in $f=c-ed=(c_{1}a_{1}+c_{2}a_{2}+...+c_{n}a_{n})-e(d_{1}a_{1}+d_{2}a_{2}+...+d_{n}a_{n})=(c_{1}-ed_{1})a_{1}+(c_{2}-ed_{2})a_{2}+...+(c_{n}-ed_{n})a_{n}$.

Siis $f$ kuuluu ideaaliin $I$. Jos $f$ on suurempi kuin nolla, saadaan ristiriita luvun $d$ valinnan kanssa. Siis v?ltt?m?tt? jokainen ideaalin $I$ alkio on luvun $d$ monikerta.

Toisin sanoen lukujen $a_{1},a_{2},...a_{n}$ viritt?m? ideaali on sama, kuin ko. ideaalin pienimm?n positiivisen alkion $d$ viritt?m? ideaali. T?t? lukua $d$ kutsutaan lukujen $a_{1},a_{2},...,a_{n}$ suurimmaksi yhteiseksi tekij?ksi.

Esimerkkej?

• Lukujen 12 ja 15 suurin yhteinen tekij? on 3. T?m? n?hd??n jakamalla luvut tekij?ihin: 12 = 2² · 3 ja 15 = 3 · 5.
• Lukujen 132 ja 222 suurin yhteinen tekij? syt(132,222) = 6, koska 132 = 2² · 3 · 11 ja 222 = 2 · 3 · 37.

Yksinkertainen k?yt?nn?n esimerkki

Olkoon teht?v?n? peitt?? suorakaiteen muotoisen huoneen, jonka leveys a ja pituus b ovat kokonaislukuja, lattia mahdollisimman suurilla kesken??n samankokoisilla neli?n muotoisilla laatoilla. Miten laatan sivun pituus c on valittava?

Ratkaisun antaa lukujen a ja b suurin yhteinen tekij? suoraan. Siis valitaan c=syt(a,b).

Ominaisuuksia

• Jos syt(a, b) = 1, a ja b ovat kesken??n jaottomia.
• syt(a, b) = syt(b, a) = syt(|a|, |b|)
• syt(a, a) = a
• syt(0, a) = a
• syt(m·a, m·b) = m·syt(a, b)
• syt(a, b) = syt(a - kb, b), jossa k on kokonaisluku
• Eukleideen algoritmi: syt(a, b) = syt(b, a modulo b)

K?yt?nn?ss? nopein tapa m??ritt?? kahden luvun suurin yhteinen tekij? on k?ytt?? Josef Steinin vuonna 1961 julkaisemaa bin??rist? algoritmia, mik?li lukujen alkutekij?hajotelmaa ei tunneta.

Ohjelmallinen toteutus

Suurin yhteinen tekij? kahdelle ep?negatiiviselle kokonaisluvulle on laskettavissa Pythonilla rekursiolla seuraavalla funktiolla:

def syt(a, b):
  if b == 0:
    return a
  else:
    return syt(b, (a % b))

Katso my?s

• Pienin yhteinen jaettava
• Aito jakaja
• Yhteinen tekij?

L?hteet

• Rosen, Kenneth H.: Elementary Number Theory and Its Applications. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4 (englanniksi)

Aiheesta muualla

• Kuvia tai muita tiedostoja aiheesta Suurin yhteinen tekij? Wikimedia Commonsissa