Teori om små tal. Talteori: teori og praksis

Talteori eller højere aritmetik er en gren af matematikken, der studerer heltal og lignende objekter.

Talteori beskæftiger sig med studiet af heltals egenskaber. I øjeblikket omfatter talteori en meget bredere vifte af spørgsmål, der går ud over studiet af naturlige tal.

I talteorien betragtes ikke kun naturlige tal, men også mængden af alle heltal, mængden rationelle tal, en masse algebraiske tal. Moderne talteori er karakteriseret ved brugen af meget forskellige metoder forskning. I moderne talteori er metoder meget brugt matematisk analyse.

Moderne teori tal kan opdeles i følgende sektioner:

1) Elementær talteori. Dette afsnit indeholder spørgsmål om talteori, som er direkte udvikling teorier om delelighed og spørgsmål om tals repræsentativitet i en bestemt form. Et mere generelt problem er problemet med at løse systemer af diofantiske ligninger, det vil sige ligninger, hvor værdierne af de ukendte nødvendigvis skal være heltal.

2) Algebraisk teori tal. Dette afsnit indeholder spørgsmål relateret til studiet af forskellige klasser af algebraiske tal.

3) Diofantiske tilnærmelser. Dette afsnit indeholder spørgsmål relateret til studiet af tilnærmelse af reelle tal rationelle brøker. Nært beslægtet med den samme kreds af ideer, er diofantiske tilnærmelser nært beslægtede med studiet af den aritmetiske karakter af forskellige klasser af tal.

4) Analytisk teori om tal. Dette afsnit indeholder spørgsmål om talteori, til undersøgelsen af hvilke det er nødvendigt at anvende metoder til matematisk analyse.

Basale koncepter:

1) Delbarhed er et af de grundlæggende begreber inden for aritmetik og talteori forbundet med divisionsoperationen. Set fra mængdelærens synspunkt er deleligheden af heltal en relation defineret på mængden af heltal.

Hvis der for et eller andet heltal a og et heltal b er et heltal q, således at bq = a, så siger vi, at tallet a er deleligt med b, eller at b deler a. I dette tilfælde kaldes tallet b divisor af tallet a, udbyttet af a vil være et multiplum af tallet b, og tallet q kaldes kvotienten af a divideret med b.

2) Et simpelt tal? er et naturligt tal, der har præcis to forskellige naturlig divisor: enhed og dig selv. Alle andre tal undtagen ét kaldes sammensatte tal.

3) Perfekt tal? (gammelgræsk ἀριθμὸς τέλειος) - naturligt tal, lig med summen alle sine egne divisorer (dvs. alle positive divisorer, forskellig fra sig selv? tal).

Det første perfekte tal er 6 (1 + 2 + 3 = 6), det næste er 28 (1 + 2 + 4 + 7 + 14 = 28). Når de naturlige tal stiger, perfekte tal bliver mindre og mindre almindelige.

4) Den største fælles divisor (GCD) for to heltal m og n er den største af deres fælles divisorer. Eksempel: for tallene 70 og 105 den største fælles divisor svarer til 35.

Den største fælles divisor findes og er entydigt bestemt, hvis mindst et af tallene m eller n ikke er nul.

5) Det mindste fælles multiplum (LCM) af to heltal m og n er det mindste naturlige tal, der er deleligt med m og n.

6) Tal m og n kaldes coprime, hvis de ikke har andre fælles divisorer end én. For sådanne tal er GCD(m,n) = 1. Omvendt, hvis GCD(m,n) = 1, så er tallene coprime.

7) Euklidisk algoritme - en algoritme til at finde den største fælles divisor af to heltal eller det største fælles mål for to homogene størrelser.

Du kan også finde den information, du er interesseret i, i den videnskabelige søgemaskine Otvety.Online. Brug søgeformularen:

Mere om emne nr. 17. Grundlæggende begreber i talteori:

Talteori er en gren af matematikken, der studerer tals egenskaber.

Hovedformålet med talteori er naturlige tal (se Tal). Deres vigtigste egenskab, som betragtes af talteori, er delelighed. Den første række af problemer i talteorien er faktorisering af tal. De vigtigste "byggesten" i denne nedbrydning er primtal, dvs. tal kun delelige med 1 og sig selv; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - det er de første ti Primtal(tallet 1 betragtes ikke som primtal). Vidunderlig sætning, kaldet aritmetikkens grundsætning, siger: ethvert naturligt tal kan dekomponeres til primære faktorer, og den eneste måde(op til rækkefølgen af deres placering). Ved at faktorisere to tal i primfaktorer er det let at bestemme, om det ene af dem er deleligt med det andet eller ej. Men det kan stadig være svært at finde ud af, om det er det stort antal enkelt, dvs. om det er deleligt med et andet tal end sig selv og et.

Serien forbundet med at faktorisere tal til primfaktorer er aritmetiske funktioner. Lad os pege på nogle af dem. φ(n) - Euler funktion - antallet af tal fra 1 til n, der er coprime til tallet n (dvs. ikke deler med n) fælles faktorer, bortset fra én); α(n) er antallet af divisorer af tallet n, t(n) er summen af alle divisorer af tallet n, π(n) er Chebyshev-funktionen - antallet af primtal, der ikke overstiger n. Disse funktioner udtrykker mange egenskaber ved naturlige tal. Euklids sætning siger, at der er uendeligt mange primtal. Det betyder, at π(n)→∞ når tallet n stiger. Vi var i stand til at finde ud af, hvor hurtigt funktionen π(n) tenderer mod det uendelige. Det viste sig, at det er omtrent det samme som funktionen

Denne sætning kaldes den asymptotiske lov om fordeling af primtal. Det blev formuleret og stort set bevist af P. L. Chebyshev (1849), og blev fuldt bevist kun 50 år senere.

Den asymptotiske lov om fordeling af primtal er resultatet af den såkaldte analytiske talteori, som i vid udstrækning anvender matematisk analysemetoder til at studere talteoretiske funktioner. Opdaget i anden halvdel af det 19. århundrede. forholdet mellem et så diskret objekt som heltal og funktioners dybe egenskaber havde stor indflydelse på talteoriens udvikling.

Faktorering af tal tager kun hensyn til strukturen af det sæt af naturlige tal, der er forbundet med multiplikation, de dybeste og svære opgaver talteorier opstår ved sammenligning af addition og multiplikation. Sådanne problemer omfatter for eksempel Goldbachs problem - er det muligt at gøre noget? lige tal repræsentere det som summen af to primtal; stor sætning Fermat (se Fermats sidste sætning) - er det muligt n'te potens repræsentere tallene som sum n'er potenser af to tal osv.

Talteori er attraktiv, fordi den indeholder mange enkle formuleringer, men svære og interessante opgaver. Mange af disse problemer, løste og uløste, har akkumuleret, og talteori virker ofte som en samling af forskellige elegante gåder. Det er det dog ikke. Talteori har skabt sine egne vidunderlige metoder, og mange af dem er blevet aktivt udviklet i de seneste årtier, hvilket har sprøjtet en ny levende strøm ind i netop denne. den gamle del matematik.

Den klassiske metode for talteori er metoden til sammenligninger. Ved at identificere tal, der giver identiske rester, når de divideres med et udvalgt tal, er det ofte muligt at fastslå umuligheden af ethvert forhold. For eksempel, hvis man betragter resten af division med 3 (eller, som de siger, modulo 3), er det let at bevise uløseligheden af ligningen 3x 2 + 4y 2 = 5z 2 i naturlige tal.

Analytisk metode består, som vi allerede har sagt, i det faktum, at de ud fra tal konstruerer funktioner, der studeres ved matematiske analysemetoder. Ja, sovjet videnskabsmand akademiker I.M. Vinogradov beviste en version af Goldbachs problem - repræsentationen af et tilstrækkeligt stort ulige tal som en sum af tre primtal.

Vi illustrerer talteoriens geometriske metode ved at bruge Fermats sidste sætning som eksempel. I denne sætning vi taler om på løseligheden af ligningen x n + y n = z n i heltal. Ved at dividere begge sider af ligningen med z n og erstatte x/z med m og y/z med v, får vi ligningen u n + v n = 1. Denne ligning definerer en bestemt kurve på planet med koordinater (u, v). Løsninger til den oprindelige ligning i heltal svarer til løsninger til den nye ligning i rationelle tal. Hver sådan løsning (u, v) kan omtales som et punkt med rationelle koordinater på dette plan. Nu kan vi prøve at søge geometriske metoder til kurven u n + v n = 1 for at studere punktersættet med rationelle koordinater på.

En stor del af talteorien, der beskæftiger sig med at finde løsninger til ligninger i heltal og rationelle tal, kaldes teorien om diofantiske ligninger, opkaldt efter den antikke græske videnskabsmand Diophantus (3. århundrede).

Et af de meget gamle og velkendte problemer inden for talteori er problemet med at repræsentere tal ved kvadratsummer. Vi lister nogle af de opnåede resultater:

hvert heltal kan repræsenteres som summen af fire kvadrater af heltal (for eksempel: 7 = 2 2 + 1 2 + 1 2 + 1 2);

hvert primtal på formen 4n + 1 kan repræsenteres som summen af to kvadrater af heltal (for eksempel: 5 = 2 2 + 1 2, 41 = 4 2 + 5 2 osv.), men ikke et enkelt heltal ( ikke blot et primtal) et tal på formen 4n + 3 kan ikke repræsenteres i denne form;

Hvert primtal, undtagen tal på formen 8n - 1, kan repræsenteres som summen af tre kvadrater af heltal.

Simpel algebraisk identitet

(a 2 + b 2) (x 2 + y 2) = (ax + by) 2 + (ay - bx) 2

giver os mulighed for at konkludere: Hvis to tal er repræsenteret som summen af to kvadrater, så er deres produkt også repræsenteret som summen af to kvadrater. Algebraiske metoder V På det sidste meget brugt i talteori. Dette blev lettet af udviklingen af et så generelt algebraisk koncept som et felt, hvis udseende i høj grad blev stimuleret af problemer i talteori.

Hvorfor er talteori så værdifuld? Det er trods alt svært at finde direkte anvendelse af dets resultater. Ikke desto mindre har talteoretiske problemer tiltrukket både nysgerrige unge mennesker og videnskabsmænd i mange århundreder. Hvad er der i vejen her? Først og fremmest er disse problemer, som allerede nævnt, meget interessante og smukke. Til alle tider har folk været overrasket over det simple spørgsmål Det er så svært at finde et svar på tal. Søgningen efter disse svar har ofte ført til opdagelser, hvis betydning langt overstiger rækkevidden af talteori. Det er tilstrækkeligt at nævne den såkaldte teori om idealer tysk matematiker XIX århundrede E. Kummer, som blev født i forbindelse med forsøg på at bevise Fermats sidste sætning.

Navn: Talteori. 2008.

Lærebogen er baseret på resultaterne elementær teori tal, dannet i klassikernes værker - Fermat, Euler, Gauss og andre Spørgsmål som primtal og sammensatte tal, aritmetiske funktioner, teorien om sammenligninger, primitive rødder og indekser, fortsatte brøker, algebraiske og transcendentale tal. Primtals egenskaber, teorien om diofantiske ligninger, algoritmiske aspekter af talteori med anvendelser i kryptografi (test af store primtal for primalitet, faktorisering store tal ind i faktorer, diskret logaritme) og brug af en computer.
For universitetsstuderende.

Emnet for studiet af talteori er tal og deres egenskaber, dvs. tal optræder her ikke som et middel eller instrument, men som et studieobjekt. Naturlig serie
1,2,3,4, ...,9,10,11, ...,99,100,101, ...
- sættet af naturlige tal - er det vigtigste forskningsområde, ekstremt informativt, vigtigt og interessant.
Studiet af naturlige tal begyndte i Det gamle Grækenland. Euklid og Eratosthenes opdagede egenskaberne ved tals delelighed, beviste uendeligheden af sættet af primtal og fandt måder at konstruere dem på. Problemer forbundet med løsningen ubestemte ligninger i hele tal, var genstand for forskning af Diophantus, såvel som videnskabsmænd Oldtidens Indien og det gamle Kina, de centralasiatiske lande.

Indholdsfortegnelse
Introduktion
Kapitel 1. Om tals delelighed
1.1. Heltals delelighedsegenskaber
1.2. Mindste fælles multiplum og største fælles divisor
1.3. Euklids algoritme
1.4. Heltalsløsning lineære ligninger

Kapitel 2. Primtal og sammensatte tal
2.1. Primtal. Sigte af Eratosthenes. Uendeligheden af sættet af primtal
2.2. Aritmetikkens grundlæggende sætning
2.3. Chebyshevs teoremer
2.4. Riemann Zeta-funktion og egenskaber for primtal
Problemer, der skal løses selvstændigt
Kapitel 3. Aritmetiske funktioner
3.1. Multiplikative funktioner og deres egenskaber
3.2. Möbius funktion og inversionsformler
3.3. Euler funktion
3.4. Summen af divisorer og antal divisorer naturligt tal
3.5. Estimater af middelværdien af aritmetiske funktioner
Problemer, der skal løses selvstændigt
Kapitel 4: Numeriske sammenligninger
4.1. Sammenligninger og deres grundlæggende egenskaber
4.2. Fradragsklasser. Ring af restklasser for et givet modul
4.3. Komplette og reducerede fradragssystemer
4.4. Wilsons teorem
4.5. Eulers og Fermats sætninger
4.6. Repræsentation af rationelle tal som uendelige decimaler
4.7. Test for primalitet og konstruktion af store primtal
4.8. Heltalsfaktorisering og kryptografiske applikationer
Problemer, der skal løses selvstændigt
Kapitel 5. Sammenligninger med en ukendt
5.1.Grundlæggende definitioner
5.2. Sammenligninger af første grad
5.3.Kinesisk restsætning
5.4. Polynomielle sammenligninger ved enkelt modul
5.5. Polynomielle sammenligninger ved sammensatte moduloProblemer til uafhængig løsning
Kapitel 6. Sammenligninger af anden grad
6.1. Sammenligninger af anden grads modulo primtal
6.2. Legendres symbol og dets egenskaber
6.3. Kvadratisk gensidighedslov
6.4 Jacobi-symbolet og dets egenskaber
6.5 Summer af to og fire kvadrater
6.6. Repræsentation af nul kvadratiske former fra tre variable
Problemer, der skal løses selvstændigt
Kapitel 7. Antiderivative rødder og indekser
7.1. Indikator for et tal for et givet modul
7.2. Eksistensen af primitive rødder modulo prime
7.3. Konstruktion af primitive rødder vha. modulerne pk og 2pk
7.4. Sætning om fravær af primitive rødder i andre moduler end 2, 4, pk og 2pk
7.5. Indekser og deres egenskaber
7.6. Diskret logaritme
7.7. Binomiale sammenligninger
Problemer, der skal løses selvstændigt
Kapitel 8. Fortsat brøker
8.1. Dirichlets sætning om tilnærmelse af reelle tal ved rationelle tal
8.2. Endelige fortsatte fraktioner
8.3. Fortsat brøkdel reelle tal
8.4. Bedste Approksimationer
8.5. Tilsvarende tal
8.6. Kvadratiske irrationaliteter og fortsatte brøker
8.7. Brug af fortsatte brøker til at løse nogle diofantiske ligninger
8.8 Dekomponering af tallet e til en fortsat brøk
Problemer, der skal løses selvstændigt
Kapitel 9. Algebraiske og transcendentale tal
9.1.Felt med algebraiske tal
9.2. Approksimationer af algebraiske tal med rationelle tal. Eksistensen af transcendentale tal
9.3. Irrationaliteten af tallene er og n
9.4. Transcendens af tallet e
9.5. Transcendens af tallet n
9.6. Det er umuligt at kvadrere en cirkel
Problemer, der skal løses selvstændigt
Svar og anvisninger
Bibliografi

Gratis download e-bog i et praktisk format, se og læs:
Download bogen Talteori - Nesterenko Yu.V. - fileskachat.com, hurtig og gratis download.

Download djvu
Nedenfor kan du købe denne bog til den bedste pris med rabat med levering i hele Rusland.

Talteori 1

1. Grundlæggende begreber i delelighedsteori

Î DEFINITION Nummer a er deleligt med et ikke-nul tal b, hvis der er et heltal c, således at ligheden a = b · c gælder.

Betegnelser:

1) a .b a divideres med b ;

2) b | a b deler a;

3) a er et multiplum (multipel) af b , b af divisor a .

Division med resten

Lad to tal a èb ,a Z ,b N være givet, lad Z være et sæt af heltal, og N være et sæt naturlige tal. Delelig íàb med resten a =b · q +r , ãäår ligger i intervallet 0≤ r< b ,q неполное частное,r остаток. Например, 7 = 2· 3 + 1.

Sætning 1. For ethvert heltal a og naturligt tal b, repræsentationen

a = b q+ r,0 ≤ r< b

kun.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Eksistens.

Lad os overveje uendeligt sæt tal (a − tb) , ãäåa ,b faste tal, t ethvert tal, t Z . Fra den vælger vi det mindste ikke-negative tal r =a − q · b. Lad os bevise, at r ligger indeni

0 ≤ r< b.

Lad dette tal ikke høre til dette interval. Så er den større end eller lig med b. Lad os konstruere et nyt tal r ′ =r−b =a−q·b−b =a−b (q +1).

Ud fra dette kan vi se følgende:

1) r ′ (a − tb);

2) r ′ ikke-negativ;

1 S.V. september 2012. Forelæsnings- og opgaverforløb. Distribueres frit. Kurset blev undervist på St. Petersburg State University of Aviation Administration (1997 1999; 2008 2011) og St. Petersburg State Pedagogical University (2002 2005).

3) r"< r .

Derfor ikke r , a r ′ er den mindste ikke-negativt tal fra mængden (a − tb), så er antagelsen r ≥ b falsk.

Eksistens er blevet bevist.

2. Unikhed.

Lad der være en anden repræsentation a =bq ′ +r ′ , forudsat at 0≤r′< b ;a ,b фиксированные числа,q Z . Т.е., мы можем разделить числоa íàb двумя способами, тогдаbq +r =bq ′ +r ′ . Flytning af vilkåreneñq i den ene retning, og сr i den anden, får vi b (q − q ′ ) =r ′ − r . Det ses,

÷òî (r′−r) .b. Hver af resten er mindre end b и

(r′ − r) . b. |r′ − r|< b

Følgelig er r ′ − r = 0, hvilket betyder r ′ =r èq =q ′ . Så det har vi bevist

at et tal kan divideres med et andet på en unik måde. Sætningen er blevet bevist.

Sætning 2. Hvis a .b èb .c , tòa .c , ãäåb, c ≠ 0.

a = b · q. b=ct

Derfor er a =c · qt. Per definition er det klart, at en .c.

Sætning 3. Lad ligheden a 1 +a 2 =b 1 +b 2 og tallene a 1, a 2, b 1 .d være opfyldt, så b 2 .d.

Ä î ê à ç à ò å ë ü ñ ò â î

a1 =d · t1,a2 =d · t2,b1 =d · t3. Lad os udtrykke b 2 ud fra sætningens betingelser b 2 = a 1 +a 2 − b 1 =d (t 1 +t 2 − t 3 ). Ved definitionen af delelighed er det klart, at b 2 .d .

2. Største fælles divisor

Î definition Hvis nummeret c er en divisor af tallet a èb, så kaldes tallet c en fælles divisor af tallet a èb.

Definition Den største af de fælles divisorer af tallene a èb kaldes den største fælles divisor (GCD) af tallene a èb.

Notation: (a, b) =d, ãäåa èb-tal, ad er den største almindelige

divisor af disse tal.

Lad os se på et eksempel for tallene 12 og 9. Lad os skrive alle divisorerne af 12 og alle divisorerne af 9 ned. For 12: 1, 2, 3, 4, 6 og 12; for 9: 1, 3 og 9; det er tydeligt, at de har fælles divisor 1 og 3. Lad os vælge den største af dem er 3. Således er (12, 9) = 3.

Definition To tal a og b kaldes coprime, hvis deres gcd er lig med 1.

Eksempel. Fordi (10,9)=1, så er 10 og 9 relativt primtal.

Denne definition kan udvides til et vilkårligt antal tal. Hvis (a, b, c, . . . ) = 1, så er tallene a, b, c, . . . gensidigt enkelt. For eksempel:

Î ï ð å ä ë å í è å. (a 1 , a 2 , ...a n ) er parvise coprimtal hvis gcd af et par lig med én(ai, a j) = 1,i ≠ j.

For eksempel: 12,17,11 er ikke kun relativt prime, men også parvise coprime.

Sætning 1. Hvis a .b , så er (a, b ) =b .

Ä î ê à ç à ò å ë ü ñ ò â î

Tallet b kan ikke divideres med et tal, der er større end sig selv. Derfor er b en GCD af èb .

Sætning 2. Lad der være en repræsentation a =bq +r (r er ikke nødvendigvis resten), så er (a, b) = (b, r).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Overvej enhver fælles divisor a èb c. Åñëa .c èb .c , tî

ved Sætning 1.3 r .c er t.å.c også en fælles divisor for b èr . Enhver fælles divisor a èb er en fælles divisor b èr.

2. Enhver fælles divisor b èr er en divisor af a. Det betyder, at de fælles divisorer a, b èb, r er sammenfaldende. Dette gælder også for GCD.

3. Euklids algoritme

For alle tal kan en èb ved hjælp af den euklidiske algoritme finde

Lad a ,b N være inputdataene for algoritmen, og (a, b ) =d N være outputtet.

		Bq 0	0 < r1 < b
		R 1 q 1	0 < r2 < r1
		R 2 q 2	0 < r3 < r2

	r i−2	R i−1 q i−1	0 < ri < ri− 1

	r n−2 = r n−1 q n−1 + r n		0 < rn < rn− 1
n+1	r n−1 = r nq n

Trin 1. Divider en íàb med resten a =bq 0 +r 1 , ãäå 0< r 1 < b . По теореме 2.2 (a, b ) = (b, r 1 ).

Trin 2. Divider b íàr 1 med resten b =r 1 q 1 +r 2 , ãäå 0< r 2 < r 1 . Ïî теореме 2.2 (b, r 1 ) = (r 1 , r 2 ).

Og så videre indtil det er helt delt. Fra ligestillingskæden

(a, b) = (b, r 1) = (r 1, r 2) = (r 2, r 3) =... = (r n− 2, r n− 1) = (r n− 1, r n) =r n

det følger, at den sidste rest, der ikke er nul, r n vil være den største almindelige divisord =r n = (a, b ). Fordi resten falder, så vil algoritmen fuldføres endeligt nummer trin.

Sætninger relateret til den euklidiske algoritme

Sætning 1. Gcd af to tal er delelig med enhver fælles divisor af disse

Åñëè (a, b) =d, òî (a c, c b) =d c, ãäå c fælles divisor a èb.

Ä î ê à ç à ò å ë ü ñ ò â î

Â indtastninger af den euklidiske algoritme a, b и âñår jeg vil dele os. Vi får

registrering af den euklidiske algoritme med inputdata a b

navn a		c èc. Ud fra det er det klart
navn a
	è c	er lig med c.

Sætning 2. Hvis to tal divideres med deres gcd, får vi relativt primtal (a d, d b) = 1.

Ä î ê à ç à ò å ë ü ñ ò â î

Sætning 3. Hvis

I stedet for c (fra sætning 1) erstatter vi d.

(a, b) = 1, tòîc .b .ac. b

Ä î ê à ç à ò å ë ü ñ ò â î

For relativt primtal a èb er der ifølge sætning 7.1 en repræsentation ax +by = 1. Multiplicerer denne lighed med c, har vi ac ·x +byc =c,

íî ac =bq,bqx +byc =c,b (qx +yc) =c. Derfor er c.b.

GCD af flere numre

(a1, a2, . . . , an) = dn (a1, a2) = d2

(d 2 , a 3 ) = d 3

(d n− 1 , a n ) =d n

4. Mindste fælles multiplum

Î DEFINITION: Fælles multiplum af to tal a èb er et tal, der er deleligt med begge disse tal a èb.

Î DEFINITION: Mindste fælles multiplum a èb kaldes det mindste fælles multiplum (LCM) af en èb.

Lad M .a èM .b , så er M et fælles multiplum af en èb . Vi betegner det mindste fælles multiplum af en èb som .

Sætning 1. LCM af to tal lig med forholdet deres værker til

=(a, ab b) .

Ä î ê à ç à ò å ë ü ñ ò â î

Lad os betegne et fælles multiplum af tallene a èb med M , derefter M .

a èM .b . Derudover er d = (a, b),a =a ′ d,b =b ′ d, og (a ′, b ′) = 1. Per definition af delelighed M =a · k, ãäåk Z




					a′ dk				a′ k
					b′ d				b′

a ′ er ikke deleligt med b ′ , fordi de er relativt primtal, derfor k .b ′ fra sætning 3.3

k = b′ t=




M = a · k=
					(a, b)

form af ethvert fælles multiplum af en èb. Ïðèt = 1M er LCM for tallet a èb.

LCM af flere numre

[a1, a2, . . . , an] = Mn [a1, a2] = M2

M3 = M4

Åñëè (a, b) = 1, tòî =ab. Pr (ai, aj) = 1,i ≠ j,M =a1a2·. . . · en n .

5. Primtal og sammensatte tal

Ethvert tal er deleligt med 1 og sig selv. Lad os kalde disse divisorer trivielle.

Definition: Et tal kaldes primtal, hvis det ikke har nogen ikke-trivielle divisorer. Et tal kaldes sammensat, hvis det har en ikke-trivial divisor. Tallet 1 er hverken primtal eller sammensat.

Sætning 1. For ethvert naturligt tal a og primtal p

er opfyldt eller (a, p ) = 1 èëèa .p .

Ä î ê à ç à ò å ë ü ñ ò â î

Primtallet p har to trivielle divisorer. Muligt

to muligheder: a .p èëèa ̸ .p . Åñëèa ̸ .p , så er GCD for èp 1. Derfor er (a, p ) = 1.

Sætning 2. Den mindste divisor af et heltal forskelligt fra et, større end én, er et primtal.

Ä î ê à ç à ò å ë ü ñ ò â î

Åñëè a ≠ 1, òîa =p·q , ãäåp er den mindste ikke-trivielle divisor. Antag, at p er et sammensat tal. Det betyder, at der er

sådan et tal s , ÷òîp .s , men så er et .s èp ikke mindste divisor, hvilket strider mod betingelsen. T.o.p er et primtal.

Sætning 3. Mindste ikke-trivial divisor komposit nummer ikke overstiger sin rod.

Ä î ê à ç à ò å ë ü ñ ò â î

a = q b, q ≤ b, q2 ≤ bq= a, q ≤ a.

Sigte af Eratosthenes

Lad os skrive mængden af naturlige tal ned

1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 , . . .

Enheden er specialnummer. Vi fortsætter med de resterende tal på følgende måde: tag et tal, erklær det som primtal og streg multiplerne af det ud.

For eksempel er 2 et primtal, vi overstreger de tal, der er multipla af to, derfor vil der ikke være lige tal tilbage. Lad os gøre det samme med de tre. Du skal overstrege 6, 9, 12, 15, 18 osv. Alle resterende tal er primtal.

Sætning 4. Sættet af primtal er uendeligt. Bevis

Lad ( 2, 3, 5, . . . , P) være et endeligt sæt af primtal og N = 2· 3· 5·. . .·P +1.N er ikke delelig med nogen af primtallene, fordi når den divideres, er resten 1. Men den mindste ikke-trivielle divisor N ifølge sætning 2 er et primtal 2(, 3, 5, . . . , P). Følgelig er antallet af primtal ikke en endelig mængde, men en uendelig.

6. Kanonisk form af tallet

Sætning 1 (Fundamental Theorem of Arithmetic). Ethvert andet tal end 1 kan kun repræsenteres som et produkt af primtal.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Eksistens.

Tallet n, ved sætning 5.2, har en primdivisor p 1

nn1 = p1.

Lignende ræsonnement er gyldigt for tallet n 1

n2 = n1,p 2

åå s 2 prime divisor n 1. Og vi fortsætter på denne måde, indtil vi får n i = 1.

2. Unikhed.

Lad tallet n have to primtalsnedbrydninger

n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs.

Uden tab af generelitet accepterer vi l ≤ s. Hvis venstre side lighed er delelig med 1, så er den højre også delelig med 1. Det betyder, at nogle q i =p 1 . Lad det være q 1 =p 1 . Divider begge sider af ligheden med 1

På samme måde, lad os acceptere q2 = p2. Vi fortsætter denne procedure, indtil udtrykket tager formen

1 = ql +1 · . . . · qs.

Åñëè l< s , то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числаn невер-

íî. Åsëè s =l , tòp i =q i äëÿi og de to udvidelser falder sammen. Sætningen er blevet bevist.

Ethvert tal n N kan skrives i kanonisk form

n = p1 s 1 · . . . · pl s l ,

L p i er primtal, s i N .

Den kanoniske repræsentation giver dig mulighed for at nedskrive alle divisorerne for et tal og bestemme GCD og LCM.

Alle divisorer c af tallet n har formen

c = p1i1 · p2i2. . . pl i l ,ãäå ij .

Finde GCD og LCM

Lad tallene a og b være repræsenteret i formen

a = p1 s 1 · p2 s 2 · . . . · pl s l b= p1 t 1 · p2 t 2 · . . . · pl t l .

Denne repræsentation adskiller sig fra den kanoniske ved, at nogle s i и t i kan være lig med 0.

Derefter den største fælles divisor a èb

(a, b) = p1 min (s1,t1) · p2 min (s2,t2) ·. . . · pl min (s l ,t l ),

og det mindste fælles multiplum er:

[a, b] = p1 max (s 1 , t 1 ) · p2 max (s 2 , t 2 ) · . . . · pl max (s l ,t l ).

Herfra er det også klart, at (a, b) er delelig med enhver fælles divisor a èb.

7. Lineære diofantiske ligninger med to ukendte

Î D e ﬁ nition En lineær diofantligning med to ubekendte er en ligning af formen

axe + by= c,

hvor koefficienterne a, b, c og de ukendte x, y er heltal, aa og b er ikke lig med nul på samme tid.

Sætning 1 (Om den lineære repræsentation af GCD). For ethvert talpar (a, b) ((a, b) ≠ (0, 0)) er der sådanne x, y Z, ÷òîax +by =(a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

Overvej sættet af tal (ax + by) og vælg minimum fra det positivt tal d = ax 0 + gange 0 .

Lad os bevise, at d er en divisor af b.

Lad d ikke være en divisorb, derfor,b =d q +r, ãäå 0< r < d ,

r = b − dq= b −(ax0 + by0 ) q= a(−x0 q) + b(1 − y0 q). Det er klart, at:

1) tal r (ax +by) ;

2) r er positiv;

3)r< d .

Men vi antog, at d er det mindste positive tal fra dette sæt, deraf vores antagelse, at r< d неверно, значитd делительb .

På samme måde kan vi bevise, at en .d.

Af alt dette følger, at d er en fælles divisor af en èb.

en. (a, b)

Kostak, f. (a, b) d. (a, b), íîd er fælles divisor for en èb, derfor d ÍÎÄ a è b.

Sætning 2. Ligningen ax +by =c har en løsning, hvis og kun ifc er delelig med (a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Ladec. (a, b), derefter ved sætning 1 økse+ved= (a, b). Gang ligningen med c

( a,b )

-en (en,xcb) + b (en,ycb) = c.

Et par tal ( x0 , y0 ) vil være en løsning på den oprindelige ligning

{ x0 = (a,bxc)y0 = (a,byc).

2. Lad os bevise, at hvis ligningen har en løsning, så c. (a, b).

-en. (a, b) , derfor, c skal også være deleligt med ( a, b).

b . ( a, b )