Jämförelser med enkel modulo. Modulo jämförelser

Innehåll.

Introduktion

§1. Modulo jämförelse

§2. Jämförelseegenskaper

1. Moduloberoende jämförelseegenskaper
2. Modulberoende egenskaper hos jämförelser

§3. Avdragssystem

1. Fullständigt system med avdrag
2. Minskat system för avdrag

§4. Eulers sats och Fermat

1. Euler funktion
2. Eulers sats och Fermat

Kapitel 2. Teori om jämförelser med en variabel

§1. Grundläggande begrepp relaterade till att lösa jämförelser

1. Jämförelsernas rötter
2. Likvärdighet av jämförelser
3. Wilsons teorem

§2. Första gradens jämförelser och deras lösningar

1. Urvalsmetod
2. Eulers metoder
3. Euklids algoritmmetod
4. Fortsatt fraktionsmetod

§3. System av jämförelser av 1: a graden med en okänd

§4. Indelning av jämförelser av högre grader

§5. Antiderivata rötter och index

1. Avdragsklassordning
2. Primitiva rötter modulo prime
3. Indexerar modulo prime

Kapitel 3. Tillämpning av teorin om jämförelser

§1. Tecken på delbarhet

§2. Kontrollera resultaten av aritmetiska operationer

§3. Omvandling av en vanlig fraktion till en slutlig fraktion

decimal systematisk bråkdel

Slutsats

Litteratur

Introduktion

I våra liv måste vi ofta hantera heltal och problem relaterade till dem. I denna avhandling behandlar jag teorin om jämförelse av heltal.

Två heltal vars skillnad är en multipel av ett givet naturligt tal m kallas jämförbara i modul m.

Ordet "modul" kommer från latinets modul, som på ryska betyder "mått", "magnitude".

Påståendet "a är jämförbart med b modulo m" skrivs vanligtvis som ab (mod m) och kallas jämförelse.

Definitionen av jämförelse formulerades i boken av K. Gauss "Arithmetic Studies". Detta arbete, skrivet på latin, började tryckas 1797, men boken publicerades först 1801 på grund av att tryckprocessen vid den tiden var extremt arbetskrävande och långdragen. Den första delen av Gauss bok heter: "Om jämförelsen av siffror i allmänhet."

Jämförelser är mycket bekväma att använda i de fall där det räcker att veta i någon forskning siffror exakta till multiplar av ett visst tal.

Till exempel, om vi är intresserade av vilken siffra kuben i ett heltal a slutar med, så räcker det för oss att bara veta upp till multipler av 10 och vi kan använda jämförelser modulo 10.

Syftet med detta arbete är att beakta teorin om jämförelser och studera de grundläggande metoderna för att lösa jämförelser med okända, samt att studera tillämpningen av teorin om jämförelser på skolmatematik.

Avhandlingen består av tre kapitel, där varje kapitel är indelat i stycken och stycken i stycken.

Det första kapitlet beskriver allmänna frågor om teorin om jämförelser. Här tar vi hänsyn till begreppet modulo-jämförelse, egenskaper hos jämförelser, det kompletta och reducerade systemet av rester, Eulers funktion, Eulers och Fermats sats.

Det andra kapitlet ägnas åt teorin om jämförelser med det okända. Den beskriver de grundläggande begreppen förknippade med att lösa jämförelser, diskuterar metoder för att lösa jämförelser av första graden (urvalsmetod, Eulers metod, metoden för den euklidiska algoritmen, metoden för fortsatta bråk, med användning av index), jämförelsesystem av första graden med en okänd, jämförelser av högre grader, etc. .

Det tredje kapitlet innehåller några tillämpningar av talteori på skolmatematik. Tecknen på delbarhet, kontroll av resultaten av åtgärder och omvandling av vanliga bråk till systematiska decimalbråk beaktas.

Presentationen av teoretiskt material åtföljs av ett stort antal exempel som avslöjar kärnan i de introducerade begreppen och definitionerna.

Kapitel 1. Allmänna frågor om jämförelseteorin

§1. Modulo jämförelse

Låt z vara ringen av heltal, m vara ett fast heltal och m·z vara mängden av alla heltal som är multipler av m.

Definition 1. Två heltal a och b sägs vara jämförbara modulo m om m delar a-b.

Om talen a och b är jämförbara modulo m, skriv a b (mod m).

Tillstånd a b (mod m) betyder att a-b är delbart med m.

a b (mod m)↔(a-b) m

Låt oss definiera att jämförbarhetsrelationen modulo m sammanfaller med jämförbarhetsrelationen modulo (-m) (delbarhet med m är ekvivalent med delbarhet med –m). Därför, utan förlust av generalitet, kan vi anta att m>0.

Exempel.

Sats. (ett tecken på jämförbarhet av andetal modulo m): Två heltal a och b är jämförbara modulo m om och endast om a och b har samma rester när de divideras med m.

Bevis.

Låt resten när a och b divideras med m vara lika, det vill säga a=mq₁+r,(1)

B=mq2+r, (2)

Där 0≤r≥m.

Subtrahera (2) från (1), vi får a-b= m(q₁- q₂), det vill säga a-b m eller a b (mod m).

Omvänt, låt a b (mod m). Detta innebär att a-b m eller a-b=mt, t z (3)

Dividera b med m; vi får b=mq+r i (3), vi får a=m(q+t)+r, det vill säga när man dividerar a med m får man samma rest som när man dividerar b med m.

Exempel.

5=4·(-2)+3

23=4·5+3

24=3·8+0

10=3·3+1

Definition 2. Två eller flera tal som ger identiska rester när de divideras med m kallas lika rester eller jämförbara modulo m.

Exempel.

Vi har: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², och (- m²) är dividerat med m => vår jämförelse är korrekt.

1. Bevisa att följande jämförelser är falska:

Om tal är jämförbara modulo m, så har de samma gcd med sig.

Vi har: 4=2·2, 10=2·5, 25=5·5

GCD(4,10) = 2, GCD(25,10) = 5, därför är vår jämförelse felaktig.

§2. Jämförelseegenskaper

1. Moduloberoende egenskaper för jämförelser.

Många egenskaper hos jämförelser liknar egenskaperna hos jämlikheter.

a) reflexivitet: aa (mod m) (vilket heltal som helst a jämförbar med sig själv modulo m);

B) symmetri: om a b (mod m), sedan b a (mod m);

C) transitivitet: om en b (mod m), och b med (mod m), sedan a med (mod m).

Bevis.

Genom villkor m/(a-b) och m/ (c-d). Därför är m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).

Exempel.

Hitta resten när du delar vid 13.

Lösning: -1 (mod 13) och 1 (mod 13), sedan (-1)+1 0 (mod 13), det vill säga resten av divisionen med 13 är 0.

a-c b-d (mod m).

Bevis.

Genom villkor m/(a-b) och m/(c-d). Därför m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (en konsekvens av fastigheterna 1, 2, 3). Du kan lägga till samma heltal på båda sidor av jämförelsen.

Bevis.

Låt a b (mod m) och k är vilket heltal som helst. Genom egenskapen reflexivitet

k=k (mod m), och enligt egenskaperna 2 och 3 har vi a+k b+k (mod m).

a·c·d (mod m).

Bevis.

Enligt villkor, a-b є mz, c-d є mz. Därför a·c-b·d = (a·c - b·c)+(b·c-b·d)=(a-b)·c+b·(c-d) є mz, det vill säga a·c·d (mod m).

Följd. Båda sidorna av jämförelsen kan höjas till samma icke-negativa heltalspotens: om ab (mod m) och s är ett icke-negativt heltal, sedan a s b s (mod m).

Exempel.

Lösning: uppenbarligen 13 1 (mod 3)

2 -1 (mod 3)

5 -1 (mod 3), sedan

- · 1-1 0 (mod 13)

Svar: den nödvändiga resten är noll och A är delbar med 3.

Lösning:

Låt oss bevisa att 1+ 0(mod13) eller 1+ 0(mod 13)

1+ =1+ 1+ =

Sedan 27 1 (mod 13), sedan 1+ 1+1·3+1·9 (mod 13).

etc.

3. Hitta resten när du dividerar med resten av ett tal vid 24.

Vi har: 1 (mod 24), alltså

1 (mod 24)

Lägger vi till 55 på båda sidor av jämförelsen får vi:

(mod 24).

Vi har: (mod 24), därför

(mod 24) för valfri k є N.

Därav (mod 24). Sedan (-8)16 (mod 24), den nödvändiga återstoden är 16.

1. Båda sidorna av jämförelsen kan multipliceras med samma heltal.

2. Egenskaper för jämförelser beroende på modul.

Bevis.

Eftersom a b (mod t), då (a - b) t. Och eftersom t n , då på grund av delbarhetsrelationens transitivitet(a - b n), det vill säga a b (mod n).

Exempel.

Hitta resten när 196 divideras med 7.

Lösning:

Att veta att 196= , vi kan skriva 196(mod 14). Låt oss använda den tidigare egenskapen, 14 7 får vi 196 (mod 7), det vill säga 196 7.

1. Båda sidorna av jämförelsen och modulen kan multipliceras med samma positiva heltal.

Bevis.

Låt a b (mod t ) och c är ett positivt heltal. Då är a-b = mt och ac-bc=mtc, eller ac bc (mod mc).

Exempel.

Bestäm om värdet på ett uttryck är ett heltal.

Lösning:

Låt oss representera bråk i form av jämförelser: 4(mod 3)

1 (mod 9)

31 (mod 27)

Låt oss lägga till dessa jämförelser term för term (egenskap 2), vi får 124(mod 27) Vi ser att 124 inte är ett heltal delbart med 27, därav betydelsen av uttrycketär inte heller ett heltal.

1. Båda sidorna av jämförelsen kan delas med sin gemensamma faktor om den är coprime till modulen.

Bevis.

Om ca cb (mod m), det vill säga m/c(a-b) och numret Med samprima till m, (c,m)=1, sedan delar m a-b. Därav, a b (mod t).

Exempel.

60 9 (mod 17), efter att ha dividerat båda sidor av jämförelsen med 3 får vi:

20 (mod 17).

I allmänhet är det omöjligt att dividera båda sidorna av jämförelsen med ett tal som inte är coprime till modulen, eftersom efter division kan de tal erhållas som är oförlikbara med avseende på en given modul.

Exempel.

8 (mod 4), men 2 (mod 4).

1. Båda sidorna av jämförelsen och modulen kan delas med sin gemensamma divisor.

Bevis.

Om ka kb (mod km), sedan divideras k (a-b) med km. Därför är a-b delbart med m, det vill säga a b (mod t).

Bevis.

Låt P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n. Genom villkor a b (mod t), alltså

a k b k (mod m) för k = 0, 1, 2, …,n. Multiplicera båda sidor av var och en av de resulterande n+1-jämförelserna med c n-k, vi får:

c n-k a k c n-k b k (mod m), där k = 0, 1, 2, …,n.

Lägger vi ihop de sista jämförelserna får vi: P (a) P (b) (mod m). Om a (mod m) och c i d i (mod m), 0 ≤ i ≤n, då

(mod m). I jämförelse med modulo m kan således individuella termer och faktorer ersättas med tal som är jämförbara modulo m.

Samtidigt bör det noteras att de exponenter som hittas i jämförelser inte kan ersättas på detta sätt: fr.o.m.

a n c(mod m) och n k(mod m) det följer inte att a k s (mod m).

Fastighet 11 har ett antal viktiga tillämpningar. I synnerhet är det med dess hjälp möjligt att ge en teoretisk motivering för tecknen på delbarhet. För att illustrera, som ett exempel, kommer vi att ge härledningen av delbarhetstestet med 3.

Exempel.

Varje naturligt tal N kan representeras som ett systematiskt tal: N = a O 10 n + a 1 10 n-1 + ... + a n-1 10 + a n.

Betrakta polynomet f(x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . Därför att

10 1 (mod 3), sedan efter egenskap 10 f (10) f(1) (mod 3) eller

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +...+ a n-1 + a n (mod 3), d.v.s. för att N ska vara delbart med 3, är det nödvändigt och tillräckligt att summan av siffrorna i detta tal är delbar med 3.

§3. Avdragssystem

1. Fullständigt system med avdrag.

Lika resttal, eller, vad är samma sak, jämförbara modulo m, bildar en klass av tal modulo m.

Av denna definition följer att alla tal i klassen motsvarar samma återstod r, och vi får alla tal i klassen om vi i formen mq+r får q att gå genom alla heltal.

Följaktligen, med m olika värden på r, har vi m klasser av tal modulo m.

Vilket nummer som helst i en klass kallas en restmodulo m med avseende på alla tal i samma klass. Återstoden som erhålls vid q=0, lika med resten r, kallas den minsta icke-negativa resten.

Resten ρ, den minsta i absoluta värde, kallas den absolut minsta resten.

Uppenbarligen har vi för r ρ=r; vid r> vi har ρ=r-m; slutligen, om m är jämnt och r=, då kan vilket som helst av de två talen tas som ρ och -m= -.

Låt oss välja från varje klass av rester modulo T ett nummer i taget. Vi får t heltal: x 1,..., x m. Mängden (x 1,..., x t) kallas komplett system av avdrag modulo m.

Eftersom varje klass innehåller ett oändligt antal rester, är det möjligt att komponera ett oändligt antal olika kompletta system av rester för en given modul m, som var och en innehåller t avdrag.

Exempel.

Sammanställ flera kompletta system av modulo-avdrag T = 5. Vi har klasser: 0, 1, 2, 3, 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

Låt oss skapa flera kompletta system av avdrag, med ett avdrag från varje klass:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

etc.

Den vanligaste:

1. Komplett system av minst icke-negativa rester: 0, 1, t-1 I exemplet ovan: 0, 1, 2, 3, 4. Detta system av rester är enkelt att skapa: du måste skriva ner alla icke-negativa rester som erhålls när du dividerar med m.
2. Komplett system av minst positiva rester(minsta positiva avdrag tas från varje klass):

1, 2, …, m. I vårt exempel: 1, 2, 3, 4, 5.

1. Ett komplett system med absolut minimala avdrag.Vid udda m representeras de absolut minsta resterna sida vid sida.

- ,…, -1, 0, 1,…, ,

och i fallet med jämn m, en av de två raderna

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

I exemplet: -2, -1, 0, 1, 2.

Låt oss nu överväga de grundläggande egenskaperna hos hela systemet av rester.

Sats 1 . Alla samlingar av m heltal:

x l ,x 2 ,…,x m (1)

parvis ojämförlig modulo m, bildar ett komplett system av rester modulo m.

Bevis.

1. Vart och ett av numren i samlingen (1) tillhör en viss klass.
2. Alla två siffror x i och x j från (1) är ojämförliga med varandra, d.v.s. de tillhöra olika klasser.
3. Det finns m tal i (1), dvs samma antal som det finns moduloklasser T.

x 1, x 2,..., x t - komplett system för avdrag modulo m.

Sats 2. Låt (a, m) = 1, b - godtyckligt heltal; sedan om x 1, x 2,..., x t är ett komplett system av rester modulo m, sedan samlingen av tal ax 1 + b, axe 2 + b,..., ax m + b är också ett komplett system av rester modulo m.

Bevis.

Låt oss överväga

Axe 1 + b, axe 2 + b,..., axe m + b (2)

1. Vart och ett av numren i samlingen (2) tillhör en viss klass.
2. Alla två tal ax i +b och ax j + b från (2) är ojämförliga med varandra, det vill säga de tillhör olika klasser.

Faktum är att om det i (2) fanns två siffror så att

ax i +b ax j + b (mod m), (i = j), då skulle vi få ax i ax j (mod t). Sedan (a, t) = 1, då kan jämförelsens egenskap reducera båda delarna av jämförelsen med A . Vi får x i x j (mod m).

Enligt villkor x i x j (mod t) vid (i = j), eftersom x 1, x 2, ..., x m - ett komplett system med avdrag.

1. Uppsättningen av nummer (2) innehåller T siffror, det vill säga så många som det finns klasser modulo m.

Så, axe 1 + b, axe 2 + b,..., ax m + b - komplett system av rester modulo m.

Exempel.

Låt m = 10, a = 3, b = 4.

Låt oss ta ett komplett system av rester modulo 10, till exempel: 0, 1, 2,..., 9. Låt oss komponera nummer av formen yxa + b. Vi får: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Den resulterande uppsättningen siffror är ett komplett system av rester modulo 10.

1. Det givna systemet för avdrag.

Låt oss bevisa följande teorem.

Sats 1.

Tal av samma restklass modulo m har samma största gemensamma divisor med m: if a b (mod m), sedan (a, m) = (b, m).

Bevis.

Låt a b (mod m). Då a = b +mt, där t є z. Av denna jämlikhet följer att (a, t) = (b, t).

Låt δ vara en gemensam divisor för a och m, sedan a 5, m 5. Eftersom a = b +mt, då b=a-mt, därför bδ. Därför är varje gemensam divisor för talen a och m en gemensam divisor för m och b.

Omvänt, om m δ och b δ, då a = b +mt är delbart med δ, och därför är varje gemensam divisor för m och b en gemensam divisor för a och m. Teoremet har bevisats.

Definition 1. Största gemensamma moduldelaren t och valfritt tal a från denna klass av avdrag med T kallas den största gemensamma delaren T och denna klass av avdrag.

Definition 2. Restklass a modulo t kallas coprime till modul m , om den största gemensamma delaren a och t är lika med 1 (det vill säga om m och alla tal från a är coprime).

Exempel.

Låt t = 6. Restklass 2 består av talen (..., -10, -4, 2, 8, 14, ...). Den största gemensamma divisorn för något av dessa tal och modul 6 är 2. Följaktligen är (2, 6) = 2. Den största gemensamma divisorn för något tal från klass 5 och modul 6 är 1. Klass 5 är alltså coprime till modul 6 .

Låt oss välja ett nummer från varje klass av rester som är coprime med modulo m. Vi får ett avdragssystem som ingår i det kompletta avdragssystemet. De ringer hennereducerat system av rester modulo m.

Definition 3. En uppsättning rester modulo m, tagen en från varje coprime med T klass av rester för denna modul kallas ett reducerat system av rester.

Från definition 3 följer en metod för att erhålla det reducerade systemet av modulo-rester T: det är nödvändigt att skriva ner något komplett system av rester och ta bort från det alla rester som inte är coprime med m. Den återstående uppsättningen av avdrag är det reducerade systemet med avdrag. Uppenbarligen kan ett oändligt antal system av rester modulo m sammansättas.

Om vi ​​tar det fullständiga systemet av minst icke-negativa eller absolut minsta rester som initialsystem, så får vi med den angivna metoden ett reducerat system av minst icke-negativa respektive absolut minsta rester modulo m.

Exempel.

Om T = 8, då är 1, 3, 5, 7 det reducerade systemet av minst icke-negativa rester, 1, 3, -3, -1- det reducerade systemet med absolut minsta avdrag.

Sats 2.

Låta antalet klasser coprime till m är lika med k.Sedan valfri samling av k heltal

parvis ojämförlig modulo m och coprime till m, är ett reducerat system av rester modulo m.

Bevis

A) Varje nummer i populationen (1) tillhör en viss klass.

1. Alla tal från (1) är parvis ojämförbara i modul T, det vill säga de tillhör olika klasser modulo m.
2. Varje siffra från (1) är coprime med T, det vill säga alla dessa tal tillhör olika klasser coprime till modulo m.
3. Totalt (1) tillgängligt k antal, det vill säga lika många som det reducerade systemet av rester modulo m bör innehålla.

Därför uppsättningen av siffror(1) - minskat system för modulo-avdrag T.

§4. Euler funktion.

Eulers och Fermats satser.

1. Euler funktion.

Låt oss beteckna med φ(T) antalet klasser av rester modulo m coprime till m, det vill säga antalet element i det reducerade systemet av rester modulo t. Funktion φ (t) är numerisk. De ringer henneEuler funktion.

Låt oss välja som representanter för modulo-restklasserna t nummer 1, ..., t - 1, t. Sedan φ (t) - antalet sådana siffror samprima med t. Med andra ord, φ (t) - antalet positiva tal som inte överstiger m och relativt primtal till m.

Exempel.

1. Låt t = 9. Det kompletta systemet av rester modulo 9 består av talen 1, 2, 3, 4, 5, 6, 7, 8, 9. Av dessa är talen 1,2,4, 5, 7, 8 coprime till 9. Så eftersom antalet av dessa siffror är 6, så är φ (9) = 6.
2. Låt t = 12. Det kompletta systemet av rester består av siffrorna 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Av dessa är siffrorna 1, 5, 7, 11 coprime till 12 . Detta betyder

φ(12) = 4.

Vid t = 1, det kompletta systemet av rester består av en klass 1. Den gemensamma naturliga divisorn för talen 1 och 1 är 1, (1, 1) = 1. På grundval av detta antar vi φ(1) = 1.

Låt oss gå vidare till att beräkna Euler-funktionen.

1) Om t = sid är ett primtal, då φ(p) = p- 1.

Bevis.

Avdrag 1, 2, ..., p- 1 och bara de är relativt primtal med ett primtal R. Därför φ (р) = р - 1.

2) Om t = p k - primär effekt p, då

φ(t) = (p - 1). (1)

Bevis.

Komplett system av modulo-avdrag t = pk består av nummer 1,..., p k - 1, p k Naturliga delare T är grader R. Därför numret Akan ha en gemensam divisor med m annan än 1, endast i fallet närAdelat medR.Men bland siffrorna 1, ... , sidk -1 påRendast siffror är delbaras, 2p, ... , sid2 , ... RTill, vars antal är likaRTill: p = pk-1. Det betyder att de är coprime medt = sidTillrestenRTill- Rk-1= sidk-l(p-1)tal. Detta bevisar det

φ (RTill) = sidk-1(p-1).

Sats1.

Eulerfunktionen är multiplikativ, det vill säga för relativt primtal m och n har vi φ (mn) = φ(m) φ (n).

Bevis.

Det första kravet i definitionen av en multiplikativ funktion är uppfyllt på ett trivialt sätt: Eulerfunktionen definieras för alla naturliga tal, och φ (1) = 1. Vi behöver bara visa att omtypcoprimtal alltså

φ (tp)= φ (T) φ (P).(2)

Låt oss ordna hela systemet med avdrag modulotpsomPXT -matriser

1 2 T

t+1 t+2 2t

………………………………

(P -1) t+1 (P -1) m+2 fre

Eftersom denTOchPär relativt primtal, sedan antaletXömsesidigt bara medtpdå och bara närXömsesidigt bara medTOchXömsesidigt bara medP. Men antaletkm+tömsesidigt bara medTom och endast omtömsesidigt bara medT.Därför finns siffror coprime till m i de kolumner för vilkatgår genom det reducerade systemet av modulo-resterT.Antalet sådana kolumner är lika med φ(T).Varje kolumn presenterar det kompletta systemet av avdrag moduloP.Från dessa slutsatser φ(P)samprima medP.Detta innebär att det totala antalet tal som är relativt primtal och medToch med n lika med φ(T)φ(n)

(φ (T)kolumner, i var och en av vilka φ tas(P)tal). Dessa siffror, och bara de, är coprime tilletc.Detta bevisar det

φ (tp)= φ (T) φ (P).

Exempel.

№1 . Bevisa giltigheten av följande likheter

φ(4n) =

Bevis.

№2 . Lös ekvationen

Lösning:därför att(m)=, Den där= , det är=600, =75, =3·, sedan x-1=1, x=2,

y-1=2, y=3

Svar: x=2, y=3

Vi kan beräkna värdet på Euler-funktionen(m), känna till den kanoniska representationen av talet m:

m=.

På grund av multiplikativitet(m) vi har:

(m)=.

Men enligt formel (1) finner vi det

-1), och därför

(3)

Jämlikhet (3) kan skrivas om som:

Eftersom den=m alltså(4)

Formel (3) eller, vilket är detsamma, (4) är vad vi letar efter.

Exempel.

№1 . Vad är beloppet?

Lösning:,

, =18 (1- ) (1- =18 , Då= 1+1+2+2+6+6=18.

№2 . Baserat på egenskaperna hos Eulertalsfunktionen, bevisa att det i sekvensen av naturliga tal finns en oändlig uppsättning primtal.

Lösning:Om vi ​​antar att antalet primtal är en ändlig mängd, antar vi det- det största primtalet och låt a=är produkten av alla primtal, baserat på en av egenskaperna hos Eulertalsfunktionen

Sedan a≥, då är a ett sammansatt tal, men eftersom dess kanoniska representation innehåller alla primtal, då=1. Vi har:

=1 ,

vilket är omöjligt, och därmed är det bevisat att mängden primtal är oändlig.

№3 .Lös ekvationen, där x=Och=2.

Lösning:Vi använder egenskapen för Eulers numeriska funktion,

,

och efter tillstånd=2.

Låt oss uttrycka från=2 , vi får, ersätta in

:

(1+ -1=120, =11 =>

Sedan x=, x=11·13=143.

Svar:x= 143

2. Eulers sats och Fermat.

Eulers teorem spelar en viktig roll i teorin om jämförelser.

Eulers teorem.

Om ett heltal a är coprime till m, då

(1)

Bevis.Låta

(2)

det finns ett reducerat system av rester modulo m.

Omaär ett heltal coprime till m, alltså

(3)

Överväg en jämförelse av formuläret x 2 ≡a(mod sidα), var sid– ett enkelt udda tal. Som framgår av punkt 4 i §4 kan lösningen på denna jämförelse hittas genom att lösa jämförelsen x 2 ≡a(mod sid). Dessutom jämförelsen x 2 ≡a(mod sidα) kommer att ha två lösningar om aär en kvadratisk restmodulo sid.

Exempel:

Lös kvadratisk jämförelse x 2 = 86 (mod 125).

125 = 5 3, 5 är ett primtal. Låt oss kontrollera om 86 är en kvadratisk modulo 5.

Den ursprungliga jämförelsen har 2 lösningar.

Låt oss hitta en lösning på jämförelsen x 2 ≡ 86 (mod 5).

x 2 ≡1 (mod 5).

Denna jämförelse skulle kunna lösas på det sätt som anges i föregående stycke, men vi kommer att använda det faktum att kvadratroten ur 1 modulo är ±1, och jämförelsen har exakt två lösningar. Sålunda är lösningen på jämförelsen modulo 5

x≡±1(mod 5) eller, på annat sätt, x=±(1+5 t 1).

Låt oss ersätta den resulterande lösningen i jämförelse modulo 5 2 =25:

x 2 ≡86 (mod 25)

x 2 ≡11 (mod 25)

(1+5t 1) 2 ≡11 (mod 25)

1+10t 1 +25t 1 2 ≡11 (mod 25)

10t 1 ≡10 (mod 25)

2t 1 ≡2 (mod 5)

t 1 ≡1(mod 5), eller, vad är detsamma, t 1 =1+5t 2 .

Då är lösningen på jämförelsen modulo 25 x=±(1+5(1+5 t 2))=±(6+25 t 2). Låt oss ersätta den resulterande lösningen i jämförelse modulo 5 3 =125:

x 2 ≡86 (mod 125)

(6+25t 2) 2 ≡86 (mod 125)

36+12·25 t 2 +625t 2 2 ≡86 (mod 125)

12·25 t 2 ≡50 (mod 125)

12t 2 ≡2 (mod 5)

2t 2 ≡2 (mod 5)

t 2 ≡1 (mod 5), eller t 2 =1+5t 3 .

Då är lösningen på jämförelsen modulo 125 x=±(6+25(1+5 t 3))=±(31+125 t 3).

Svar: x≡±31 (mod 125).

Låt oss nu överväga en jämförelse av formen x 2 ≡a(mod 2a). En sådan jämförelse har inte alltid två lösningar. För en sådan modul är följande fall möjliga:

1) a=1. Då har jämförelsen en lösning först när a≡1(mod 2), och lösningen är x≡1 (mod 2) (en lösning).

2) a=2. Jämförelse har lösningar bara när a≡1(mod 4), och lösningen är x≡±1 (mod 4) (två lösningar).

3) a≥3. Jämförelse har lösningar bara när a≡1(mod 8), och det kommer att finnas fyra sådana lösningar. Jämförelse x 2 ≡a(mod 2 α) för α≥3 löses på samma sätt som jämförelser av formen x 2 ≡a(mod sidα), endast lösningar modulo 8 fungerar som den initiala lösningen: x≡±1(mod 8) och x≡±3 (mod 8). De ska jämföras modulo 16, sedan modulo 32, etc. upp till modulo 2 α.

Exempel:

Lös jämförelse x 2 ≡33 (mod 64)

64=2 6 . Låt oss kontrollera om den ursprungliga jämförelsen har en lösning. 33≡1(mod 8), vilket innebär att jämförelsen har 4 lösningar.

Modulo 8 dessa lösningar kommer att vara: x≡±1(mod 8) och x≡±3(mod 8), som kan representeras som x=±(1+4 t 1). Låt oss ersätta detta uttryck med jämförelse modulo 16

x 2 ≡33 (mod 16)

(1+4t 1) 2 ≡1 (mod 16)

1+8t 1 +16t 1 2 ≡1 (mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Då kommer lösningen att ta formen x=±(1+4 t 1)=±(1+4(0+2 t 2))=±(1+8 t 2). Låt oss ersätta den resulterande lösningen med jämförelse modulo 32:

x 2 ≡33 (mod 32)

(1+8t 2) 2 ≡1 (mod 32)

1+16t 2 +64t 2 2 ≡1 (mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Då kommer lösningen att ta formen x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Låt oss ersätta den resulterande lösningen med jämförelse modulo 64:

x 2 ≡33 (mod 64)

(1+16t 3) 2 ≡33 (mod 64)

1+32t 3 +256t 3 2 ≡33 (mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Då kommer lösningen att ta formen x=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t 4). Så, modulo 64, den ursprungliga jämförelsen har fyra lösningar: x≡±17(mod 64)i x≡±49 (mod 64).

Låt oss nu titta på en allmän jämförelse: x 2 ≡a(mod m), (a,m)=1, - kanonisk expansion av modulen m. Enligt satsen från paragraf 4 i §4 är denna jämförelse ekvivalent med systemet

Om varje jämförelse av detta system är lösbart, så är hela systemet lösbart. Efter att ha hittat lösningen på varje jämförelse av detta system, kommer vi att få ett system av jämförelser av första graden, och lösa vilket med hjälp av den kinesiska restsatsen, vi kommer att få en lösning på den ursprungliga jämförelsen. Dessutom är antalet olika lösningar till den ursprungliga jämförelsen (om den är lösbar) 2 k, om α=1, 2 k+1 om α=2, 2 k+2 om α≥3.

Exempel:

Lös jämförelse x 2 ≡4 (mod 21).

Vid n ger de samma rester.

Motsvarande formuleringar: a och b jämförbar i modul n om deras skillnad a - bär delbart med n, eller om a kan representeras som a = b + kn , Var k- något heltal. Till exempel: 32 och −10 är jämförbara modulo 7, eftersom

Påståendet "a och b är jämförbara modulo n" skrivs som:

Modulo likhetsegenskaper

Modulo jämförelserelationen har egenskaperna

Vilka två heltal som helst a Och b jämförbar modulo 1.

För siffrorna a Och b var jämförbara i modul n, är det nödvändigt och tillräckligt att deras skillnad är delbar med n.

Om siffrorna och är parvis jämförbara i modul n, sedan deras summor och , samt produkterna och är också jämförbara i modul n.

Om siffrorna a Och b jämförbar i modul n, sedan deras grader a k Och b kär också jämförbara i modul n under någon naturlig k.

Om siffrorna a Och b jämförbar i modul n, Och n delat med m, Den där a Och b jämförbar i modul m.

För siffrorna a Och b var jämförbara i modul n, presenterad i form av dess kanoniska uppdelning i enkla faktorer sid i

nödvändigt och tillräckligt för att

Jämförelserelationen är en ekvivalensrelation och har många av egenskaperna hos vanliga jämlikheter. Till exempel kan de adderas och multipliceras: if

Jämförelser kan dock generellt sett inte delas med varandra eller med andra tal. Exempel: , men om vi minskar med 2 får vi en felaktig jämförelse: . Förkortningsreglerna för jämförelser är följande.

Du kan inte heller utföra operationer på jämförelser om deras moduler inte matchar.

Övriga egenskaper:

Relaterade definitioner

Avdragsklasser

Uppsättningen av alla siffror jämförbara med a modulo n kallad avdragsklass a modulo n , och betecknas vanligtvis [ a] n eller . Således är jämförelsen ekvivalent med jämlikheten mellan restklasser [a] n = [b] n .

Sedan modulo jämförelse när en ekvivalensrelation på mängden heltal, då restklasserna modulo n representerar ekvivalensklasser; deras antal är lika n. Uppsättningen av alla restklasser modulo n betecknas med eller.

Operationerna för addition och multiplikation genom att inducera motsvarande operationer på mängden:

[a] n + [b] n = [a + b] n

Med avseende på dessa operationer är uppsättningen en ändlig ring, och om n enkelt - ändligt fält.

Avdragssystem

Restsystemet låter dig utföra aritmetiska operationer på en ändlig uppsättning tal utan att gå över dess gränser. Fullständigt system med avdrag modulo n är en uppsättning av n heltal som är ojämförliga modulo n. Vanligtvis tas de minsta icke-negativa resterna som ett komplett system av rester modulo n

0,1,...,n − 1

eller de absolut minsta avdragen som består av siffror

,

vid udda n och siffror

vid jämnt n .

Lösa jämförelser

Jämförelser av första graden

Inom talteori, kryptografi och andra vetenskapsområden uppstår ofta problemet med att hitta lösningar på första gradens jämförelser av formen:

Att lösa en sådan jämförelse börjar med att beräkna gcd (a, m)=d. I det här fallet är 2 fall möjliga:

• Om b inte en multipel d, då har jämförelsen inga lösningar.
• Om b flera olika d, då har jämförelsen en unik lösning modulo m / d, eller, vad är samma, d modulo lösningar m. I det här fallet, som ett resultat av att minska den ursprungliga jämförelsen med d jämförelsen är:

Var a 1 = a / d , b 1 = b / d Och m 1 = m / d är heltal, och a 1 och m 1 är relativt prime. Därför numret a 1 kan inverteras modulo m 1, det vill säga hitta ett sådant nummer c, det (med andra ord, ). Nu hittas lösningen genom att multiplicera den resulterande jämförelsen med c:

Praktisk beräkning av värde c kan implementeras på olika sätt: med Eulers sats, Euklids algoritm, teorin om fortsatta bråk (se algoritm) etc. I synnerhet låter Eulers sats dig skriva ner värdet c som:

Exempel

Som jämförelse har vi d= 2, så modulo 22 har jämförelsen två lösningar. Låt oss ersätta 26 med 4, jämförbart med modulo 22, och sedan minska alla 3 siffror med 2:

Eftersom 2 är coprime till modulo 11 kan vi reducera vänster och höger sida med 2. Som ett resultat får vi en lösning modulo 11: , motsvarande två lösningar modulo 22: .

Jämförelser av andra graden

Att lösa jämförelser av andra graden handlar om att ta reda på om ett givet tal är en kvadratisk rest (med hjälp av kvadratisk reciprocitetslagen) och sedan beräkna kvadratroten modulo.

Berättelse

Den kinesiska restsatsen, känd i många århundraden, säger (i modernt matematiskt språk) att restringen modulo produkten av flera samprimtal är

Matematikprojekt om ämnet

"Jämförelser modulo"

Zaripova Aisylu

Sovetsky-distriktet i Kazan

MBOU "Secondary School nr 166", 7a årskurs

Vetenskaplig handledare: Antonova N.A.

Innehållsförteckning

Introduktion_________________________________________________________________3

Vad är jämförelser____________________________________________4

1. Begreppet jämförelser modulo__________________________4

   Historien om framväxten av begreppet jämförelser modulo_____4

   Jämförelsers egenskaper_________________________________________4

Tillämpa jämförelser på problemlösning______________________________6

1. Den enklaste användningen av modulo-jämförelser är att bestämma delbarheten av tal____________________6

   En jämförelseuppgift__________________________________________8

   Användningen av modulo-jämförelser i yrkesverksamhet__________________________________________________9

Slutsats_________________________________________________10

Lista över begagnad litteratur_______________________________________11

Introduktion.

Ämne: Modulo jämförelser.

Problem: Många elever ställs inför problem när de förbereder sig för olympiader, vars lösning är baserad på kunskap om rester från att dividera heltal med ett naturligt tal. Vi var intresserade av den här typen av problem och möjliga metoder för att lösa dem. Det visar sig att de kan lösas med hjälp av modulo-jämförelser.

Mål: Ta reda på essensen av modulo-jämförelser, de viktigaste metoderna för att arbeta med modulo-jämförelser.

Mål: hitta teoretiskt material om detta ämne, överväga problem som löses med modulo-jämförelser, visa de vanligaste metoderna för att lösa sådana problem, dra slutsatser.

Studieobjekt: talteori.

Forskningsämne: teori om modulo-jämförelser.

Arbetet relaterar till teoretisk forskning och kan användas som förberedelse inför matematikolympiader. Dess innehåll avslöjar de grundläggande begreppen för modulo-jämförelser och deras huvudsakliga egenskaper, och ger exempel på att lösa problem i detta ämne.

jag . Vad är jämförelser?

1. Konceptet med modulo jämförelser.

Talen och sägs vara jämförbara i modul om de är delbara med, med andra ord, a och b har samma rester när de divideras med.

Beteckning

Exempel:

12 och 32 är jämförbara modulo 5, eftersom 12 när de divideras med 5 har en rest av 2 och 32 när de divideras med 2 har en rest av 2. Det är skrivet12 ;

101 och 17 är jämförbara modulo 21;

1. Historien om uppkomsten av begreppet modulo jämförelser.

Teorin om delbarhet skapades till stor del av Euler. Definitionen av jämförelse formulerades i boken av K.F. Gauss "Arithmetic Studies". Detta arbete, skrivet på latin, började tryckas 1797, men boken publicerades först 1801 på grund av att tryckprocessen vid den tiden var extremt arbetskrävande och långdragen. Den första delen av Gauss bok heter: "Om jämförelsen av siffror." Det var Gauss som föreslog symboliken för modulo-jämförelser som har blivit etablerad inom matematiken.

1. Jämförelsers egenskaper.

Om

Bevis:

1. Lägger vi den andra till den första jämlikheten får vi

är summan av två heltal, är därför ett heltal.

Om vi ​​subtraherar den andra från den första likheten får vi

detta är skillnaden mellan två heltal, vilket betyder att det därför är ett heltal.

Tänk på uttrycket:

Detta är skillnaden mellan produkter av heltal, vilket betyder att det därför är ett heltal.

Detta är en följd av jämförelsens tredje egenskap.

Q.E.D.

5) Om.

Bevis: Låt oss hitta summan av dessa två uttryck:

är summan av två heltal, därför är det ett heltal, därför .

Q.E.D.

6) Om är ett heltal, alltså

Bevis: , varsid– ett heltal, multiplicera denna likhet med, vi får: . Eftersom det är en produkt av heltal, det är vad som behövde bevisas.

7) Om

Bevis: resonemanget liknar egenskapsbeviset 6.

8) Om - coprimtal alltså

Bevis: , dividera detta uttryck med, får vi: - samprimtal, vilket betyder att de är delbara med ett heltal, dvs. =. Och detta betyder att det som behövde bevisas.

II . Tillämpa jämförelser på problemlösning.

2.1. Den enklaste användningen av modulo-jämförelser är att bestämma delbarheten av tal.

Exempel. Hitta resten av 2 2009 klockan 7.

Lösning: Tänk på krafterna i 2:

genom att höja jämförelsen till potensen 668 och multiplicera med får vi: .

Svar: 4.

Exempel. Bevisa att 7+7 2 +7 3 +…+7 4 n är delbart med 100 för någonnfrån en uppsättning heltal.

Lösning: Överväg jämförelser

etc. Resteras cykliska karaktär förklaras av reglerna för att multiplicera tal i en kolumn. Lägger vi ihop de fyra första jämförelserna får vi:

Detta innebär att detta belopp divideras med 100 utan rest. På liknande sätt, om vi lägger till följande jämförelser om fyra, får vi att varje sådan summa är delbar med 100 utan en rest. Det betyder att hela summan består av 4ntermer är delbart med 100 utan rest. Q.E.D.

Exempel. Bestäm till vilket värdenuttrycket är delbart med 19 utan rest.

Lösning: .

Låt oss multiplicera denna jämförelse med 20. Vi får.

Låt oss då lägga ihop jämförelserna. . Således är den högra sidan av jämförelsen alltid delbar med 19 för alla naturliga taln, vilket betyder att det ursprungliga uttrycket är delbart med 19 med naturligtn.

Svar n – vilket naturligt tal som helst.

Exempel. Vilken siffra slutar numret med?

Lösning. För att lösa detta problem kommer vi bara att övervaka den sista siffran. Tänk på krafterna i siffran 14:

Man kan märka att om exponenten är udda slutar gradens värde på 4, och om exponenten är jämn slutar den på 6. Då slutar den på 6, d.v.s. är ett jämnt tal. Så det slutar i 6.

Svar 6.

2.2. En jämförelseuppgift.

Artikeln av N. Vilenkin "Jämförelser och klasser av rester" presenterar ett problem som löstes av den berömda engelske fysikern Dirac under hans studentår.

Det finns också en kort lösning på detta problem med modulo-jämförelser. Men vi stötte på ett antal liknande problem. Till exempel.

En förbipasserande hittade en hög med äpplen nära ett träd som en apa satt på. Efter att ha räknat dem insåg han att om 1 äpple ges till apan, kommer antalet återstående äpplen att delas in i n spårlöst. Efter att ha gett det extra äpplet till apan tog han 1/ n återstående äpplen och vänster. Senare närmade sig nästa förbipasserande högen, sedan nästa osv. Varje efterföljande förbipasserande, efter att ha räknat äpplena, märkte att deras antal delat med n ger resten 1 och efter att ha gett det extra äpplet till apan tog han 1 för sig själv n de återstående äpplena och gick vidare. Efter att den sista gick, n den förbipasserande dividerades antalet äpplen som fanns kvar i högen med n spårlöst. Hur många äpplen låg i högen först?

Genom att genomföra samma resonemang som Dirac fick vi en generell formel för att lösa en klass av liknande problem: , därn- naturligt nummer.

2.3. Tillämpning av moduljämförelser i yrkesverksamhet.

Jämförelseteori tillämpas på kodningsteori, så alla som väljer ett yrke relaterat till datorer kommer att studera, och eventuellt tillämpa jämförelser i sin yrkesverksamhet. Till exempel används ett antal talteoretiska koncept, inklusive modulo-jämförelser, för att utveckla krypteringsalgoritmer för publika nyckel.

Slutsats.

Arbetet beskriver de grundläggande begreppen och egenskaperna för modulo-jämförelser och illustrerar användningen av modulo-jämförelser med exempel. Materialet kan användas som förberedelse för olympiader i matematik och Unified State Exam.

Den givna referenslistan gör det möjligt att vid behov överväga några mer komplexa aspekter av teorin om modulo-jämförelser och dess tillämpningar.

Lista över begagnad litteratur.

Alfutova N.B. Algebra och talteori./N.B.Alfutova, A.V.Ustinov. M.:MCNMO, 2002, 466 sid.

Bukhshtab A.A. Talteori. /A.A.Bukhshtab. M.: Utbildning, 1960.

Vilenkin N. Jämförelser och klasser av rester./N. Vilenkin.//Quantum. – 1978.- 10.

Fedorova N.E. Studie av algebra och matematisk analys. Årskurs 10.http:// www. prosv. ru/ e-böcker/ Fedorova_ Algebra_10 kl/1/ xht

ru. wikipedia. org/ wiki/Comparison_modulo.

En förstagradsjämförelse med en okänd har formen:

f(x) 0 (mod m); f(X) = Åh + och n. (1)

Lös jämförelse- betyder att hitta alla värden på x som uppfyller det. Två jämförelser som uppfyller samma värden på x kallas likvärdig.

Om jämförelse (1) uppfylls av någon x = x 1, sedan (enligt 49) alla siffror jämförbara med x 1, modulo m: x x 1 (mod m). Hela denna klass av siffror anses vara en lösning. Med en sådan överenskommelse kan följande slutsats dras.

66.C inriktning (1) kommer att ha lika många lösningar som antalet rester av hela systemet som uppfyller det.

Exempel. Jämförelse

6x– 4 0 (mod 8)

Bland siffrorna 0, 1,2, 3, 4, 5, 6, 7 uppfyller två siffror hela systemet av rester modulo 8: X= 2 och X= 6. Därför har denna jämförelse två lösningar:

x 2 (mod 8), X 6 (mod 8).

Jämförelse av första graden genom att flytta den fria termen (med motsatt tecken) till höger kan reduceras till formen

yxa b(mod m). (2)

Tänk på en jämförelse som uppfyller villkoret ( A, m) = 1.

Enligt 66 har vår jämförelse lika många lösningar som det finns rester av hela systemet som uppfyller det. Men när x går igenom hela systemet av modulo-rester T, Den där Åh går igenom hela systemet med avdrag (av 60). Därför för ett och bara ett värde X, hämtat från hela systemet, Åh kommer att kunna jämföras med b. Så,

67. När (a, m) = 1 jämförelseax b(mod m)har en lösning.

Låt nu ( a, m) = d> 1. Sedan, för att jämförelse (2) ska ha lösningar, är det nödvändigt (av 55) att b delat med d, annars är jämförelse (2) omöjlig för något heltal x . Förutsatt därför b multiplar d, låt oss sätta a = a 1 d, b = b 1 d, m = m 1 d. Då kommer jämförelse (2) att motsvara detta (förkortas med d): a 1 x b 1 (mod m), där redan ( A 1 , m 1) = 1, och därför kommer den att ha en lösning modulo m 1 . Låta X 1 – den minsta icke-negativa resten av denna lösning modulo m 1 , då är alla tal x , bildar denna lösning finns i formuläret

x x 1 (mod m 1). (3)

Modulo m, tal (3) bildar inte en lösning, utan fler, exakt lika många lösningar som det finns tal (3) i serien 0, 1, 2, ..., m – 1 minst icke-negativa modulo-rester m. Men följande siffror (3) kommer att falla här:

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

de där. Total d nummer (3); därför jämförelse (2) har d beslut.

Vi får satsen:

68. Låt (a, m) = d. Jämförelse ax b ( mod m) är omöjligt om b inte är delbart med d. När b är en multipel av d, har jämförelsen d-lösningar.

69. En metod för att lösa jämförelser av första graden, baserad på teorin om fortsatta bråk:

Expandera till en fortsatt bråkdel av relationen m:a,

och tittar på de två sista matchande bråken:

enligt egenskaperna hos fortsatta fraktioner (enligt 30 ) vi har

Så jämförelsen har en lösning

att hitta, vilket räcker för att beräkna Pn– 1 enligt den metod som anges i 30.

Exempel. Låt oss lösa jämförelsen

111x= 75 (mod 321). (4)

Här (111, 321) = 3, och 75 är en multipel av 3. Därför har jämförelsen tre lösningar.

Om vi ​​dividerar båda sidor av jämförelsen och modulen med 3, får vi jämförelsen

37x= 25 (mod 107), (5)

som vi först måste lösa. Vi har

q
P 3

Så i det här fallet n = 4, P n – 1 = 26, b= 25, och vi har en lösning till jämförelse (5) i formuläret

x–26 ∙ 25 99 (mod 107).

Därför presenteras lösningarna till jämförelse (4) enligt följande:

X 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

Xº99; 206; 313 (mod 321).

Beräkning av det inversa elementet med en given modulo

70.Om talen är heltal a Och när coprime, så finns det ett nummer a′, som uppfyller jämförelsen a ∙ a′ ≡ 1 (mod n). siffra a′ kallad multiplikativ invers av en modulo n och notationen som används för det är en- 1 (mod n).

Beräkningen av ömsesidiga storheter modulo ett visst värde kan utföras genom att lösa en jämförelse av första graden med en okänd, i vilken x nummer accepterat a′.

För att hitta en jämförelselösning

a∙x≡ 1(mod m),

Var ( a,m)= 1,

du kan använda Euklids algoritm (69) eller Fermat-Eulers sats, som säger att om ( a,m) = 1, då

a φ( m) ≡ 1(mod m).

x ≡ a φ( m)–1 (mod m).

Grupper och deras fastigheter

Grupper är en av de taxonomiska klasser som används vid klassificeringen av matematiska strukturer med gemensamma karakteristiska egenskaper. Grupper har två komponenter: ett gäng (G) Och operationer() definieras i denna uppsättning.

Begreppen mängd, element och medlemskap är de grundläggande odefinierade begreppen i modern matematik. Varje uppsättning definieras av de element som ingår i den (som i sin tur också kan vara uppsättningar). Således säger vi att en mängd är definierad eller given om vi för något element kan säga om den tillhör denna mängd eller inte.

För två set A, B uppgifter B A, B A, B∩ A, B A, B \ A, A × B respektive menar det Bär en delmängd av uppsättningen A(dvs alla element från B ingår också i A, till exempel, mängden naturliga tal ingår i uppsättningen av reella tal; dessutom alltid A A), Bär en riktig delmängd av uppsättningen A(de där. B A Och B ≠ A), skärningspunkt mellan många B Och A(dvs alla sådana element som ligger samtidigt i A, och i B, till exempel, skärningspunkten mellan heltal och positiva reella tal är mängden naturliga tal), föreningen av mängder B Och A(dvs en uppsättning som består av element som ligger antingen i A, Antingen i B), ställ in skillnaden B Och A(dvs uppsättningen av element som ligger i B, men lägg dig inte i A), kartesisk produkt av uppsättningar A Och B(dvs. en uppsättning par av formen ( a, b), Var a A, b B). Via | A| uppsättningens kraft anges alltid A, dvs. antal element i uppsättningen A.

En operation är en regel enligt vilken två godtyckliga element i en mängd G(a Och b) matchas med det tredje elementet från G: a b.

Många element G med en operation kallas grupp, om följande villkor är uppfyllda.