Koprime-luvut

Koprime-luvut ovat kokonaislukuja , joilla ei ole muita yhteisiä jakajia kuin ±1. Vastaava määritelmä [1] : kokonaisluvut ovat yhteislukuja , jos niiden suurin yhteinen jakaja (gcd) on 1 .

Esimerkiksi luvut 14 ja 25 ovat alkulukuja, koska niillä ei ole yhteisiä jakajia; mutta luvut 15 ja 25 eivät ole alkulukuja, koska niillä on yhteinen jakaja 5.

Numeroiden ja :n suhteellisen yksinkertaisuuden osoittamiseksi käytetään joskus merkintää (analogia kohtisuorien viivojen kanssa, joilla ei ole yhteisiä suuntia - suhteellisen alkuluvuilla ei ole yhteisiä kertoimia [2] ). $m$ $n$ $m\perp n$

Tämä käsite esiteltiin kirjassa VII Euclid's Elements . Euklidesin algoritmia voidaan käyttää määrittämään, ovatko kaksi lukua koprime .

Yksinkertaisuuden käsite yleistyy luonnollisesti kaikkiin eukleideen renkaisiin .

Parittaiset koprime-luvut

Jos kokonaislukujoukossa mitkä tahansa kaksi lukua ovat yhteislukua, niin tällaisia lukuja kutsutaan parittaiseksi alkuluvuksi (tai yksinkertaisesti parittaiseksi alkuluvuksi [3] ). Kahden luvun käsitteet "koprime" ja "pairwise alkuluku" ovat samat, useammalle kuin kahdelle luvulle parittaisen yksinkertaisuuden ominaisuus on vahvempi kuin aiemmin määritelty keskinäisen yksinkertaisuuden ominaisuus (yhteenlaskettuna) - parittaiset alkuluvut olla myös koprime, mutta päinvastoin ei pidä paikkaansa [3 ] . Esimerkkejä:

8, 15 eivät ole alkulukuja, vaan koprime.
6, 8, 9 ovat keskenään alkulukuja (kollektiivisia), mutta eivät parittaisia alkulukuja.
8, 15, 49 ovat pareittain alkuluku ja koprime (yhdessä).

Jos luvut ovat pareittain alkulukuja, niin: $a_1, \ldots , a_n$

niiden pienin yhteinen kerrannainen on yhtä suuri kuin heidän tuotteensa itseisarvo : ; $|a_{1}\cdot \ldots \cdot a_{n}|$
mille tahansa kokonaisluvulle kaava [4] pätee : $b$

NOD NOD NOD NOD ,

(a_{1}\cdot a_{2}\ldots a_{n},b)=

{\näyttötyyli (a_{1},b)}

{\näyttötyyli (a_{2},b)\pisteet }

{\näyttötyyli (a_{n},b)}

missä gcd on suurin yhteinen jakaja .

Ominaisuudet

Kaikkien tässä osiossa mainittujen lukujen oletetaan olevan kokonaislukuja, ellei toisin mainita.

Niiden luonnollisten lukujen lukumäärä, jotka ovat suhteellisen alkulukuja luonnolliseen lukuun nähden , saadaan Euler-funktiolla . $n$ $\varphi (n)$

Numerot ja ovat koprime , jos ja vain jos on kokonaislukuja ja sellaisia, että ( Bezoutin relaatio ) [1] . Jos luonnolliset luvut ja ovat koprime, niin luvut ja ovat myös koprime, ja päinvastoin on myös totta. $a$ $b$ $x$ $y$ $ax+by=1$ $a$ $b$ $2^{a}-1$ $2^{b}-1$

( Euklidesin Lemma ) Jos on tuotteen jakaja ja koprime kanssa , niin on luvun jakaja . $a$ $eKr$ $a$ $b$ $a$ $c$

Jos gcd , niin luvut ja ovat koprime. $d=$ $(a, b)$ ${\frac {a}{d))$ ${\frac {b}{d))$

Murtoluku on redusoitumaton , jos ja vain jos sen osoittaja ja nimittäjä ovat alkuluku.

Jos luvut ja ovat suhteellisen alkulukuja, niin minkä tahansa kongruenssilla on ainutlaatuinen ratkaisu [5] modulo Erityisesti kongruenssin ratkaisu antaa jäännösrenkaassa käänteisalkio for modulo m . (Katso Bezout-suhde ) $a$ $m$ $ax\equiv b{\pmod {m))$ $b$ $m.$ $b = 1$ $a$

Todennäköisyys, että satunnaisesti valitut positiiviset kokonaisluvut ovat koprime , on siinä mielessä, että , todennäköisyys, että positiiviset kokonaisluvut, jotka ovat pienempiä kuin (ja satunnaisesti valitut) ovat koprime, on yleensä . Tässä on Riemannin zeta - funktio . $k$ $\dfrac{1} {\zeta(k)}$ $N\to \infty$ $k$ ${\tekstityyli {N}}$ $\dfrac{1} {\zeta(k)}$ $\zeta (k)$

Taulukko koprime-luvuista 30 asti

Jokainen solu sisältää koordinaattiensa suurimman yhteisen jakajan , ja koordinaattipareja vastaavat yksiköt on korostettu tummalla. Yllä kuvatusta ominaisuudesta seuraa, että tummien solujen keskimääräinen tiheys, kun taulukkoa laajennetaan äärettömyyteen, tulee yhtä suureksi kuin . $1/\zeta (2)$

	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen	yksitoista	12	13	neljätoista	viisitoista	16	17	kahdeksantoista	19	kaksikymmentä	21	22	23	24	25	26	27	28	29	kolmekymmentä
yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi
2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2
3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3	yksi	yksi	3
neljä	yksi	2	yksi	neljä	yksi	2	yksi	neljä	yksi	2	yksi	neljä	yksi	2	yksi	neljä	yksi	2	yksi	neljä	yksi	2	yksi	neljä	yksi	2	yksi	neljä	yksi	2
5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5
6	yksi	2	3	2	yksi	6	yksi	2	3	2	yksi	6	yksi	2	3	2	yksi	6	yksi	2	3	2	yksi	6	yksi	2	3	2	yksi	6
7	yksi	yksi	yksi	yksi	yksi	yksi	7	yksi	yksi	yksi	yksi	yksi	yksi	7	yksi	yksi	yksi	yksi	yksi	yksi	7	yksi	yksi	yksi	yksi	yksi	yksi	7	yksi	yksi
kahdeksan	yksi	2	yksi	neljä	yksi	2	yksi	kahdeksan	yksi	2	yksi	neljä	yksi	2	yksi	kahdeksan	yksi	2	yksi	neljä	yksi	2	yksi	kahdeksan	yksi	2	yksi	neljä	yksi	2
9	yksi	yksi	3	yksi	yksi	3	yksi	yksi	9	yksi	yksi	3	yksi	yksi	3	yksi	yksi	9	yksi	yksi	3	yksi	yksi	3	yksi	yksi	9	yksi	yksi	3
kymmenen	yksi	2	yksi	2	5	2	yksi	2	yksi	kymmenen	yksi	2	yksi	2	5	2	yksi	2	yksi	kymmenen	yksi	2	yksi	2	5	2	yksi	2	yksi	kymmenen
yksitoista	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksitoista	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksitoista	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi
12	yksi	2	3	neljä	yksi	6	yksi	neljä	3	2	yksi	12	yksi	2	3	neljä	yksi	6	yksi	neljä	3	2	yksi	12	yksi	2	3	neljä	yksi	6
13	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	13	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	13	yksi	yksi	yksi	yksi
neljätoista	yksi	2	yksi	2	yksi	2	7	2	yksi	2	yksi	2	yksi	neljätoista	yksi	2	yksi	2	yksi	2	7	2	yksi	2	yksi	2	yksi	neljätoista	yksi	2
viisitoista	yksi	yksi	3	yksi	5	3	yksi	yksi	3	5	yksi	3	yksi	yksi	viisitoista	yksi	yksi	3	yksi	5	3	yksi	yksi	3	5	yksi	3	yksi	yksi	viisitoista
16	yksi	2	yksi	neljä	yksi	2	yksi	kahdeksan	yksi	2	yksi	neljä	yksi	2	yksi	16	yksi	2	yksi	neljä	yksi	2	yksi	kahdeksan	yksi	2	yksi	neljä	yksi	2
17	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	17	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi
kahdeksantoista	yksi	2	3	2	yksi	6	yksi	2	9	2	yksi	6	yksi	2	3	2	yksi	kahdeksantoista	yksi	2	3	2	yksi	6	yksi	2	9	2	yksi	6
19	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	19	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi
kaksikymmentä	yksi	2	yksi	neljä	5	2	yksi	neljä	yksi	kymmenen	yksi	neljä	yksi	2	5	neljä	yksi	2	yksi	kaksikymmentä	yksi	2	yksi	neljä	5	2	yksi	neljä	yksi	kymmenen
21	yksi	yksi	3	yksi	yksi	3	7	yksi	3	yksi	yksi	3	yksi	7	3	yksi	yksi	3	yksi	yksi	21	yksi	yksi	3	yksi	yksi	3	7	yksi	3
22	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksitoista	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	22	yksi	2	yksi	2	yksi	2	yksi	2
23	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	23	yksi	yksi	yksi	yksi	yksi	yksi	yksi
24	yksi	2	3	neljä	yksi	6	yksi	kahdeksan	3	2	yksi	12	yksi	2	3	kahdeksan	yksi	6	yksi	neljä	3	2	yksi	24	yksi	2	3	neljä	yksi	6
25	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	5	yksi	yksi	yksi	yksi	25	yksi	yksi	yksi	yksi	5
26	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	13	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	2	yksi	26	yksi	2	yksi	2
27	yksi	yksi	3	yksi	yksi	3	yksi	yksi	9	yksi	yksi	3	yksi	yksi	3	yksi	yksi	9	yksi	yksi	3	yksi	yksi	3	yksi	yksi	27	yksi	yksi	3
28	yksi	2	yksi	neljä	yksi	2	7	neljä	yksi	2	yksi	neljä	yksi	neljätoista	yksi	neljä	yksi	2	yksi	neljä	7	2	yksi	neljä	yksi	2	yksi	28	yksi	2
29	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	29	yksi
kolmekymmentä	yksi	2	3	2	5	6	yksi	2	3	kymmenen	yksi	6	yksi	2	viisitoista	2	yksi	6	yksi	kymmenen	3	2	yksi	6	5	2	3	2	yksi	kolmekymmentä

Muunnelmia ja yleistyksiä

Alkuluvun , suurimman yhteisen jakajan ja koprime-lukujen käsitteet yleistyvät luonnollisesti mielivaltaisiin eukleideen renkaisiin , kuten polynomirenkaaseen tai Gaussin kokonaislukuihin . Alkuluvun käsitteen yleistys on " pelkistymätön elementti ". Yllä oleva koprime-lukujen määritelmä ei sovellu mielivaltaiselle euklidiselle renkaalle, koska renkaassa voi olla yksikköjakajia ; erityisesti GCD määritellään yksikön jakajalla kertomiseen asti. Siksi suhteellisen alkulukujen määritelmää tulisi muuttaa [6] .

Euklidisen renkaan elementtien sanotaan olevan koprime, jos niiden suurimpien yhteisten jakajien joukko sisältää vain yksikköjakajia.

Vastaavat formulaatiot [6] :

Euklidisen renkaan alkiot ovat alkulukuja, jos niillä ei ole muita yhteisiä jakajia kuin yksikköjakajia.
( Bezoutin relaatio ) Euklidisen renkaan alkiot ovat koprime , jos ja vain jos on sellaisia elementtejä , että $a,b$ $K$ $u,v\in K$ $au+vb=1.$

Eukleideen lemma pätee myös .

Käytännön sovellus

Keskinäisen yksinkertaisuuden ominaisuudella ei ole vain tärkeä rooli lukuteoriassa ja kommutatiivisessa algebrassa , vaan sillä on useita tärkeitä käytännön sovelluksia, erityisesti ketjupyörien hampaiden lukumäärä ja ketjun lenkkien lukumäärä ketjukäytössä ovat yleensä suhteellisen suhteellisia. prime, joka varmistaa tasaisen kulumisen: ketjupyörän jokainen hammas toimii vuorotellen kaikkien ketjun lenkkien kanssa.

Muistiinpanot

↑ 1 2 Koprime-luvut. // Mathematical Encyclopedia (5 osassa). - M .: Neuvostoliiton tietosanakirja , 1977. - T. 1. - S. 690.
↑ R. Graham, D. Knuth, O. Patashnik. Konkreettinen matematiikka . - M . : "Mir", 1998. - S. 139 . - 703 s. — ISBN 5-03-001793-3 .
↑ 1 2 Mikhelovich, 1967 , s. 28.
↑ Nesterenko Yu. V. Numeroteoria . - M . : Publishing Center "Academy", 2008. - S. 40. - 272 s. — ISBN 9785769546464 .
↑ Mikhelovich, 1967 , s. 64.
↑ 1 2 Larin S. V. Algebra ja lukuteoria. Ryhmät, renkaat ja kentät: oppikirja. akateemisen ylioppilastutkinnon käsikirja. - 2. painos - M. : Yurait, 2018. - S. 92-93. – 160 s. — (kandidaatti. Akateeminen kurssi). - ISBN 978-5-534-05567-2 .

Kirjallisuus

Alkuperäiset numerot // Suuri Neuvostoliiton tietosanakirja : 66 nidettä (65 osaa ja 1 lisäosa) / ch. toim. O. Yu. Schmidt . - M . : Neuvostoliiton tietosanakirja , 1926-1947.
Mikhelovich Sh. Kh. Numeroteoria . - 2. painos - M . : Korkeakoulu, 1967. - 336 s.