Lyginiai ir modulinė aritmetika

Penki žingsniai nuo vienuolikos nuveda į keturis

Pažymėkite dvylika vienodais tarpais išdėstytų padėčių 0,1,2,…,11. Pradėkite nuo 11 ir judėkite penkias padėtis pirmyn: 0,1,2,3,4. Sveikųjų skaičių suma yra 11+5 = 16, o ją atitinkanti padėtis šiame ciferblate yra 4. Atėmus vieną visą apsisukimą, 12, padėtis nepasikeičia.

Šiame ciferblate naudojama liekana 0 ten, kur įprastame laikrodyje gali būti užrašyta 12. Šis skaičiavimas nereiškia, kad 16 lygu 4 arba kad penkios praėjusios valandos prilygsta neigiamam septynių valandų poslinkiui. Jis rodo tą pačią galutinę padėtį, atmetus visus apsisukimus. Numatykite padėtį prieš atskleisdami kryptingų žingsnių seką.

Pasiruoškite: sveikųjų skaičių su ženklu aritmetika

Paskelbtoje pamokoje „Daugyba ir dalyba“ pateikiamos tikslios sandaugos ir dalyba su liekana; pamokoje „Neigiami skaičiai ir absoliučioji vertė“ – sveikieji skaičiai su ženklu. Pamoka „Laipsniai, šaknys ir realiųjų skaičių tiesė“ parengia kartotinės daugybos pavyzdžiui. Toliau pateiktos pasiruošimo nuorodos grąžina prie šios pamokos įrodymų ir sprendinių formulės.

Simboliu ℤ žymėkite visus sveikuosius skaičius, įskaitant nulį ir neigiamus sveikuosius skaičius. Sveikiesiems skaičiams h,t žymėjimas h | t reiškia, kad t = hk su tam tikru sveikuoju skaičiumi k; h ∤ t reiškia, kad tokio sveikojo skaičiaus nėra. Pasirinkite ir užfiksuokite sveikąjį modulį m ≥ 2. Rašykite a ≡ b (mod m), kai m | (a−b), ir a ≢ b (mod m), kai šio dalumo nėra.

Pirmą kartą skaitydami išnagrinėkite ciferblatą, kanonines liekanas ir aritmetikos taisykles, tada pabandykite atlikti skaičiavimus pagal išnagrinėtus pavyzdžius. Prieš nagrinėdami prastinimą ar spręsdami tiesines kongruencijas, grįžkite prie bendrųjų daliklių ir kombinacijų su sveikaisiais koeficientais. Reikalingi teiginiai apie didžiausią bendrąjį daliklį ir dalybą su liekana įrodomi čia pat, todėl nė viena planuojama pamoka nėra privaloma paskelbta išankstinio pasirengimo medžiaga.

Kiekvienas sveikasis skaičius turi vieną liekaną nuo nulio iki m−1

Kanoninė liekana yra vienintelis r, tenkinantis 0 ≤ r < m, kuriam a = qm+r su sveikuoju q. Dalmuo q gali būti neigiamas. Dalijant −17 moduliu 7, teisinga lygybė yra −17 = (−3)·7+4, todėl kanoninė liekana yra 4. Neigiama liekana, gauta dalmenį apvalinant nulio link, nėra šis pasirinktas atstovas.

Neneigiamam sveikajam skaičiui A parinkite didžiausią neneigiamą sveikąjį q, kuriam qm ≤ A; galimi q sudaro baigtinį netuščią sąrašą. Tuomet r = A−qm yra neneigiamas ir mažesnis už m, nes jei r ≥ m, tiktų ir q+1. Neigiamam sveikajam skaičiui a pirmiausia parinkite sveikąjį K ≥ 0, kuriam a+Km ≥ 0, padalykite šį neneigiamą sveikąjį skaičių, tada iš jo dalmens atimkite K. Taip kiekvienam sveikajam a gaunamos tos pačios liekanos ribos.

Jei a = qm+r = q′m+r′ ir abi liekanos priklauso šiam intervalui, tai r−r′ yra m kartotinis, kurio absoliučioji vertė mažesnė už m. Vienintelis toks kartotinis yra 0, todėl r = r′ ir q = q′. Taigi kanoninis atstovas yra vienintelis.

Du sveikieji skaičiai yra kongruentūs moduliu m tada ir tik tada, kai jų kanoninės liekanos sutampa. Kai liekanos lygios, šių skaičių skirtumas yra m kartotinis. Ir atvirkščiai: užrašius abi dalybos lygybes, iš to, kad skaičių skirtumas yra m kartotinis, išplaukia, jog jų liekanų skirtumas taip pat yra m kartotinis, kurio absoliučioji vertė mažesnė už m, taigi lygus nuliui. Kongruentūs sveikieji skaičiai vis tiek gali būti nelygūs.

Vienoje klasėje yra be galo daug sveikųjų skaičių

Atstovo r klasę sudaro visi sveikieji skaičiai r+mk, kur k ∈ ℤ. Kai r = 4, m = 7, jai priklauso …,−17,−10,−3,4,11,18,… . Toliau pateikti šeši pavyzdiniai taškai priklauso vienai begalinei klasei. Kiekvieną jos narį apibūdina formulė, o ne baigtinis brėžinys. Yra lygiai m klasių, kurių atstovai yra 0,1,…,m−1.

Kongruencija yra refleksyvi: a−a = 0 = m·0. Ji yra simetrinė: jei a−b = mk, tai b−a = m(−k). Ji yra tranzityvi: jei a−b = mk ir b−c = mℓ, tai a−c = m(k+ℓ). Sąryšis, turintis šias tris savybes, vadinamas ekvivalentiškumo sąryšiu.

Šie įrodymai galioja visiems sveikiesiems skaičiams iš nurodytos srities. Jie paaiškina, kodėl kongruencijos klasės sudaro nuosekliai apibrėžtas grupes, o ne remiasi kelių sveikųjų skaičių išvardijimu. Simbolis ℓ tiesiog žymi kitą sveikąjį koeficientą.

Prieš sudėdami ar daugindami pakeiskite skaičius liekanomis

Tarkime, a ≡ a′ ir b ≡ b′ tuo pačiu moduliu m. Sumų skirtumas yra (a−a′)+(b−b′), o skirtumų skirtumas yra (a−a′)−(b−b′). Abu yra sveikieji m kartotiniai. Taigi a+b ≡ a′+b′ ir a−b ≡ a′−b′ moduliu m.

Sandaugoms galioja ab−a′b′ = b(a−a′)+a′(b−b′). Kiekvienas dėmuo yra m kartotinis, todėl ab ≡ a′b′. Pasirinkus b = b′, lyginį taip pat galima dauginti iš bet kurios sveikosios konstantos. Dauginant nereikia prielaidos, kad skaičiai yra tarpusavyje pirminiai.

Kiekvienam teigiamam sveikajam laipsnio rodikliui e iš a ≡ a′ išplaukia a^e ≡ (a′)^e moduliu m. Atvejis e = 1 yra prielaida. Jei teiginys galioja rodikliui e, sandaugos taisyklė, pritaikyta a^e·a, įrodo jį rodikliui e+1. Ši indukcija įrodo teiginį visiems teigiamiems laipsnio rodikliams; neigiamiems laipsniams reikia atvirkštinio elemento, ir ši laipsnių taisyklė jų neapima.

Pavyzdžiui, skaičiaus 44 liekana yra 2, o skaičiaus −17 liekana yra 4 moduliu 7. Jų sumos 27 liekana yra 6; jų skirtumo 61 liekana yra 5; jų sandaugos −748 liekana yra 1. Skaičiuodami su klasių atstovais gauname 2+4 = 6, 2−4 ≡ 5 ir 2·4 ≡ 1.

Didelio laipsnio skaičiavimas kartotinai keliant kvadratu

Norėdami rasti 3^13 moduliu 7, pirmiausia apskaičiuokite 3² ≡ 2, tada kelkite kvadratu, kad gautumėte 3⁴ ≡ 4 ir 3⁸ ≡ 2. Kadangi 13 = 8+4+1, sudauginkite šiuos tris laipsnio rodiklio dėmenis atitinkančias liekanas: 2·4·3 = 24 ≡ 3 (mod 7). Keliant kvadratu gautas laipsnis su rodikliu 2 yra apskaičiuotas, bet nepasirenkamas.

Kiekviename etape sandaugos ir teigiamų laipsnių taisyklės pagrindžia skaičiaus pakeitimą jo liekana. Laipsnio rodiklių langeliuose nurodytos tikslios rodiklių vertės, o ne skaitinės ploto ar aukščio vertės. Išsamioje lentelėje pažymėti pasirinkti rodiklio dėmenys, todėl skaičiavimą galima suprasti ir nesiremiant spalvomis.

Dauginti galima visada, prastinti – tik su sąlyga

Moduliu 6 sandaugos 2·1 = 2 ir 2·4 = 8 yra kongruenčios, tačiau 1 ir 4 nėra kongruentūs moduliu 6. Daugyba iš 2 skirtingas pradines klases 1 ir 4 atvaizduoja į tą patį rezultatą. Todėl suprastinus iš 2 ir palikus pradinį modulį būtų prarastas tikras skirtumas.

Toliau pateiktas visas daugybos atvaizdis susieja visas šešias pradines reikšmes su jų rezultatais. Kiekvienas gaunamas rezultatas turi du pirmavaizdžius; kitų liekanų gauti neįmanoma. Palyginkite jį su daugyba iš 3 moduliu 7, kuri septynias pradines reikšmes atvaizduoja į septynis skirtingus rezultatus. Toliau įrodysime tikslią sąlygą, lemiančią šį skirtumą.

Dalyba su liekana duoda naudingą tiesinę kombinaciją su sveikaisiais koeficientais

Sveikajam skaičiui c ir m ≥ 2 pažymėkime d = gcd(c,m) jų didžiausią teigiamą bendrąjį daliklį. Skaičių c ir m bendrieji dalikliai yra tie patys kaip |c| ir m; |c| yra neneigiamas skaičiaus c modulis. Tokių daliklių yra, nes 1 dalija abu skaičius, o jų sąrašas baigtinis, nes jie dalija teigiamą skaičių m. Jei c = 0, tai d = m. Skaičiai yra tarpusavyje pirminiai, kai d = 1.

Padalykite neneigiamą A iš teigiamo B ir užrašykite A = qB+r, kur 0 ≤ r < B. Sveikasis skaičius dalija ir A, ir B tada ir tik tada, kai jis dalija ir B, ir r: viena kryptimi atimkite qB, kita – pridėkite qB. Todėl pakeitus (A,B) į (B,r) išlieka visi bendrieji dalikliai. Kartojant pasiekiama liekana 0, nes teigiamos liekanos griežtai mažėja. Paskutinė nenulinė liekana yra d.

Sekite pradinių c,m tiesines kombinacijas su sveikaisiais koeficientais. Iš pradžių m = 0·c+1·m ir |c| = s·c+0·m, kur s = 1, kai c ≥ 0, ir s = −1, kai c < 0. Iš vienos kombinacijos atėmus kitą, padaugintą iš q, vėl gaunama tiesinė kombinacija su sveikaisiais koeficientais. Todėl paskutinė nenulinė liekana tenkina lygybę d = uc+vm, kur u,v yra sveikieji skaičiai. Tai Bezu tapatybė. Kai c = 0, ši tapatybė yra tiesiog m = 0·c+1·m.

Kai c = 7,m = 26, dalybos su liekana yra 26 = 3·7+5; 7 = 1·5+2; 5 = 2·2+1; 2 = 2·1+0. Atgaliniu įstatymu gauname 1 = 5−2·2 = 3·5−2·7 = 3·26−11·7. Sveikieji koeficientai yra u = −11 ir v = 3.

Atvirkštinis elementas: sandaugos liekana – vienetas

Skaičiaus c atvirkštinis elementas moduliu m yra sveikasis skaičius t, tenkinantis ct ≡ 1 (mod m). Jei d = 1, iš tapatybės uc+vm = 1 gauname cu ≡ 1; kanoninė u liekana yra kanoninis atvirkštinis elementas. Ir atvirkščiai: jei ct−1 yra m kartotinis, kiekvienas bendras c,m daliklis dalija ct ir ct−1, taigi dalija ir 1. Todėl atvirkštinis elementas egzistuoja tada ir tik tada, kai gcd(c,m) = 1.

Jo kanoninis atstovas yra vienintelis. Jei ct ≡ cs ≡ 1, padauginkite ct ≡ cs iš t ir, remdamiesi ct ≡ 1 bei sandaugos taisykle, gaukite t ≡ s. Du kanoniniai atstovai iš 0,…,m−1, kurie yra kongruentūs, turi būti lygūs. Kiti sveikieji atvirkštiniai elementai yra kongruentūs atstovai; vienatinumas nereiškia, kad tinka tik vienas sveikasis skaičius.

Tapatybė 1 = 3·26−11·7 duoda atvirkštinį elementą −11 ≡ 15 moduliu 26. Patikrinkite: 7·15 = 105 = 4·26+1. O 6 neturi atvirkštinio elemento moduliu 15, nes jų didžiausiasis bendrasis daliklis yra 3. Neigiamas sveikasis skaičius −3 turi atvirkštinį elementą 2 moduliu 7, nes −6 = (−1)·7+1. Nulis neturi atvirkštinio elemento jokiam m ≥ 2.

Modulį išlaikykite tik kai daugiklis su juo tarpusavyje pirminis

Jei gcd(c,m) = 1 ir m dalija c(a−b), pasinaudokite uc+vm = 1. Padauginę iš a−b, gauname a−b = uc(a−b)+vm(a−b), t. y. m kartotinių sumą. Taigi a ≡ b (mod m). Tai įrodo, kad galima suprastinti išlaikant pradinį modulį; dauginant gaunama atvirkštinė implikacija.

Kai c yra bet koks, užrašykite d = gcd(c,m), c′ = c/d ir m′ = m/d. Padaliję Bezu tapatybę iš d, gauname uc′+vm′ = 1. Taigi c′ ir m′ yra tarpusavyje pirminiai. Dalumo sąlyga m | c(a−b) yra lygiavertė m′ | c′(a−b), o ši – m′ | (a−b). Todėl ca ≡ cb (mod m) galioja tada ir tik tada, kai a ≡ b (mod m/d).

Jei m/d = 1, ši paskutinė dalumo sąlyga teigia, kad bet kuris sveikųjų skaičių skirtumas dalijasi iš 1; supaprastinta sąlyga tenkinama automatiškai. Tik čia vartojamas sutrumpintas žymėjimas moduliu 1, kurio vienintelė liekana yra 0. Jis neleidžia suprastinti išlaikant pradinį modulį. Kai c = 0, jis teisingai išreiškia, kad 0a ir 0b visada sutampa.

Neteisingo suprastinimo pavyzdyje, kai c = 2,m = 6, sumažintas modulis yra 3. Teisinga išvada yra 1 ≡ 4 (mod 3). Kai c ir m yra tarpusavyje pirminiai, sumažintas modulis lygus m, todėl neprarandama jokios informacijos apie liekanas.

Išspręskite tiesinę kongruenciją ir išlaikykite visas klases

Nagrinėkime cx ≡ b (mod m), kur c, b, x yra sveikieji skaičiai ir m ≥ 2. Tegul d = gcd(c,m). Jei yra sprendinys, tai cx−km = b su tam tikru sveikuoju skaičiumi k, todėl d turi dalyti b. Jei d ∤ b, sprendinių nėra.

Jei d | b ir uc+vm = d, padauginkime iš b/d: c·u(b/d)+m·v(b/d) = b. Taigi x₀ = u(b/d) yra sprendinys. Bet kuris kitas x yra sprendinys tada ir tik tada, kai m | c(x−x₀). Pagal patikslintą prastinimo taisyklę x = x₀+(m/d)k su tam tikru sveikuoju skaičiumi k. Tai įrodo ir tai, kad kiekvienas nurodytas sveikasis skaičius tinka, ir tai, kad nepraleistas nė vienas sprendinys.

Pasirinkime kanoninį x₀ iš 0,…,m/d−1, prireikus pakeisdami jį kongruenčiu sveikuoju skaičiumi, besiskiriančiu m/d kartotiniu. Tarp 0,…,m−1 yra lygiai d sprendinių atstovų: x₀, x₀+m/d,…,x₀+(d−1)m/d. Jie yra skirtingi ir neperžengia nurodytų ribų. Sveikųjų sprendinių yra be galo daug, tačiau sprendinių klasių moduliu m yra tik d.

Kongruencijai 6x ≡ 8 (mod 14) turime d = 2 ir 2 = 14−2·6. Pradinis sprendinys yra x₀ = −2·4 = −8; jo atstovas moduliu 7 yra 6. Visi sveikieji sprendiniai yra x = 6+7k, o dvi kanoninės liekanos moduliu 14 yra 6 ir 13. Abi jų sandaugos 36 ir 78 duoda liekaną 8.

Kai koeficientas lygus nuliui, taikomas tas pats kriterijus. Kongruencijai 0x ≡ b (mod m) turime d = m. Jei m | b, tinka kiekvienas sveikasis skaičius x, todėl gauname visas m liekanų klases, o tarpas tarp sprendinių yra 1. Jei m ∤ b, netinka nė vienas. Formulėje niekada nedalijama iš c, todėl c = 0 nesukuria nei išimties, nei neapibrėžto veiksmo.

Numatykite rezultatą, tada išnagrinėkite visas baigtinio atvejo galimybes

Išbandykite ciferblato poslinkius su ženklu, neigiamus klasės elementus, daugybos atvaizdžius, kuriuose skirtingi argumentai duoda tą patį rezultatą arba tokių sutapimų nėra, ir atvirkštinius elementus, kai koeficientai teigiami, neigiami ir lygūs nuliui. Tiesiniu atveju, prieš atskleisdami visų galimų kandidatų sandaugas, numatykite, ar tikslinė reikšmė pasiekiama ir kiek liekanų klasių tinka.

Baigtinės lentelės apima visus nurodyto modulio arba veiksmų sekos atvejus. Jos gali patvirtinti konkretų pavyzdį ir atskleisti kontrpavyzdį. Bendrosios taisyklės, galiojančios kiekvienam sveikajam skaičiui, išplaukia iš pirmiau pateiktų įrodymų, o ne iš riboto sąrašo tikrinimo.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Nurodykite skaičiaus 35 kanoninę liekaną moduliu 12 ir skaičiaus −25 kanoninę liekaną moduliu 6, taip pat abu dalmenis.

   Rodyti atsakymą ir paaiškinimą

   35 = 2·12+11 ir −25 = (−5)·6+5, todėl liekanos yra 11 ir 5.

   Abi liekanos yra neneigiamos ir mažesnės už nurodytą modulį. Kad būtų tenkinamos šios ribos, antrasis dalmuo turi būti −5, o ne −4.

2. Ar 19 ir −1 yra lygūs? Ar jie kongruentūs moduliu 5? Nurodykite dar tris jų klasės narius.

   Rodyti atsakymą ir paaiškinimą

   Jie nėra lygūs, bet yra kongruentūs moduliu 5. Kitų narių pavyzdžiai: −6,4,9.

   Jų skirtumas yra 20 = 4·5. Kiekvienas narys yra pavidalo 4+5k, kur k yra sveikasis skaičius; skirtingi sveikieji skaičiai gali atstovauti tai pačiai liekanų klasei.

3. Jei a−b = 7u ir b−c = 7v, kur u ir v yra sveikieji skaičiai, įrodykite, kad a ≡ c (mod 7).

   Rodyti atsakymą ir paaiškinimą

   a−c = (a−b)+(b−c) = 7(u+v), todėl 7 dalija a−c.

   Suma u+v yra sveikasis skaičius. Tai tranzityvumo įrodymas bet kokiems a, b ir c, o ne baigtinės imties patikrinimas.

4. Ar iš a ≡ b (mod 6) galima daryti išvadą, kad 2a ≡ 2b (mod 6)? Ar atvirkštinė implikacija galioja be papildomos sąlygos?

   Rodyti atsakymą ir paaiškinimą

   Dauginti galima. Atvirkštinė implikacija negalioja: a = 1, b = 4 yra kontrpavyzdys.

   Skirtumas, kuris yra modulio kartotinis, padauginus išlieka jo kartotiniu. Tačiau 2·1 ir 2·4 turi tą pačią liekaną 2, o 1 ir 4 liekanos moduliu 6 yra skirtingos.

5. Raskite skaičiaus −3 kanoninį atvirkštinį elementą moduliu 7. Ar 6 turi atvirkštinį elementą moduliu 15?

   Rodyti atsakymą ir paaiškinimą

   Skaičiaus −3 atvirkštinis elementas moduliu 7 yra 2. Skaičius 6 neturi atvirkštinio elemento moduliu 15.

   (−3)·2 = −6 ≡ 1 moduliu 7. Kiekviena sandauga 6t dalijasi iš 3, todėl jos skirtumas su 1 negali būti skaičiaus 15 kartotinis, kuris taip pat dalijasi iš 3.

6. Tiksliai nurodykite, kokia išvada gaunama suprastinus 5a ≡ 5b (mod 6) ir 3a ≡ 3b (mod 6).

   Rodyti atsakymą ir paaiškinimą

   Pirmoji kongruencija yra ekvivalenti a ≡ b (mod 6). Antroji yra ekvivalenti a ≡ b (mod 2).

   Didžiausieji bendrieji dalikliai yra 1 ir 3. Pradinį modulį padalykite iš atitinkamo didžiausiojo bendrojo daliklio; antrojoje išvadoje palikus 6, būtų atmestos kai kurios tinkamos poros.

7. Ar 6x ≡ 5 (mod 14) turi sveikąjį sprendinį?

   Rodyti atsakymą ir paaiškinimą

   Sprendinių nėra.

   Didžiausiasis bendrasis daliklis yra 2, o 5 iš jo nesidalija. Ir 6x, ir kiekvienas skaičiaus 14 kartotinis yra lyginiai, todėl jų skirtumas negali būti lygus nelyginiam skaičiui 5.

8. Pateikite visus kanoninius kongruencijos 4x ≡ 0 (mod 8) sprendinius, tada – visus sveikuosius sprendinius.

   Rodyti atsakymą ir paaiškinimą

   Kanoniniai atstovai yra 0,2,4,6. Visi sveikieji sprendiniai yra x = 2k, kur k ∈ ℤ.

   Didžiausiasis bendrasis daliklis yra 4, o žingsnis yra 8/4 = 2. Moduliu 8 yra lygiai keturios skirtingos sprendinių klasės, tačiau kongruenciją tenkina be galo daug lyginių sveikųjų skaičių.

9. Išspręskite 0x ≡ 0 (mod 6) ir 0x ≡ 1 (mod 6).

   Rodyti atsakymą ir paaiškinimą

   Pirmąją kongruenciją tenkina kiekvienas sveikasis skaičius, taigi sprendiniai sudaro visas šešias liekanų klases. Antroji sprendinių neturi.

   Skaičių 0 ir 6 didžiausiasis bendrasis daliklis yra 6, todėl dešinioji pusė turi dalytis iš 6. Skaičiuojant iš nulio nedalijama.

10. Remdamiesi 3² ≡ 2 ir 3⁴ ≡ 4 moduliu 7, raskite 3^5. Ar pasirenkamas keliant kvadratu gautas laipsnis su rodikliu 2?

    Rodyti atsakymą ir paaiškinimą

    3^5 ≡ 4·3 = 12 ≡ 5 (mod 7). Keliant kvadratu gautas laipsnis su rodikliu 2 nepasirenkamas.

    5 = 4+1. Pakartotinai keliant kvadratu gaunami naudingi tarpiniai laipsniai, tačiau į galutinę sandaugą įtraukiami tik tie laipsniai, kurių rodikliai yra pasirinktos sumos dėmenys.

11. Ar atvirkštinio elemento vienatis reiškia, kad 15 yra vienintelis sveikasis skaičius t, tenkinantis 7t ≡ 1 (mod 26)?

    Rodyti atsakymą ir paaiškinimą

    Ne. Tai vienintelis kanoninis atstovas, o kiekvienas t = 15+26k, kur k ∈ ℤ, taip pat tinka.

    Sandaugų skirtumas 7·26k yra skaičiaus 26 kartotinis. Vienaties teiginiui būtinas apribojimas 0 ≤ t < 26 arba, lygiavertiškai, liekanų klasės vienatis.

Ką verta įsidėmėti

• Kongruencija nusako skirtumo dalumą, o ne sveikųjų skaičių lygybę.
• Kanoninės liekanos yra vieninteliai atstovai 0,…,m−1, taip pat ir neigiamųjų sveikųjų skaičių atveju.
• Kai modulis fiksuotas, sudėtis, atimtis, daugyba ir kėlimas teigiamais sveikaisiais laipsniais išsaugo lyginį.
• Atvirkštinis elementas egzistuoja tada ir tik tada, kai koeficientas ir modulis yra tarpusavyje pirminiai; jo kanoninė liekana yra vienintelė.
• Koeficientą c suprastinkite sumažindami modulį iki m/gcd(c,m); modulį m palikite tik tada, kai šis didžiausiasis bendrasis daliklis lygus 1.
• Tiesinis lyginys cx ≡ b turi sprendinių tada ir tik tada, kai gcd(c,m) dalija b; atstumas tarp gretimų sveikųjų sprendinių yra m/gcd(c,m).
• Išsamios baigtinės lentelės patvirtina jose nurodytus atvejus. Bendrosioms taisyklėms reikia įrodymų sveikųjų skaičių srityje.