Bézout' lemma

Bézout' lemma on väide, et täisarvude suurima ühisteguri saab esitada nende arvude täisarvuliste kordajatega lineaarkombinatsioonina.^[1]

See on nimetatud Étienne Bézout' auks.

Täisarvude a ja b suurim ühistegur d on ka vähim positiivne täisarv, mida saab esitada kujul ax + by, kus x ja y on täisarvud.

Formuleeringud

Olgu

a

,

b

täisarv, millest vähemalt üks ei ole null. Siis leiduvad täisarvud

x, y

nii, et kehtib seos

SÜT

(a, b) = x \cdot a + y \cdot b .

Seda väidet nimetatakse Bézout' lemmaks või Bézout' samasuseks^[2]. Täisarve $x, y$ nimetatakse Bézout' kordajateks.

Kui $a$ ja $b$ on ühisteguriteta (see on erijuht, kus SÜT $(a, b) = 1$ ), siis leiduvad $s, t \in ℤ$ nii, et

1 = s \cdot a + t \cdot b .

Peale selle kehtib ka pöördväide: kui leiduvad $s, t \in ℤ$ nii, et $s a + t b = 1$ , siis SÜT $(a, b) = 1$ .^[3]

Kordajaid $s$ ja $t$ saab laiendatud Eukleidese algoritmi abil efektiivselt arvutada.

Küsimusega, milliseid arve saab esitada isegi naturaalarvuliste kordajatega, tegeleb mündiprobleem.

On ka Bézout' lemma variant, mis piirdub naturaalarvudega^[4]:

Olgu

a

,

b

naturaalarvud. Siis leiduvad naturaalarvud

x, y

nii, et kehtib seos

SÜT

(a, b) = x \cdot a - y \cdot b .

Kui kasutada ringi ideaali mõistet, siis peaideaalid $a R$ ja $b R$ sisalduvad peaideaalis SÜT $(a, b) R .$ Järelikult sisaldub ka ideaal $a R + b R$ ideaalis SÜT $(a, b) R .$ Bézout' lemma võib formuleerida ka nii, et täisarvude ringis $R = ℤ$ (või üldse Eukleidese ringides) kehtib

a R + b R = c R

, kui

c =

SÜT

(a, b) .

Näited

SÜT(12,30)=6. Kehtib
$6 = 3 \cdot 12 + (- 1) \cdot 30$
- Suurimat ühistegurit saab liidetavateks lahutada ka teisiti, näiteks: $6 = (- 2) \cdot 12 + 1 \cdot 30 .$
Arvude 12 ja 42 suurim üh9istegur on 6, ja selle saab esitada kujul

(−3)⋅12 + 1⋅42 = 6 ning ka 1 kujul 4⋅12 + (−1)⋅42 = 6.

Tõestus

Tõestus jäägiga jagamise kaudu

Lemma tõestus põhineb jäägiga jagamisel. Seetõttu on seda kerge üle kanda Eukleidese ringidele.

Juhul, kui $a = 0,$ võib võtta $s = 0$ ja $t = \pm 1$ , järelikult võib üldisust kitsendamata eeldada, et $a \neq 0 .$ . Kõikide arvude $x = s \cdot a + t \cdot b$ seas, kus $s, t \in ℤ,$ on kindlasti ka positiivseid arve. Olgu $d = s \cdot a + t \cdot b$ vähim nende seas (see samm kasutab positiivsete täisarvude hulga täielikku järjestatust). Et SÜT $(a, b)$ jagab nii arvu $a$ kui ka arvu $b$ , jagab SÜT $(a, b)$ ka arvu $d$ .

Näitame nüüd, et $d$ on ka arvude $a$ ja $b$ jagaja. Jäägiga jagamine annab arvu $a$ esituse kujul $q \cdot d + r$ , kus $0 \leq r < d$ . Asendades $d$ esitusega $s \cdot a + t \cdot b$ ning avaldades võrrandist $r,$ saame $r = (1 - q \cdot s) \cdot a + (- q \cdot t) \cdot b$ . Et $d$ on minimaalne, siis $r = 0$ , järelikult $d$ on arvu $a$ jagaja. Samamoodi on $d$ arvu $b$ jagaja, nii et $d \leq$ SÜT $(a, b)$ . Nägime juba, et SÜT $(a, b)$ on arvu $d$ jagaja. Järelikult $d =$ SÜT $(a, b)$ .

Tõestus kongruentside kaudu

Olgu d arvude a a b suurim ühistegur, p = a / d ja q = b / d, siis p ja q on ühisteguriteta arvud. Vaaatleme nüüd arve p, 2p, …, (q−1)p. Ükski neist arvudest ei ole kongruentne nulliga modulo q ning (p, 2p, …, (q−1)p) modulo q on arvude (1, 2, …, q − 1) permutatsioon. Sellepärast peab leiduma arv α, 1 ≤ α ≤ q − 1 nii, et αp (mod q) ≡ 1 (mod q). Järelikult leidub ka arv β nii, et αp + βq = 1. Po Korrutades võrduse mõlemad pooled arvuga d, saame Bézout' samasuse αa+ βb = d.

Bézout' kordajad

Et juhtum, kus vähemalt üks arvudest $a, b$ võrdub nulliga, on triviaalne, siis on selles jaotises edaspidi eeldatud, et kumbki neist arvudest ei võrdu nulliga.

Mitteühesus

Bézout' kordajate leidmine on ekvivalentne kahe tundmatuga esimest järku diofantilise võrrandi

a x + b y = d,

kus

d =

SÜT

(a, b),

lahendamisega.

Selle võrrandi samaväärne kuju on:

\frac{a}{d} x + \frac{b}{d} y = 1 .

Siit järeldub, et Bézout' kordajad $x, y$ on määratud mitteüheselt — kui mingid nende väärtused $x_{0}, y_{0}$ on teada, siis kogu kordajate hulga annab valem^[5]

{(x_{0} + \frac{k b}{d}, y_{0} - \frac{k a}{d}) ∣ k = 0, \pm 1, \pm 2, \pm 3 \dots} .

Allpool on näidatud, et leiduvad Bézout' kordajad, mis rahuldavad võrratusi $| x | < | \frac{b}{d} |$ ja $| y | < | \frac{a}{d} |$ .

Kordajate arvutamine Eukleidese algoritmi abil

Bézout' kordajate leidmiseks saab kasutada Eukleidese laiendatud algoritmi SÜT-i leidmiseks ning esitada jäägid arvude a ja b lineaarkombinatsioonidena^[6]. Algoritmi sammudel on järgmine kuju:

r_{1} = a - b q_{0},

r_{2} = b - r_{1} q_{1} = b - (a - b q_{0}) q_{1} = b (1 + q_{0} q_{1}) - a q_{1},

r_{3} = r_{1} - r_{2} q_{2} = (a - b q_{0}) - (b (1 + q_{0} q_{1}) - a q_{1}) q_{2} = a (1 + q_{1} q_{2}) - b (q_{0} + q_{2} + q_{0} q_{1} q_{2}),

…

r_{n} = r_{n - 2} - r_{n - 1} q_{n - 1} = \dots = a x + b y .

Näide

Leiame Bézout' samasuse $a = 991, b = 981$ korral. Eukleidese algoritmi valemitel on kuju

991 = 981 \cdot 1 + 10,

981 = 10 \cdot 98 + 1,

10 = 1 \cdot 10 .

Seega SÜT $(991, 981) = 1 .$ Nendest valemitest saame:

10 = 991 - 1 \cdot 981,

1 = 981 - 10 \cdot 98 = 981 - 98 \cdot (991 - 981) = 99 \cdot 981 - 98 \cdot 991 .

Bézout' samasusel on seega kuju

1 = 99 \cdot 981 - 98 \cdot 991 .

Kordajate arvutamine ahelmurdude abil

Võrrandi $a x + b y = d$ arvutamise alternatiivne (ekvivalentne) viis kasutab ahelmurde. Jagame võrrandi mõlemad pooled SÜT-iga: $a_{1} x + b_{1} y = 1$ . Edasi arendame murru $\frac{| a_{1} |}{| b_{1} |}$ ahelmurruks ja arvutame lähismurrud $\frac{p_{k}}{q_{k}}$ . Neist viimane ( $n$ -is) võrdub $\frac{| a_{1} |}{| b_{1} |}$ ning on eelmisega seotud tavalise seosega:

p_{n} q_{n - 1} - q_{n} p_{n - 1} = (- 1)^{n - 1} .

Asetame sellesse valemisse $p_{n} = a_{1}; q_{n} = b_{1}$ ja korrutame mõlemad pooled arvuga $d$ , saame

a q_{n - 1} - b p_{n - 1} = \pm d .

Märgi täpsusega on see Bézout' samasus, sellepärast annab eelviimane lähismurd $\frac{p_{n - 1}}{q_{n - 1}}$ lahendi absoluutväärtused: $| x |$ on selle murru nimetaja ning $| y |$ on selle lugeja. Jääb üle leida arvude $x, y$ märk, lähtudes algsest võrrandist; selleks piisab, kui leida viimased numbrid korrutistes $| a x |, | b y |$ ^[7].

Minimaalsed kordajate paarid

Eelmises jaotises toodud algoritm ahelmurdude kaudu, nagu ka sellega ekvivalentne Eukleidese algoritm, annab tulemuseks paari $(x, y)$ , mis rahuldab võrratusi

| x | < | \frac{b}{d} |; | y | < | \frac{a}{d} | .

See järeldub sellest, et nagu ülalpool näidatud, moodustavad murrud $\frac{| y |}{| x |}$ ja $\frac{| a_{1} |}{| b_{1} |}$ järjestikused lähismurrud ning järgmise murru lugeja ja nimetaja on alati suuremad kui eelmise omad^[7]^[8]. Lühiduse mõttes võib niisugust paari nimetada minimaalseks, selliseid paare on alati kaks.

Näide. Olgu $a = 12, b = 42 .$ SÜT(12, 42) = 6. Järgnevas ära toodud mõned Bézout' kordajate paaride nimekirja elemendid, kusjuures minimaalsed paarid on välja toodud punasega:

\begin{matrix} \dots \\ 12 \times & - 10 & + 42 \times & 3 & = 6 \\ 12 \times & - 3 & + 42 \times & 1 & = 6 \\ 12 \times & 4 & + 42 \times & - 1 & = 6 \\ 12 \times & 11 & + 42 \times & - 3 & = 6 \\ 12 \times & 18 & + 42 \times & - 5 & = 6 \\ \dots \end{matrix}

Järeldused

Kui arvud $a, b$ on ühismõõduta, siis võrrandil

a x + b y = 1

on täisarvulisi lahendeid^[9] See oluline fakt hõlbustab esimest järku diofantiliste võrrandite lahendamist.

SÜT $(a, b)$ on vähim naturaalarv, mida saab esitada arvude $a$ ja $b$ täisarvuliste kordajatega lineaarkombinatsioonina^[10].

Täisarvuliste kordajatega lineaarkombinatsioonide hulk ${a x + b y}$ langeb kokku arvu SÜT $(a, b)$ kordsete hulgaga^[11].

Rakendused

Bézout' lemmal on matemaatikas ja eriti arvuteoorias põhjapanev tähtsus. Nii näiteks saab sellest tuletada Eukleidese lemma, millest järeldub algteguriteks lahutuse ühesus. Ka Hiina jäägiklassiteoreem järeldub Bézout' lemmast. Lineaarsete diofantiliste võrrandite korral annab Bézout' lemma nende lahenduvuse kriteeriumi. Bézout' lemmat kasutatakse ka kongruentside lahendamisel.

Esimese astme diofantiliste võrrandite lahendamine

Vaatleme diofantiliste võrrandite kujul

a x + b y = c

täisarvuliste lahendite leidmist. Täistame $d =$ SÜT $(a, b) .$ On ilmne, et võrrandil on täisarvulisi lahendeid ainult juhul, kui $c$ jagub arvuga $d$ . Eeldame, et see tingimus on täidetud, ja leiame ühega ülaltoodud algoritmidest Bézout' kordajad $x, y$ :

a x + b y = d .

Siis on algse võrrandi lahendiks paar $c_{1} x, c_{1} y$ , kus $c_{1} = c / d$ .

Esimese astme kongruentside lahendamine

Esimese astme kongruentsi

a x \equiv b (\mod m)

lahendamiseks piisab selle teisendamisest kujule^[11]

a x + m y = b .

Praktilise tähtsusega erijuht on pöördelemendi leidmine jäägiklassiringis, s.o kongruentsi

a x \equiv 1 (\mod m)

lahendamine.

Üldistused

Lemmat saab üldistada enamale kui kahele täisarvule: kui $a_{1}, \dots, a_{n}$ on täisarvud, mis ei võrdu kõik nulliga, siis leiduvad täisarvulised kordajad $s_{1}, \dots, s_{n}$ nii, et

s_{1} a_{1} + \dots + s_{n} a_{n} =

SÜT

(a_{1}, \dots, a_{n})

.

Integriteetkondi, kus Bézout' lemma kehtib, nimetatakse Bézout' ringideks. Nende seas on Gaussi täisarvude ring.

Bézout' lemma kehtib igas peaideaaliringis, isegi ühes mittekommutatiivses ringis (Hurwitzi kvaternioonid). Lemma kehtib Eukleidese ringides.

Peaideaaliringid on integriteetkonnad, milles iga ideaal on peaideaal. Seal leidub ringi elementide a ja b korral alati element c nii, et ideaal aR+bR on peaideaal cR. Element c on siis ühelt poolt elementide a ja b ühine jagaja ning teiselt poolt a ja b lineaarkombinatsioon. Peaideaaliringides kehtib Bézout' lemma seetõttu otsekui definitsiooni kohaselt, kui võtta elementi c kui a ja b suurimat ühistegurit.

Näide. Formuleering (ühe muutuja) polünoomide ringi korral:

Olgu

{(P_{i})}_{i \in I}

mingi polünoomide pere, kusjuures need ei võrdu kõik nulliga. Tähistame tähega

Δ

nende suurima ühisteguri. Siis leidub polünoomide pere

{(A_{i})}_{i \in I}

nii, et kehtib seos:

Δ = \sum_{i \in I} A_{i} P_{i}

.

Kahe ühe muutuja polünoomi Bézout' kordajad saab arvutada analoogselt täisarvude juhtumiga (laiendatud Eukleidese algoritmi abil) ^[12]. Kahe polünoomi ühised juured on ka nende suurima ühisteguri juured, sellepärast järeldub Bézout' lemmast ja algebra põhiteoreemist järgmine tulemus:

Olgu antud polünoomid

f (x)

ja

g (x)

kordajatega mingis korpuses. Siis polünoomid

a (x)

ja

b (x)

nii, et

a f + b g = 1

, leiduvad siis ja ainult siis, kui polünoomidel

f (x)

ja

g (x)

ei ole ühiseid juuri mitte üheski algebraliselt kinnises korpuses (viimaseks võetakse tavaliselt kompleksarvude korpus).

Selle tulemuse üldistus kui tahes paljudele pölünoomidele ja tundmatutele on Hilberti teoreem nullkohtadest.

Ajalugu

Selle tulemuse avaldas esimesena 1624. aastal Claude-Gaspard Bachet de Méziriac ühisteguriteta arvude kohta^[13]. Bаchet' formuleering on järgmine: "Antud on kaks ühisteguriteta arvu, leidke kummagi vähim kordne, mis ületab ühe võrra teise kordset"^[14]. Ülesande lahendamiseks kasutas Bachet Eukleidese algoritmi.^[15]

Étienne Bézout oma neljaköitelises "Matemaatikakursuses" (Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine, kd 3, 1766) üldistas teoreemi, laiendades selle suvalistele arvupaaridele ning ka polünoomidele.^[16]

Viited

Mall:Viited

Välislingid

↑ Хассе Г. Лекции по теории чисел, М.: Изд. иностранной литературы, 1953, lk 29.
↑ Jones, G. A., Jones, J. M. §1.2. Bezout's Identity. – Elementary Number Theory, Berlin: Springer-Verlag 1998, lk 7—11.
↑ Tõepoolest, kui $d \in ℤ$ on arvude $a$ ja $b$ ühine jagaja, järelikult $a = a^{'} d$ ja $b = b^{'} d$ , siis $1 = s a^{'} d + t b^{'} d = (s a^{'} + t b^{'}) d = 1$ , järelikult on $d$ arvu 1 jagaja. ■
↑ Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел, М.: Наука 1965, lk 28.
↑ Гельфонд А. О. Решение уравнений в целых числах, Наука 1983, |Популярные лекции по математике, 8, lk 9—10.
↑ Егоров Д. Ф. Элементы теории чисел, Москва—Петроград: Госиздат 1923, 1k 14.
↑ ^7,0 ^7,1 Сушкевич А. К. Теория чисел. Элементарный курс, Харьков: Изд-во Харьковского университета 1954, lk 49—51.
↑ Хинчин А. Я. Цепные дроби, 3. trükk, М.: ГИФМЛ 1961, lk 11—12.
↑ Хассе 1953: 33.
↑ Фаддеев Д. К. Лекции по алгебре. Учебное пособие для вузов, Наука 1984, lk 9.
↑ ^11,0 ^11,1 Bezout's identity, brilliant.org.
↑ Коблиц Н. Курс теории чисел и криптографии, М.: Научное изд-во ТВП 2001, lk 19, ISBN 5-94057-103-4.
↑ Математика XVII столетия. – А. П. Юшкевич (toim). История математики, 3 kd, М.: Наука 1970, kd II, lk 75.
↑ Problèmes plaisants et délectables. – Claude Gaspard Bachet, sieur de Méziriac. Problemes plaisans, qui se font par nombres, 2. trükk, Lyons: Pierre Rigaud & Associates 1624, lk 18—33.
↑ Wolfgang K. Seiler. Zahlentheorie, loengukonspekt, Uni Mannheim, 2018
↑ Seiler 2018.

[1] Хассе Г. Лекции по теории чисел, М.: Изд. иностранной литературы, 1953, lk 29.

[2] Jones, G. A., Jones, J. M. §1.2. Bezout's Identity. – Elementary Number Theory, Berlin: Springer-Verlag 1998, lk 7—11.

[3] Tõepoolest, kui $d \in ℤ$ on arvude $a$ ja $b$ ühine jagaja, järelikult $a = a^{'} d$ ja $b = b^{'} d$ , siis $1 = s a^{'} d + t b^{'} d = (s a^{'} + t b^{'}) d = 1$ , järelikult on $d$ arvu 1 jagaja. ■

[4] Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел, М.: Наука 1965, lk 28.

[5] Гельфонд А. О. Решение уравнений в целых числах, Наука 1983, |Популярные лекции по математике, 8, lk 9—10.

[6] Егоров Д. Ф. Элементы теории чисел, Москва—Петроград: Госиздат 1923, 1k 14.

[SUSH-7] 7,0 ^7,1 Сушкевич А. К. Теория чисел. Элементарный курс, Харьков: Изд-во Харьковского университета 1954, lk 49—51.

[8] Хинчин А. Я. Цепные дроби, 3. trükk, М.: ГИФМЛ 1961, lk 11—12.

[9] Хассе 1953: 33.

[10] Фаддеев Д. К. Лекции по алгебре. Учебное пособие для вузов, Наука 1984, lk 9.

[brill-11] 11,0 ^11,1 Bezout's identity, brilliant.org.

[12] Коблиц Н. Курс теории чисел и криптографии, М.: Научное изд-во ТВП 2001, lk 19, ISBN 5-94057-103-4.

[13] Математика XVII столетия. – А. П. Юшкевич (toim). История математики, 3 kd, М.: Наука 1970, kd II, lk 75.

[14] Problèmes plaisants et délectables. – Claude Gaspard Bachet, sieur de Méziriac. Problemes plaisans, qui se font par nombres, 2. trükk, Lyons: Pierre Rigaud & Associates 1624, lk 18—33.

[15] Wolfgang K. Seiler. Zahlentheorie, loengukonspekt, Uni Mannheim, 2018

[16] Seiler 2018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Bézout' lemma

Sisukord

Formuleeringud

Näited

Tõestus

Tõestus jäägiga jagamise kaudu

Tõestus kongruentside kaudu

Bézout' kordajad

Mitteühesus

Kordajate arvutamine Eukleidese algoritmi abil

Kordajate arvutamine ahelmurdude abil

Minimaalsed kordajate paarid

Järeldused

Rakendused

Esimese astme diofantiliste võrrandite lahendamine

Esimese astme kongruentside lahendamine

Üldistused

Ajalugu

Viited

Välislingid

Navigeerimismenüü

Bézout' lemma

Formuleeringud

Näited

Tõestus

Tõestus jäägiga jagamise kaudu

Tõestus kongruentside kaudu

Bézout' kordajad

Mitteühesus

Kordajate arvutamine Eukleidese algoritmi abil

Kordajate arvutamine ahelmurdude abil

Minimaalsed kordajate paarid

Järeldused

Rakendused

Esimese astme diofantiliste võrrandite lahendamine

Esimese astme kongruentside lahendamine

Üldistused

Ajalugu

Viited

Välislingid

Navigeerimismenüü

Otsing