Sveikųjų skaičių dalumas ir Euklido algoritmas
Kartojant dalybą apskaičiuojamas didžiausias bendrasis daliklis.
Esminės žinios
Teigiamiems sveikiesiems skaičiams a ir b dalyba su liekana a = qb + r, 0 ≤ r < b, išsaugo lygybę gcd(a,b) = gcd(b,r). Kai liekana pirmą kartą tampa lygi nuliui, esamas daliklis yra didžiausias bendrasis daliklis. Egzistuoja sveikieji skaičiai u,v, tenkinantys lygybę ua + vb = gcd(a,b).
Vertės ir lygtys
a = qb + r; gcd(a,b) = gcd(b,r)
- a, b
- Teigiamos sveikosios įvesties reikšmės dalybos žingsnyje
- q
- Sveikasis dalmuo
- r
- Liekana, tenkinanti sąlygą 0 ≤ r < b
Sąlygos ir taikymo ribos
- Dabartinis daliklis yra teigiamas; sustokite, kai liekana lygi nuliui.
- Šiame įraše įvesties reikšmės apribojamos teigiamais sveikaisiais skaičiais.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Teoremos 6.1–6.3: dalyba / DBD / Bezu tapatybė; Euklido algoritmo pavyzdys; teorema 6.7: skaidymas pirminiais dauginamaisiais.
2026-10-10 · Sveikųjų skaičių dalyba, DBD radimas Euklido algoritmu ir Bezu tapatybė.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- math-divisibility-gcd
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas