doel

Vergelijkingen van de eerste graad oplossen. Vergelijkingen en hun toepassingen oplossen Waarom moeten we getallen vergelijken modulo

19.06.2022

Inhoud.

Invoering

§een. Modulo vergelijking

§2. Vergelijkingseigenschappen

Module-onafhankelijke vergelijkingseigenschappen
Modulespecifieke vergelijkingseigenschappen

§3. aftreksysteem

Compleet systeem van inhoudingen
Het verlaagde systeem van aftrekposten

vier. Stelling van Euler en Fermat

Euler-functie
Stelling van Euler en Fermat

Hoofdstuk 2. Theorie van vergelijkingen met een variabele

§een. Basisconcepten met betrekking tot het nemen van vergelijkingen

De wortels van vergelijkingen
Gelijkwaardigheid van vergelijkingen
Stelling van Wilson

§2. Vergelijkingen van de eerste graad en hun oplossingen

Selectie methode:
Euler-methoden
De algoritmemethode van Euclides
Voortgezette breuk methode

§3. Vergelijkingssystemen van de 1e graad met een onbekende

vier. Verdeling van vergelijkingen van hogere machten

§5. Primitieve wortels en indices

Aftrek klasse bestelling
Primitieve wortels modulo prime
Indexen modulo prime

Hoofdstuk 3 Toepassing van de theorie van vergelijkingen

§een. Tekenen van deelbaarheid

§2. De resultaten van rekenkundige bewerkingen controleren

§3. Een gewone breuk converteren naar een eindige

decimale fractie

Conclusie

Literatuur

Invoering

In ons leven hebben we vaak te maken met gehele getallen en daarmee samenhangende taken. In dit proefschrift beschouw ik de theorie van vergelijking van gehele getallen.

Twee gehele getallen waarvan het verschil een veelvoud is van een bepaald natuurlijk getal m worden vergelijkbare modulo . genoemd m.

Het woord "module" komt van het Latijnse modulus, wat in het Russisch "maat", "waarde" betekent.

De uitspraak "a is congruent met b modulo m" wordt meestal geschreven als ab (mod m) en wordt vergelijking genoemd.

De definitie van vergelijking is geformuleerd in het boek van K. Gauss "Aritmetic Research". Dit werk, geschreven in het Latijn, werd in 1797 gedrukt, maar het boek werd pas in 1801 gepubliceerd vanwege het feit dat het drukproces in die tijd buitengewoon arbeidsintensief en langdurig was. Het eerste deel van Gauss' boek heet "Over de vergelijking van getallen in het algemeen".

Vergelijkingen zijn erg handig om te gebruiken in die gevallen waarin het voldoende is om getallen te kennen in elk onderzoek tot veelvouden van een bepaald getal.

Als we bijvoorbeeld geïnteresseerd zijn in op welk cijfer de derde macht van een geheel getal a eindigt, dan hoeven we alleen a te kennen tot veelvouden van 10 en kunnen we vergelijkingen modulo 10 gebruiken.

Het doel van dit werk is de theorie van vergelijkingen te bestuderen en de belangrijkste methoden voor het oplossen van vergelijkingen met onbekenden te bestuderen, evenals de toepassing van de vergelijkingstheorie op schoolwiskunde te bestuderen.

Het proefschrift bestaat uit drie hoofdstukken, waarbij elk hoofdstuk is onderverdeeld in paragrafen en paragrafen in paragrafen.

Het eerste hoofdstuk behandelt algemene vragen van de theorie van vergelijkingen. Hier beschouwen we het concept van modulo-vergelijking, de eigenschappen van vergelijkingen, het volledige en gereduceerde systeem van residuen, de Euler-functie, de stelling van Euler en Fermat.

Het tweede hoofdstuk is gewijd aan de theorie van vergelijkingen met het onbekende. Het schetst de basisconcepten met betrekking tot het oplossen van vergelijkingen, beschouwt methoden voor het oplossen van vergelijkingen van de eerste graad (selectiemethode, Euler's methode, Euclid's algoritmemethode, de methode van kettingbreuken, met behulp van indices), systemen van vergelijkingen van de eerste graad met een onbekende, vergelijkingen van hogere graden, enz. .

Het derde hoofdstuk bevat enkele toepassingen van getaltheorie op schoolwiskunde. De tekenen van deelbaarheid, verificatie van de resultaten van acties, conversie van gewone breuken in systematische decimale breuken worden overwogen.

De presentatie van het theoretische materiaal gaat vergezeld van een groot aantal voorbeelden die de essentie van de geïntroduceerde concepten en definities onthullen.

Hoofdstuk 1. Algemene vragen van de theorie van vergelijkingen

§een. Modulo vergelijking

Laat z-ring van gehele getallen, m-vast geheel getal en m z-verzameling van alle gehele getallen die deelbaar zijn door m.

Definitie 1. Twee gehele getallen a en b zijn congruent modulo m als m a-b deelt.

Als de getallen a en b vergelijkbaar zijn modulo m, schrijf dan a b (mod m).

Voorwaarde a b (mod m) betekent dat a-b deelbaar is door m.

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

We definiëren dat de vergelijkbaarheidsrelatie modulo m samenvalt met de vergelijkbaarheidsrelatie modulo (-m) (deelbaarheid door m is gelijk aan deelbaarheid door –m). Daarom kunnen we, zonder verlies van algemeenheid, aannemen dat m>0.

Voorbeelden.

Stelling. (teken van vergelijkbaarheid van geestgetallen modulo m): Twee gehele getallen a en b zijn vergelijkbaar modulo m als en slechts dan als a en b dezelfde rest hebben als ze worden gedeeld door m.

Een bewijs.

Laat de resten bij het delen van a en b door m gelijk zijn, dat wil zeggen, a=mq₁+r,(1)

B=mq₂+r, (2)

Waar 0≤r≥m.

Trek (2) van (1) af, we krijgen a-b= m(q₁- q₂), d.w.z. a-b m of een b (mod m).

Omgekeerd, laat een b (mod m). Dit betekent a-b m of a-b=mt, t z (3)

Deel b door m; we krijgen b=mq+r in (3), we hebben a=m(q+t)+r, dat wil zeggen, het delen van a door m geeft dezelfde rest als het delen van b door m.

Voorbeelden.

5=4 (-2)+3

23=4 5+3

24=3 8+0

10=3 3+1

Definitie 2. Twee of meer getallen die dezelfde rest geven als ze worden gedeeld door m, worden equidistante of vergelijkbare modulo m genoemd.

Voorbeelden.

We hebben: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², en (- m²) is deelbaar door m => onze vergelijking is correct.

Bewijs dat de volgende vergelijkingen onjuist zijn:

Als de getallen vergelijkbaar zijn modulo m, dan hebben ze dezelfde ggd erbij.

We hebben: 4=2 2, 10=2 5, 25=5 5

ggd(4,10) = 2, ggd(25,10) = 5, dus onze vergelijking is fout.

§2. Vergelijkingseigenschappen

Module-onafhankelijke vergelijkingseigenschappen.

Veel eigenschappen van vergelijkingen zijn vergelijkbaar met die van gelijkheden.

a) reflexiviteit: aa (mod m) (elk geheel getal a is vergelijkbaar met zichzelf modulo m);

C) symmetrie: als a b (mod m), dan b a (mod m);

C) transitiviteit: als a b (mod m), en b met (mod m), dan a met (mod m).

Een bewijs.

Op voorwaarde m/(a-b) en m/ (c-d). Dus m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b + d (mod m).

Voorbeelden.

Vind de rest bij het delen om 13.

Oplossing: -1 (mod 13) en 1 (mod 13), dan (-1)+1 0 (mod 13), dat wil zeggen, de rest van de deling met 13 is 0.

a-c b-d (mod m).

Een bewijs.

Op voorwaarde m/(a-b) en m/(c-d). Daarom, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

(een gevolg van eigenschappen 1, 2, 3). U kunt hetzelfde gehele getal aan beide delen van de vergelijking toevoegen.

Een bewijs.

laat een b (mod m) en k is een willekeurig geheel getal. Door de eigenschap van reflexiviteit

k=k (mod m), en volgens eigenschappen 2 en 3 hebben we a+k b + k (mod m).

a c d (mod m).

Een bewijs.

Op voorwaarde, a-b є mz, c-d є mz. Vandaar a c-b d = (a c - b c)+(b c- b d)=(a-b) c+b (c-d) є mz, d.w.z. a c d (mod m).

Gevolg. Beide delen van de vergelijking kunnen worden verheven tot dezelfde gehele niet-negatieve macht: als ab (mod m) en s is een niet-negatief geheel getal, dan is a sbs (mod m).

Voorbeelden.

Oplossing: uiteraard 13 1 (mod 3)

2-1 (mod. 3)

5 -1 (mod 3), dan

- 1-1 0 (mod 13)

Antwoorden: de gewenste rest is nul en A is deelbaar door 3.

Oplossing:

Laten we bewijzen dat 1+ 0(mod13) of 1+ 0(mod 13)

1+ =1+ 1+ =

Aangezien 27 1 is (mod 13), volgt hieruit dat 1+1+1 3+1 9 (mod 13).

h.t.d.

3. Vind de rest bij het delen door de rest van een getal op 24.

We hebben: 1 (mod 24), dus

1 (mod 24)

Als we 55 aan beide delen van de vergelijking toevoegen, krijgen we:

(model 24).

We hebben: (mod 24), dus

(mod 24) voor elke k N.

Vervolgens (model 24). sinds (-8)16(mod 24), de gewenste rest is 16.

Beide delen van de vergelijking kunnen met hetzelfde gehele getal worden vermenigvuldigd.

2. Eigenschappen van vergelijkingen afhankelijk van de module.

Een bewijs.

Aangezien a b (mod t), dan (a - b) t. En aangezien t n , dan vanwege de transitiviteit van de deelbaarheidsrelatie(a - b n), dat wil zeggen, a b (mod n).

Voorbeeld.

Vind de rest na 196 te delen door 7.

Oplossing:

Wetende dat 196= , we kunnen 196 . schrijven(model 14). Laten we de vorige eigenschap gebruiken, 14 7, we krijgen 196 (mod 7), dat wil zeggen 196 7.

Beide delen van de vergelijking en de modulus kunnen worden vermenigvuldigd met hetzelfde positieve gehele getal.

Een bewijs.

Laat een b (mod m ) en c is een positief geheel getal. Dan a-b = mt en ac-bc=mtc, of ac bc (mod mc).

Voorbeeld.

Controleer of de waarde van een uitdrukking is geheel getal.

Oplossing:

Laten we breuken weergeven in de vorm van vergelijkingen: 4(mod. 3)

1 (model 9)

31 (mod. 27)

We voegen deze vergelijkingen term voor term toe (eigenschap 2), we krijgen 124(mod 27) We zien dat 124 geen geheel getal is dat deelbaar is door 27, vandaar de waarde van de uitdrukkingis ook geen geheel getal.

Beide delen van de vergelijking kunnen worden gedeeld door hun gemeenschappelijke factor als deze relatief priem is ten opzichte van de modulus.

Een bewijs.

als het kan cb (mod m), d.w.z. m/c(a-b) en nummer Met coprime tot m, (c,m)=1, dan deelt m a-b. Vervolgens, a b (mod t ).

Voorbeeld.

60 9 (mod 17), na het delen van beide delen van de vergelijking door 3 krijgen we:

20 (model 17).

In het algemeen is het onmogelijk om beide delen van de vergelijking te delen door een getal dat niet gelijk is aan de modulus, omdat na deling getallen kunnen worden verkregen die onvergelijkbaar zijn in deze modulus.

Voorbeeld.

8 (mod 4) maar 2 (mod 4).

Beide delen van de vergelijking en de modulus kunnen worden gedeeld door hun gemeenschappelijke deler.

Een bewijs.

Als ka kb (mod km), dan is k (a-b) deelbaar door km. Daarom is a-b deelbaar door m, dat wil zeggen a b (mod t ).

Een bewijs.

Zij P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n . Op voorwaarde a b (mod t), dan

a k b k (mod m) voor k = 0, 1, 2, …,n. Beide delen van elk van de resulterende n + 1 vergelijkingen vermenigvuldigen met c n-k , we krijgen:

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

Als we de laatste vergelijkingen toevoegen, krijgen we: P (a) P(b) (mod m). Als a (mod m) en c i d i (mod m), 0 ≤ i ≤ n, dan

(mod m). Dus in congruentie modulo m kunnen individuele termen en factoren worden vervangen door getallen congruent modulo m.

Tegelijkertijd moet er op worden gelet dat de exponenten die in vergelijkingen worden aangetroffen niet op deze manier kunnen worden vervangen: van

a n c(mod m) en n k(mod m) betekent niet dat a k met (mod m).

Woning 11 kent een aantal belangrijke toepassingen. Het kan met name worden gebruikt om een theoretische onderbouwing te geven van de tekens van deelbaarheid. Ter illustratie geven we als voorbeeld de afleiding van de test voor deelbaarheid door 3.

Voorbeeld.

Elk natuurlijk getal N kan worden weergegeven als een systematisch getal: N = a 0 10 n + een 1 10 n-1 + ... + een n-1 10 + een n .

Beschouw de polynoom f (x) = a 0 x n + a 1 x n-1 + ... + een n-1 x+a n . Omdat

10 1 (mod 3), dan door eigenschap 10 f (10) f(1) (mod 3) of

N = een 0 10 n + een 1 10 n-1 + ... + een n-1 10 + een n een 1 + een 2 +…+ een n-1 + een n (mod 3), d.w.z. om N deelbaar te maken door 3, is het noodzakelijk en voldoende dat de som van de cijfers van dit getal deelbaar is door 3.

§3. aftreksystemen

Compleet facturatiesysteem.

Equidistante getallen, of wat hetzelfde is, vergelijkbare modulo m, vormen een klasse van getallen modulo m.

Uit deze definitie volgt dat dezelfde rest r overeenkomt met alle getallen van de klasse, en we krijgen alle getallen van de klasse als we q dwingen door alle gehele getallen te lopen in de vorm mq + r.

Dienovereenkomstig hebben we met m verschillende waarden van r m klassen van getallen modulo m.

Elk nummer van een klasse wordt een residu modulo m genoemd met betrekking tot alle nummers van dezelfde klasse. Het residu verkregen bij q=0, gelijk aan de rest r, wordt het kleinste niet-negatieve residu genoemd.

Het residu ρ, de kleinste in absolute waarde, wordt het absoluut kleinste residu genoemd.

Vanzelfsprekend geldt voor r ρ=r; wanneer r> we hebben ρ=r-m; tenslotte, als m even is en r=, dan kan men voor ρ elk van de twee getallen nemen en -m= - .

We kiezen uit elke klasse van residuen modulo t door één nummer. Krijgen m gehele getallen: x 1 ,…, x m . De verzameling (x 1, ..., x t) heet compleet systeem van residuen modulo m.

Aangezien elke klasse een ontelbare reeks residuen bevat, is het mogelijk om een ontelbare reeks van verschillende complete systemen van residuen modulo m samen te stellen, die elk t inhoudingen.

Voorbeeld.

Stel verschillende complete systemen van residuen modulo . samen t = 5. We hebben klassen: 0, 1, 2, 3, 4.

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

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

Laten we verschillende volledige aftreksystemen maken, waarbij we van elke klasse één aftrek nemen:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

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

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

enz.

Meest gebruikt:

Compleet systeem van de minste niet-negatieve residuen: 0, 1, t -1 In bovenstaand voorbeeld: 0, 1, 2, 3, 4. Zo'n systeem van residu's is eenvoudig: je moet alle niet-negatieve resten opschrijven die het gevolg zijn van deling door m.
Compleet systeem van minst positieve residuen(de kleinste positieve aftrek wordt van elke klasse genomen):

1, 2, ...,m. In ons voorbeeld: 1, 2, 3, 4, 5.

Een compleet systeem van absoluut minimale residu's.In het geval van oneven m verschijnen de absoluut kleinste residuen naast elkaar.

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

en in het geval van een even m, een van de twee rijen

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

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

In het gegeven voorbeeld: -2, -1, 0, 1, 2.

Laten we nu eens kijken naar de belangrijkste eigenschappen van het volledige systeem van residuen.

Stelling 1 . Elke reeks m gehele getallen:

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

paarsgewijze onvergelijkbare modulo m, vormt een compleet systeem van residuen modulo m.

Een bewijs.

Elk van de nummers in de set (1) behoort tot een bepaalde klasse.
Twee willekeurige getallen x i en x j van (1) zijn onvergelijkbaar met elkaar, d.w.z. ze behoren tot verschillende klassen.
In totaal zijn er m-getallen in (1), d.w.z. net zoveel als er klassen modulo zijn t.

x 1, x 2,…, x t is een compleet systeem van residuen modulo m.

Stelling 2. Laat (a, m) = 1, b - willekeurig geheel getal; dan als x 1, x 2,…, x t -compleet systeem van residuen modulo m, dan de reeks getallen ax 1 + b, bijl 2 + b,…, bijl m + b is ook een compleet systeem van residuen modulo m.

Een bewijs.

Beschouwen

Bijl 1 + b, bijl 2 + b, ..., bijl m + b (2)

Elk van de nummers in de set (2) behoort tot een bepaalde klasse.
Twee willekeurige getallen ax i +b en ax j + b van (2) zijn onvergelijkbaar met elkaar, dat wil zeggen, ze behoren tot verschillende klassen.

Inderdaad, als er twee getallen in (2) zouden staan, zodanig dat

bijl i + b bijl j + b (mod m), (i = j), dan krijgen we bijl ik bijl j (mod m). Aangezien (a, t) = 1, dan kan de eigenschap van vergelijkingen beide delen van de vergelijking verminderen met a . We krijgen x i x j (mod m).

Op voorwaarde, x i x j (mod m) voor (i = j) , aangezien x 1 ,x 2 , ..., x m - volledig systeem van inhoudingen.

De reeks cijfers (2) bevat t getallen, dat wil zeggen, zoveel als er klassen modulo m zijn.

Dus, ax 1 + b, ax 2 + b, ..., ax m + b is het complete systeem van residuen modulo m.

Voorbeeld.

Laat m = 10, a = 3, b = 4.

Laten we een compleet systeem van residuen modulo 10 nemen, bijvoorbeeld: 0, 1, 2, ..., 9. Laten we getallen van de vorm samenstellen bijl + b. We krijgen: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. De resulterende reeks getallen is een compleet systeem van residuen modulo 10.

Het gegeven systeem van aftrekposten.

Laten we de volgende stelling bewijzen.

Stelling 1.

Getallen van dezelfde residuklasse modulo m hebben dezelfde grootste gemene deler met m: if een b (mod m), dan (a, m) = (b, m).

Een bewijs.

Laat een b (mod m). Dan a = b + mt, waar t z. Uit deze gelijkheid volgt dat (a, m) = (b, m).

Stel inderdaad de δ-gemeenschappelijke deler van a en m, dan a, m . Aangezien a = b + mt, dan b=a-mt, dus b. Daarom is elke gemeenschappelijke deler van a en m een gemeenschappelijke deler van m en b.

Omgekeerd, als m δ en b δ, dan is a = b + mt is deelbaar door δ, en daarom is elke gemeenschappelijke deler van m en b een gemeenschappelijke deler van a en m. De stelling is bewezen.

Definitie 1. Grootste gemene deler van een modulus t en elk nummer a van deze klasse van inhoudingen voor t de grootste gemene deler genoemd t en deze klasse van residuen.

Definitie 2. Residuklasse a modulo m heet coprime met modulo m als de grootste gemene deler een en t is gelijk aan 1 (dat wil zeggen, als m en elk nummer van a zijn coprime).

Voorbeeld.

laten we = 6. Restklasse 2 bestaat uit getallen (..., -10, -4, 2, 8, 14, ...). De grootste gemene deler van elk van deze getallen en module 6 is 2. Vandaar (2, 6) = 2. De grootste gemene deler van elk getal uit klasse 5 en module 6 is 1. Vandaar dat klasse 5 relatief priem is voor module 6.

Laten we kiezen uit elke klasse van residuen coprime met modulo m één getal. We krijgen een systeem van inhoudingen, dat deel uitmaakt van het volledige systeem van inhoudingen. Ze noemen haargereduceerd systeem van residuen modulo m.

Definitie 3. De reeks residuen modulo m, één voor één genomen uit elke coprime met t klasse van residuen modulo deze module wordt een gereduceerd residusysteem genoemd.

Definitie 3 impliceert een methode voor het verkrijgen van het gereduceerde systeem van residuen modulo t: het is noodzakelijk om een compleet systeem van residuen uit te schrijven en alle residuen die niet coprime zijn met m eruit te verwijderen. De resterende set inhoudingen is het gereduceerde systeem van inhoudingen. Er zijn natuurlijk een oneindig aantal gereduceerde systemen van residuen modulo m.

Als we het volledige stelsel van de minst niet-negatieve of absoluut minste residu's als begin nemen, dan krijgen we op de aangegeven manier het respectievelijk gereduceerde stelsel van de minst niet-negatieve of absoluut minste residu's modulo m.

Voorbeeld.

Als T = 8, dan 1, 3, 5, 7 - gereduceerd systeem van de minste niet-negatieve residuen, 1, 3, -3, -1- gereduceerd systeem van absoluut minimale residu's.

Stelling 2.

Laten het aantal klassen relatief priem tot m is gelijk aan k.Dan is elke verzameling van k gehele getallen

paarsgewijze onvergelijkbare modulo m en relatief priem met m, is een gereduceerd systeem van residuen modulo m.

Een bewijs

A) Elk nummer in de set (1) behoort tot een bepaalde klasse.

Alle getallen vanaf (1) zijn paarsgewijs onvergelijkbaar modulo t, dat wil zeggen, ze behoren tot verschillende klassen modulo m.
Elk nummer van (1) is coprime met t, dat wil zeggen, al deze getallen behoren tot verschillende klassen coprime met modulo m.
In totaal heeft (1) k getallen, dat wil zeggen, zoveel als het gereduceerde systeem van residuen modulo m zou moeten bevatten.

Daarom is de reeks getallen(1) - gereduceerd systeem van residuen modulo t.

vier. Euler-functie.

De stellingen van Euler en Fermat.

Euler-functie.

Geef aan met(t) het aantal klassen van residuen modulo m coprime met m, dat wil zeggen, het aantal elementen van het gereduceerde systeem van residuen modulo t. Functie φ (t) is numeriek. Ze noemen haarEuler-functie.

We kiezen als vertegenwoordigers van de residuklassen modulo t getallen 1, ... , t - 1, t Dan φ (t) is het aantal van dergelijke getallen co-prime met t Met andere woorden, φ (t) - het aantal positieve getallen dat m niet overschrijdt en relatief priem is tot m.

Voorbeelden.

laten we = 9. Het complete systeem van residuen modulo 9 bestaat uit de getallen 1, 2, 3, 4, 5, 6, 7, 8, 9. Hiervan zijn de getallen 1,2,4, 5, 7, 8 coprime vanaf 9. Dus aangezien het aantal van deze getallen 6 is, dan is φ (9) = 6.
Laat t = 12. Het complete systeem van residuen bestaat uit de nummers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Hiervan zijn de nummers 1, 5, 7, 11 coprime van 12. Vandaar,

φ(12) = 4.

bij t = 1, het complete systeem van residuen bestaat uit één klasse 1. De gemeenschappelijke natuurlijke deler van de getallen 1 en 1 is 1, (1, 1) = 1. Op basis hiervan stellen we φ(1) = 1.

Laten we verder gaan met de berekening van de Euler-functie.

1) Als m = p is een priemgetal, dan φ(p) = p-1.

Een bewijs.

Residuen 1, 2, ... , p- 1 en alleen zij zijn coprime met een priemgetal R. Daarom φ (p) = p - 1.

2) Als m = p k - macht van een priemgetal p, dan

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

Een bewijs.

Compleet systeem van residuen modulo t = p k bestaat uit de nummers 1,..., pk - 1, pk natuurlijke delers t zijn graden R. daarom het nummer akan een gemeenschappelijke deler hebben met m anders dan 1, alleen wanneeragedeeld doorR.Maar onder de nummers 1, ... , pk -1 op deRalleen getallen delenp, 2p, ... , p2 , ... Rtot, waarvan het nummer isRtot: p = pk-1. Vandaar, coprime mett = ptotrust uitRtot- Rk-1=pkl(p-1)nummers. Het is dus bewezen dat

φ (Rtot) = pk-1(r-1).

Stelling1.

De Euler-functie is multiplicatief, dat wil zeggen, voor de priemgetallen m en n geldt φ (mn) = φ(m) φ (n).

Een bewijs.

Aan de eerste vereiste in de definitie van een multiplicatieve functie wordt op een triviale manier voldaan: de Euler-functie is gedefinieerd voor alle natuurlijke getallen, en φ (1) = 1. Dat hoeven we alleen maar aan te tonen alssoort vanrelatief priemgetallen, dan

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

Regel het complete systeem van residuen modulotpnet zoPXt -matrices

1 2 t

t+1 t+2 2t

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

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

Omdat detenPcoprime, dan het nummerXwederzijds eenvoudig mettpals en alleen alsXwederzijds eenvoudig mettenXwederzijds eenvoudig metP. Maar het nummerkm + twederzijds eenvoudig mettals en alleen alstwederzijds eenvoudig mett.Daarom bevinden getallen die relatief priem zijn tot m zich in die kolommen waarvoor:tloopt door het gereduceerde systeem van residuen modulot.Het aantal van dergelijke kolommen is φ(t).Elke kolom presenteert het volledige systeem van residuen moduloP.Van deze resten φ(P)samenvallen metP.Vandaar dat het totale aantal getallen coprime en metten met n, gelijk aan φ(t)(n)

(φ (t)kolommen, die elk φ . duren(P)nummers). Deze getallen, en alleen zij, zijn coprime metenz.Het is dus bewezen dat

φ (tp)= φ (t) φ (P).

Voorbeelden.

№1 . Bewijs de volgende gelijkheden

φ(4n) =

Een bewijs.

№2 . los De vergelijking op

Oplossing:omdat(m)=, dan= , dat is=600, =75, =3, dan x-1=1, x=2,

y-1=2, y=3

Antwoord: x=2, y=3

We kunnen de waarde van de Euler-functie berekenen(m), kennende de canonieke weergave van het getal m:

m=.

Vanwege de vermenigvuldiger(m) we hebben:

(m)=.

Maar volgens formule (1) krijgen we dat

-1), en daarom

(3)

Gelijkheid (3) kan worden herschreven als:

Omdat de=m, dan(4)

Formule (3) of, wat hetzelfde is, (4) is de gewenste.

Voorbeelden.

№1 . Wat is het bedrag?

Oplossing:,

, =18 (1- ) (1- =18 , dan= 1+1+2+2+6+6=18.

№2 . Bewijs op basis van de eigenschappen van de Euler-getalfunctie dat er een oneindige reeks priemgetallen is in de reeks natuurlijke getallen.

Oplossing:Het aantal priemgetallen afvlakken met een eindige verzameling, stel dat:is het grootste priemgetal en laat a=is het product van alle priemgetallen, gebaseerd op een van de eigenschappen van de Euler-getalfunctie

sinds a≥, dan is a een samengesteld getal, maar aangezien zijn canonieke voorstelling alle priemgetallen bevat, dan is=1. Wij hebben:

=1 ,

wat onmogelijk is, en dus is bewezen dat de verzameling priemgetallen oneindig is.

№3 .Los De vergelijking op, waarbij x=en=2.

Oplossing:We gebruiken de eigenschap van de Euler-numerieke functie,

en op voorwaarde=2.

Express van=2 , we krijgen, laten we vervangen in

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

Dan x=, x=11 13=143.

Antwoorden:x= 143

De stelling van Euler en Fermat.

In de vergelijkingstheorie speelt de stelling van Euler een belangrijke rol.

De stelling van Euler.

Als een geheel getal a relatief priem is tot m, dan

(1)

Een bewijs.Laten

(2)

is een gereduceerd systeem van residuen modulo m.

Als eenais een geheel getal relatief priem tot m, dan

(3)

Overweeg een vergelijking van het formulier x 2 ≡a(mod p), waar p is een eenvoudig oneven getal. Zoals getoond in Paragraaf 4 §4, kan de oplossing voor deze congruentie worden gevonden door de congruentie op te lossen x 2 ≡a(mod p). En de vergelijking x 2 ≡a(mod pα) heeft twee oplossingen als a is een kwadratische rest modulo p.

Voorbeeld:

Kwadratische vergelijking oplossen x 2 ≡86 (mod 125).

125 = 5 3 , 5 is een priemgetal. Laten we eens kijken of 86 een vierkante modulo 5 is.

De originele vergelijking heeft 2 oplossingen.

Laten we een vergelijkingsoplossing zoeken x 2 ≡86 (mod. 5).

x 2 ≡1 (mod. 5).

Deze vergelijking zou kunnen worden opgelost op de manier die in de vorige paragraaf is aangegeven, maar we zullen gebruik maken van het feit dat de vierkantswortel van 1 modulo ±1 is, en de vergelijking heeft precies twee oplossingen. Dus de oplossing voor congruentie modulo 5 is

x≡±1(mod 5) of, anders, x=±(1+5 t 1).

Vervang de resulterende oplossing in de vergelijking 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), of gelijkwaardig, t 1 =1+5t 2 .

Dan is de oplossing voor congruentie modulo 25 x=±(1+5(1+5 t 2))=±(6+25 t 2). Vervang de resulterende oplossing in de vergelijking 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), of t 2 =1+5t 3 .

Dan is de oplossing voor de vergelijking modulo 125 x=±(6+25(1+5 t 3))=±(31+125 t 3).

Antwoorden: x≡±31 (mod. 125).

Overweeg nu een vergelijking van het formulier x 2 ≡a(mod2α). Zo'n vergelijking heeft niet altijd twee oplossingen. Voor een dergelijke module zijn de volgende gevallen mogelijk:

1) α=1. Dan heeft de vergelijking alleen een oplossing als a≡1(mod 2), en de oplossing is x≡1(mod 2) (één oplossing).

2) α=2. De vergelijking heeft alleen oplossingen als: a≡1(mod 4), en de oplossing is x≡±1(mod 4) (twee oplossingen).

3) α≥3. De vergelijking heeft alleen oplossingen als: a≡1(mod 8) en er zullen vier van dergelijke oplossingen zijn. Vergelijking x 2 ≡a(mod 2 α) voor α≥3 wordt op dezelfde manier opgelost als vergelijkingen van de vorm x 2 ≡a(mod pα), alleen oplossingen modulo 8 fungeren als de initiële oplossing: x≡±1(mod 8) en x≡±3 (mod. 8). Ze moeten worden vervangen door modulo 16, dan modulo 32, enzovoort tot modulo 2 .

Voorbeeld:

Vergelijking oplossen x 2 ≡33 (mod 64)

64=26. Laten we eens kijken of de originele vergelijking een oplossing heeft. 33≡1(mod 8), dus de vergelijking heeft 4 oplossingen.

Modulo 8 deze oplossingen zullen zijn: x≡±1(mod 8) en x≡±3(mod 8), die kan worden weergegeven als x=±(1+4 t een). Vervang deze uitdrukking in vergelijking 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)

Dan zal de oplossing de vorm aannemen x=±(1+4 t 1)=±(1+4(0+2 .) t 2))=±(1+8 t 2). Vervang de resulterende oplossing in de congruentie 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)

Dan zal de oplossing de vorm aannemen x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Vervang de resulterende oplossing in de vergelijking 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)

Dan zal de oplossing de vorm aannemen x=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t vier). Dus, modulo 64, de oorspronkelijke vergelijking heeft vier oplossingen: x≡±17 (mod 64) en x≡±49 (mod. 64).

Overweeg nu een algemene vergelijking: x 2 ≡a(mod m), (a,m)=1, - canonieke ontleding van de module m. Volgens de stelling uit paragraaf 4 van §4 is deze vergelijking equivalent aan het systeem

Als elke vergelijking van dit systeem beslisbaar is, dan is het hele systeem beslisbaar. Nadat we de oplossing van elke vergelijking van dit systeem hebben gevonden, verkrijgen we een systeem van vergelijkingen van de eerste graad, waarbij we oplossen, met behulp van de Chinese reststelling, de oplossing van de oorspronkelijke vergelijking verkrijgen. Bovendien is het aantal verschillende oplossingen van de oorspronkelijke vergelijking (als deze oplosbaar is) 2 k, als α=1, 2 k+1 als α=2, 2 k+2 als α≥3.

Voorbeeld:

Vergelijking oplossen x 2 ≡4 (mod. 21).

Wiskundeproject over het onderwerp

"Modulo-vergelijkingen"

Zaripova Aisylu

Sovetsky-district van de stad Kazan

MBOU "Secundaire school nr. 166", klas 7a

Wetenschappelijk adviseur: Antonova N.A.

Inhoudsopgave

Inleiding _________________________________________________________3

Wat zijn vergelijkingen _________________________________________4

Toepassing van vergelijkingen bij het oplossen van problemen ______________________6

De eenvoudigste toepassing van modulo-vergelijkingen is om de deelbaarheid van getallen te bepalen _____________________6
Eén taak ter vergelijking __________________________________________8
Het gebruik van modulo-vergelijkingen in professionele activiteiten ___________________________________________9

Conclusie____________________________________________________10

Lijst met referenties ______________________________11

Invoering.

R&D: Modulo-vergelijkingen.

Probleem: Veel studenten worden geconfronteerd met taken ter voorbereiding op de Olympiade, waarvan de oplossing is gebaseerd op de kennis van de restanten van het delen van gehele getallen door een natuurlijk getal. We waren geïnteresseerd in dergelijke problemen en mogelijke methoden voor hun oplossing. Het blijkt dat ze kunnen worden opgelost met behulp van modulo-vergelijkingen.

Doel: De essentie van modulo-vergelijkingen verduidelijken, de belangrijkste methoden om met modulo-vergelijkingen te werken.

Taken: theoretisch materiaal zoeken over dit onderwerp, problemen overwegen die met behulp van modulo-vergelijkingen zijn opgelost, de meest gebruikelijke methoden voor het oplossen van dergelijke problemen laten zien, conclusies trekken.

Studieobject: getaltheorie.

Onderwerp van onderzoek: de theorie van vergelijkingen modulo.

Het werk behoort tot theoretisch onderzoek en kan worden gebruikt ter voorbereiding op olympiades in de wiskunde. In de inhoud worden de basisconcepten van modulo-vergelijkingen en hun belangrijkste eigenschappen onthuld, voorbeelden van het oplossen van problemen over dit onderwerp worden gegeven.

l . Wat zijn vergelijkingen.

Getallen en worden modulo vergelijkbaar genoemd als ze deelbaar zijn door, met andere woorden, a en b hebben dezelfde rest als ze worden gedeeld door.

Aanduiding

Voorbeelden:

12 en 32 zijn vergelijkbaar modulo 5, aangezien 12, wanneer gedeeld door 5, een rest heeft van 2, en 32, wanneer gedeeld door 2, een rest heeft van 2. Het is geschreven12 ;

101 en 17 zijn congruent modulo 21;

De theorie van deelbaarheid is voor een groot deel gemaakt door Euler. De definitie van vergelijking is geformuleerd in het boek van C.F. Gauss "Arithmetic Research". Dit werk, geschreven in het Latijn, werd in 1797 gedrukt, maar het boek werd pas in 1801 gepubliceerd vanwege het feit dat het drukproces in die tijd buitengewoon arbeidsintensief en langdurig was. Het eerste deel van Gauss' boek heet "On the Comparison of Numbers". Het was Gauss die de symboliek van modulo-vergelijkingen voorstelde, die in de wiskunde was gevestigd.

Als een

Een bewijs:

Als we de tweede bij de eerste vergelijking optellen, krijgen we

is de som van twee gehele getallen, dus is een geheel getal dus.

Als we de tweede van de eerste vergelijking aftrekken, krijgen we

is het verschil van twee gehele getallen, dus is een geheel getal dus.

Denk aan de uitdrukking:

is het verschil tussen de producten van gehele getallen, dus is een geheel getal dus.

Dit is een gevolg van de derde eigenschap van vergelijkingen.

QED

5) Als een.

Een bewijs: Laten we de som van deze twee uitdrukkingen vinden:

is de som van twee gehele getallen, dus is een geheel getal, dus .

QED

6) Als een geheel getal is, dan

Bewijs: waar?p- een geheel getal, vermenigvuldig deze gelijkheid met, we krijgen: . Omdat het product van gehele getallen is, wat moest worden bewezen.

7) Als een

Een bewijs: De redenering is vergelijkbaar met het bewijs van eigenschap 6.

8) Als een - relatief priemgetallen, dan

Een bewijs: , delen we deze uitdrukking door, we krijgen: - coprime getallen, wat betekent dat het deelbaar is door een geheel getal, d.w.z. =. En dit betekent dat wat moest worden bewezen.

II . Toepassing van vergelijkingen bij het oplossen van problemen.

2.1. De eenvoudigste toepassing van modulo-vergelijkingen is om de deelbaarheid van getallen te bepalen.

Voorbeeld. Vind de rest van deling 2 2009 om 7 uur.

Oplossing: overweeg machten van 2:

Als we de vergelijking verhogen tot de macht 668 en vermenigvuldigen met, krijgen we: .

Antwoord: 4.

Voorbeeld. Bewijs dat 7+7 2 +7 3 +…+7 4 n deelbaar door 100 voor anynuit een verzameling gehele getallen.

Oplossing: overweeg vergelijkingen

enz. De cycliciteit van de residuen wordt verklaard door de regels voor het vermenigvuldigen van getallen met een kolom. Als we de eerste vier vergelijkingen toevoegen, krijgen we:

Deze som is dus deelbaar door 100 zonder rest. Evenzo, als we de volgende vergelijkingen over vier optellen, krijgen we dat elke dergelijke som deelbaar is door 100 zonder rest. Dus de hele som van 4ntermen is deelbaar door 100 zonder rest. QED

Voorbeeld. Bepaal tegen welke waardende uitdrukking is deelbaar door 19 zonder rest.

Oplossing: .

Vermenigvuldig deze vergelijking met 20. We krijgen.

Laten we dan vergelijkingen toevoegen. . De rechterkant van de vergelijking is dus altijd deelbaar door 19 voor elke natuurlijken, wat betekent dat de oorspronkelijke uitdrukking deelbaar is door 19 met natuurlijkn.

Antwoorden n is een natuurlijk getal.

Voorbeeld. Op welk cijfer eindigt het getal.

Oplossing. Om dit probleem op te lossen, volgen we alleen het laatste cijfer. Overweeg de krachten van het getal 14:

Het is te zien dat voor een oneven exponent de waarde van de graad eindigt op 4, en voor een even exponent eindigt op 6. Dan eindigt het op 6, d.w.z. een even getal is. Dus het zal eindigen in 6.

Antwoord 6.

2.2. Een taak ter vergelijking.

In het artikel van N. Vilenkin "Comparisons and Residue Classes" wordt een probleem gepresenteerd dat in zijn studententijd werd opgelost door de beroemde Engelse natuurkundige Dirac.

Er is ook een korte oplossing voor dit probleem met behulp van modulo-vergelijkingen. Maar we ontmoetten een aantal vergelijkbare taken. Bijvoorbeeld.

Een voorbijganger vond een bos appels bij de boom waar de aap zat. Nadat hij ze had geteld, realiseerde hij zich dat als 1 appel aan een aap wordt gegeven, het aantal resterende appels wordt gedeeld door n zonder een spoor. Nadat hij de extra appel aan de aap had gegeven, nam hij 1/ n resterende appels en vertrokken. De stapel werd later benaderd door de volgende voorbijganger, dan de volgende, enzovoort. Elke volgende voorbijganger die de appels telde, merkte op dat hun aantal, wanneer gedeeld door n geeft de rest 1 en, de aap een extra appel gevend, nam hij 1 / n resterende appels en ging verder. Na de laatste vertrokken n de voorbijganger, het aantal appels dat nog in de stapel ligt, is deelbaar door n zonder een spoor. Hoeveel appels lagen er eerst op de stapel?

Nadat we dezelfde redenering als Dirac hadden uitgevoerd, kregen we een algemene formule voor het oplossen van een klasse van vergelijkbare problemen: , waarbijn- natuurlijk nummer.

2.3. Het gebruik van modulo-vergelijkingen in professionele activiteiten.

De theorie van vergelijkingen wordt gebruikt in de codeertheorie, dus alle mensen die een beroep hebben gekozen dat verband houdt met computers, zullen vergelijkingen bestuderen en mogelijk toepassen in hun professionele activiteiten. Om bijvoorbeeld algoritmen voor versleuteling met openbare sleutels te ontwikkelen, worden een aantal concepten uit de getaltheorie gebruikt, waaronder modulo-vergelijkingen.

Conclusie.

Het artikel schetst de basisconcepten en eigenschappen van modulo-vergelijkingen; voorbeelden illustreren het gebruik van modulo-vergelijkingen. Het materiaal kan worden gebruikt ter voorbereiding op Olympiades in de wiskunde en het Unified State Examination.

De bovenstaande lijst met referenties maakt het mogelijk om, indien nodig, enkele meer complexe aspecten van de theorie van modulo-vergelijkingen en zijn toepassingen te overwegen.

Lijst met gebruikte literatuur.

Alfutova NB Algebra en getaltheorie./NBAlfutova, AVUstinov. M.: MTSNMO, 2002, 466 d.

Bukhshtab AA Nummer theorie. / AA Bukhshtab. Moskou: Onderwijs, 1960.

Vilenkin N. Vergelijkingen en residuklassen./N.Vilenkin.//Kvant. – 1978.- 10.

Fedorova NE De studie van algebra en wiskundige analyse. Graad 10.http:// www. voordelen. en/ e-boeken/ Fedorova_ Algebra_10 kl/1/ xht

en. wikipedia. org/ wiki/Modulo_vergelijking.

Bij n geven ze dezelfde rest.

Equivalente formuleringen: a en b vergelijkbare module n als hun verschil a - b is deelbaar door n , of als a kan worden weergegeven als a = b + kn , waar k is een geheel getal. Bijvoorbeeld: 32 en −10 zijn congruent modulo 7 omdat

De verklaring "a en b zijn congruent modulo n" wordt geschreven als:

Modulo Gelijkheid Eigenschappen

De modulo-vergelijkingsrelatie heeft de eigenschappen

Elke twee gehele getallen a en b zijn vergelijkbaar modulo 1.

Om de cijfers a en b waren vergelijkbaar modulo n, is het noodzakelijk en voldoende dat hun verschil deelbaar is door n.

Als de getallen en paarsgewijs vergelijkbaar zijn modulo n, dan hun sommen en , evenals producten en zijn ook vergelijkbaar modulo n.

Als nummers a en b vergelijkbare module n, dan hun graden a k en b k zijn ook vergelijkbaar modulo n voor elke natuurlijke k.

Als nummers a en b vergelijkbare module n, en n gedeeld door m, dan a en b vergelijkbare module m.

Om de cijfers a en b waren vergelijkbaar modulo n, weergegeven als de canonieke ontleding in priemfactoren p i

nodig en voldoende om

De vergelijkingsrelatie is een equivalentierelatie en heeft veel van de eigenschappen van gewone gelijkheden. Ze kunnen bijvoorbeeld worden opgeteld en vermenigvuldigd: als

Vergelijkingen kunnen echter in het algemeen niet door elkaar of door andere getallen worden gedeeld. Voorbeeld: , echter verminderend met 2, krijgen we een foutieve vergelijking: . De reductieregels voor vergelijkingen zijn als volgt.

U kunt ook geen bewerkingen uitvoeren op vergelijkingen als hun modules niet overeenkomen.

Andere eigenschappen:

Verwante definities

Aftrek lessen

De verzameling van alle getallen vergelijkbaar met a modulo n genaamd aftrek klasse a modulo n , en wordt meestal aangeduid met [ a] n of . De vergelijking is dus gelijk aan de gelijkheid van de residuklassen [a] n = [b] n .

Omdat modulo vergelijking n is een equivalentierelatie op de verzameling gehele getallen, dan zijn de residuklassen modulo n zijn equivalentieklassen; hun nummer is n. De verzameling van alle residuklassen modulo n aangeduid met of .

De bewerkingen van optellen en vermenigvuldigen op induceren de overeenkomstige bewerkingen op de verzameling:

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

Met betrekking tot deze bewerkingen is de verzameling een eindige ring, en als n eenvoudig - laatste veld .

aftreksystemen

Met het residusysteem kunt u rekenkundige bewerkingen uitvoeren op een eindige reeks getallen zonder verder te gaan. Compleet systeem van inhoudingen modulo n is elke verzameling van n gehele getallen die onvergelijkbaar zijn modulo n. Gewoonlijk neemt men als een compleet systeem van residuen modulo n de kleinste niet-negatieve residuen

0,1,...,n − 1

of absoluut kleinste resten bestaande uit getallen

in geval van oneven n en cijfers

in het geval van even n .

Vergelijkingsbesluit

Vergelijkingen van de eerste graad

In getaltheorie, cryptografie en andere wetenschapsgebieden doet zich vaak het probleem voor om oplossingen te vinden voor een vergelijking van de eerste graad van de vorm:

De oplossing van zo'n vergelijking begint met de berekening van de ggd (a, m)=d. In dit geval zijn er 2 gevallen mogelijk:

Als een b geen veelvoud d, dan heeft de vergelijking geen oplossingen.
Als een b meerdere d, dan heeft de vergelijking een unieke oplossing modulo m / d, of, wat hetzelfde is, d modulo-oplossingen m. In dit geval, als gevolg van het verminderen van de oorspronkelijke vergelijking met d vergelijking resultaten:

waar a 1 = a / d , b 1 = b / d en m 1 = m / d zijn gehele getallen, en a 1 en m 1 zijn coprime. daarom het nummer a 1 kan modulo worden omgekeerd m 1, dat wil zeggen, vind zo'n getal c dat (met andere woorden, ). Nu wordt de oplossing gevonden door de resulterende vergelijking te vermenigvuldigen met c:

Praktische waardeberekening c kan op verschillende manieren: met behulp van de stelling van Euler, het algoritme van Euclides, de theorie van kettingbreuken (zie algoritme), enz. In het bijzonder kunt u met de stelling van Euler de waarde schrijven c net zo:

Voorbeeld

Ter vergelijking: we hebben d= 2 , dus modulo 22 de vergelijking heeft twee oplossingen. Laten we 26 vervangen door 4, wat vergelijkbaar is met modulo 22, en dan alle 3 de getallen annuleren door 2:

Aangezien 2 coprime is met modulo 11, kunnen we de linker- en rechterkant met 2 verkleinen. Als resultaat krijgen we één oplossing modulo 11: , wat gelijk is aan twee oplossingen modulo 22: .

Vergelijkingen van de tweede graad

Het oplossen van vergelijkingen van de tweede graad wordt gereduceerd tot het uitzoeken of een gegeven getal een kwadratische rest is (met behulp van de kwadratische wet van wederkerigheid) en vervolgens de vierkantswortel modulo dit te berekenen.

Verhaal

De Chinese reststelling, die al vele eeuwen bekend is, stelt (in moderne wiskundige taal) dat de residuring modulo het product van verschillende priemgetallen is

Een vergelijking van de eerste graad met een onbekende heeft de vorm:

f(x) 0 (mod m); f(X) = Oh + een. (1)

Vergelijking oplossen betekent om alle waarden van x te vinden die eraan voldoen. Twee vergelijkingen die voldoen aan dezelfde waarden van x heten gelijkwaardig.

Als vergelijking (1) enigszins voldoet x = x 1, dan (volgens 49) alle getallen vergelijkbaar met x 1, modulo m: x x 1 (mod) m). Deze hele klasse van getallen telt als: een oplossing. Met deze overeenkomst kan de volgende conclusie worden getrokken.

66.C uitlijning (1) zal net zoveel oplossingen hebben als er resten van het complete systeem zijn die eraan voldoen.

Voorbeeld. Vergelijking

6x– 4 0 (mod 8)

onder de getallen 0, 1,2, 3, 4, 5, 6, 7 van het volledige systeem van residuen modulo 8, voldoen twee getallen: X= 2 en X= 6. Daarom heeft deze vergelijking twee oplossingen:

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

Vergelijking van de eerste graad door de vrije term (met het tegengestelde teken) naar de rechterkant over te brengen kan worden teruggebracht tot de vorm

bijl b(mod m). (2)

Overweeg een vergelijking die voldoet aan de voorwaarde ( a, m) = 1.

Volgens 66 heeft onze vergelijking evenveel oplossingen als er resten zijn van het complete systeem dat eraan voldoet. Maar wanneer x loopt door het volledige systeem van residuen modulo t, dan Oh loopt door het volledige systeem van inhoudingen (van de 60). Daarom, voor één en slechts één waarde X, overgenomen uit het volledige systeem, Oh zal vergelijkbaar zijn met b. Dus,

67. Voor (a, m) = 1 vergelijking ax b(mod m)heeft één oplossing.

Laat nu ( a, m) = d> 1. Dan, ter vergelijking (2) om oplossingen te hebben, is het noodzakelijk (van de 55) dat b verdeeld in d, anders is vergelijking (2) onmogelijk voor elk geheel getal x . er van uitgaande dat b meerdere d, laten we a = a 1 d, b = b 1 d, m = m 1 d. Dan is vergelijking (2) hiermee gelijk (verkleind met d): a 1 x b 1 (mod) m), waarin al ( a 1 , m 1) = 1, en daarom zal het één oplossing hebben modulo m een . Laten X 1 is het kleinste niet-negatieve residu van deze oplossing modulo m 1 , dan alle getallen x , het vormen van deze oplossing is te vinden in de vorm

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

Modulo, de getallen (3) vormen niet één oplossing, maar meer, precies zoveel oplossingen als er getallen (3) zijn in de reeks 0, 1, 2, ..., m 1 minst niet-negatief residu modulo m. Maar de volgende cijfers vallen hier (3):

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

die. Totaal d cijfers (3); vandaar vergelijking (2) heeft d oplossingen.

We krijgen de stelling:

68. Laat (a, m) = d. vergelijking bijl b ( mod m) onmogelijk als b niet deelbaar is door d. Als b een veelvoud van d is, heeft de vergelijking d-oplossingen.

69. Methode voor het oplossen van vergelijking van de eerste graad, gebaseerd op de theorie van kettingbreuken:

De verhouding uitbreiden tot een kettingbreuk m:a,

en gezien de laatste twee convergenten:

volgens de eigenschappen van kettingbreuken (volgens 30 ) wij hebben

Dus de vergelijking heeft een oplossing

voor de zoekopdracht, wat genoeg is om te berekenen P n- 1 volgens de methode gespecificeerd in 30.

Voorbeeld. Laten we de vergelijking oplossen

111x= 75 (model 321). (vier)

Hier (111, 321) = 3, en 75 is een veelvoud van 3. Daarom heeft de vergelijking drie oplossingen.

Als we beide delen van de vergelijking en de modulus door 3 delen, krijgen we de vergelijking

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

waarover we eerst moeten beslissen. Wij hebben

q
P 3

Dus in dit geval n = 4, Pn- 1 = 26, b= 25, en we hebben de oplossing van vergelijking (5) in de vorm

x–26 ∙ 25 99 (mod. 107).

Daarom worden de oplossingen van vergelijking (4) als volgt gepresenteerd:

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

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

Berekening van het inverse element modulo a gegeven

70.Als gehele getallen a en n coprime, dan is er een getal a', voldoet aan de vergelijking een een′ ≡ 1(mod) n). Nummer a' genaamd multiplicatieve inverse van een modulo n en de notatie wordt ervoor gebruikt a- 1 (mod) n).

De berekening van reciprocals modulo some kan worden gedaan door een eerstegraads vergelijkingsoplossing met een onbekende, waarbij: x geaccepteerd nummer a'.

Om een vergelijkingsoplossing te vinden

een x≡ 1 (mod m),

waar ( ben)= 1,

men kan het Euclid-algoritme (69) of de stelling van Fermat-Euler gebruiken, die stelt dat als ( ben) = 1, dan

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

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

Groepen en hun eigenschappen

Groepen zijn een van de taxonomische klassen die worden gebruikt bij de classificatie van wiskundige structuren met gemeenschappelijke karakteristieke eigenschappen. Groepen hebben twee componenten: veel (G) en activiteiten() gedefinieerd op deze set.

De concepten verzameling, element en lidmaatschap zijn de ongedefinieerde basisconcepten van de moderne wiskunde. Elke set wordt gedefinieerd door de elementen die erin zijn opgenomen (die op hun beurt ook sets kunnen zijn). We zeggen dus dat een verzameling is gedefinieerd of gegeven als we voor elk element kunnen zeggen of het tot deze verzameling behoort of niet.

Voor twee sets A, B records B EEN, B EEN, B∩ EEN, B EEN, B \ EEN, EEN × B respectievelijk betekenen dat B is een subset van de set EEN(d.w.z. elk element van B zit ook in EEN, de verzameling natuurlijke getallen zit bijvoorbeeld in de verzameling reële getallen; trouwens, altijd EEN EEN), B is een juiste subset van de set EEN(die. B EEN en B ≠ EEN), kruising van velen B en EEN(d.w.z. al dergelijke elementen die tegelijkertijd en in EEN, en in B, bijvoorbeeld het snijpunt van gehele getallen en positieve reële getallen is de verzameling natuurlijke getallen), de vereniging van verzamelingen B en EEN(d.w.z. een verzameling die bestaat uit elementen die ofwel in EEN, ofwel in B), verschil instellen B en EEN(d.w.z. de verzameling elementen die in B, maar lieg er niet in EEN), het cartesiaanse product van verzamelingen EEN en B(d.w.z. een set paren van de vorm ( a, b), waar a EEN, b B). door | EEN| de kardinaliteit van de set wordt altijd aangegeven EEN, d.w.z. aantal elementen in de set EEN.