Coprime čísla

Dvojnásobná čísla jsou celá čísla , která nemají žádného společného dělitele kromě ±1. Ekvivalentní definice [1] : celá čísla jsou dvojčlenná , pokud jejich největší společný dělitel (gcd) je 1 .

Například čísla 14 a 25 jsou koprimá, protože nemají žádné společné dělitele; ale čísla 15 a 25 nejsou koprimá, protože mají společného dělitele 5.

K označení relativní jednoduchosti čísel a , se někdy používá zápis (obdoba s kolmými úsečkami, které nemají společný směr - relativně prvočísla nemají společné činitele [2] ). $m$ $n$ $m\perp n$

Toto pojetí bylo představeno v knize VII Euclid's Elements . Euklidův algoritmus lze použít k určení, zda jsou dvě čísla coprime .

Pojem cosimplicita přirozeně zobecňuje na jakékoli euklidovské kruhy .

Párová prvočísla

Jestliže v množině celých čísel jsou některá dvě čísla coprime, pak se taková čísla nazývají párové coprime (nebo jednoduše párové prvočíslo [3] ). Pro dvě čísla jsou pojmy „koprime“ a „párové prvočíslo“ stejné, pro více než dvě čísla je vlastnost párové jednoduchosti silnější než dříve definovaná vlastnost vzájemné jednoduchosti (v souhrnu) – párová prvočísla budou být také coprime, ale obráceně to není pravda [3] . Příklady:

8, 15 nejsou prvočíslo, ale koprime.
6, 8, 9 jsou vzájemně prvočísla (souhrnně), ale ne párová prvočísla.
8, 15, 49 jsou párová prvočísla a koprimá (společně).

Pokud jsou čísla párová prvočísla, pak: $a_1, \ldots , a_n$

jejich nejmenší společný násobek se rovná absolutní hodnotě jejich součinu: ; $|a_{1}\cdot \ldots \cdot a_{n}|$
pro libovolné celé číslo platí vzorec [4] : $b$

NOD NOD NOD NOD ,

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

(a_{1},b)

(a_{2},b)\tečky

(a_{n},b)

kde gcd je největší společný dělitel .

Vlastnosti

Všechna čísla uvedená v této části jsou považována za celá čísla, pokud není uvedeno jinak.

Počet přirozených čísel, která jsou relativně prvočísla k přirozenému číslu , je dán Eulerovou funkcí . $n$ $\varphi (n)$

Čísla a jsou coprime právě tehdy, když existují celá čísla a taková, že ( Bezoutův vztah ) [1] . Jestliže přirozená čísla a jsou coprime, pak čísla a jsou také coprime, a obráceně je to také pravda. $A$ $b$ $X$ $y$ $ax+by=1$ $A$ $b$ $2^{a}-1$ $2^{b}-1$

( Euklidovo lemma ) Jestliže je dělitelem součinu a je spojeno s , potom je dělitelem . $A$ $před naším letopočtem$ $A$ $b$ $A$ $C$

Pokud gcd , pak čísla a jsou coprime. $d=$ $(a,b)$ ${\frac {a}{d))$ ${\frac {b}{d))$

Zlomek je neredukovatelný právě tehdy, když jeho čitatel a jmenovatel jsou coprime.

Jsou-li čísla a relativně prvočísla, pak kongruence pro libovolné má jedinečné řešení [5] modulo Konkrétně řešení kongruence pro dává inverzní prvek for v kruhu zbytků modulo m . (Viz vztah Bezouta ) $A$ $m$ $ax\equiv b{\pmod {m))$ $b$ $m$ $b=1$ $A$

Pravděpodobnost, že náhodně vybraná kladná celá čísla budou coprime, je , v tom smyslu, že pro , pravděpodobnost, že kladná celá čísla menší než (a náhodně vybraná) budou coprime, má tendenci k . Zde je Riemannova funkce zeta . $k$ $\dfrac{1} {\zeta(k)}$ $N\to \infty$ $k$ ${\textstyle {N}}$ $\dfrac{1} {\zeta(k)}$ $\zeta (k)$

Tabulka hlavních čísel do 30

Každá buňka obsahuje největšího společného dělitele svých souřadnic a jednotky odpovídající společným dvojicím souřadnic jsou zvýrazněny tmavou barvou. Z výše popsané vlastnosti vyplývá, že průměrná hustota tmavých buněk při roztažení tabulky do nekonečna se rovná . $1/\zeta (2)$

	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet	21	22	23	24	25	26	27	28	29	třicet
jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden
2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2
3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3	jeden	jeden	3
čtyři	jeden	2	jeden	čtyři	jeden	2	jeden	čtyři	jeden	2	jeden	čtyři	jeden	2	jeden	čtyři	jeden	2	jeden	čtyři	jeden	2	jeden	čtyři	jeden	2	jeden	čtyři	jeden	2
5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5
6	jeden	2	3	2	jeden	6	jeden	2	3	2	jeden	6	jeden	2	3	2	jeden	6	jeden	2	3	2	jeden	6	jeden	2	3	2	jeden	6
7	jeden	jeden	jeden	jeden	jeden	jeden	7	jeden	jeden	jeden	jeden	jeden	jeden	7	jeden	jeden	jeden	jeden	jeden	jeden	7	jeden	jeden	jeden	jeden	jeden	jeden	7	jeden	jeden
osm	jeden	2	jeden	čtyři	jeden	2	jeden	osm	jeden	2	jeden	čtyři	jeden	2	jeden	osm	jeden	2	jeden	čtyři	jeden	2	jeden	osm	jeden	2	jeden	čtyři	jeden	2
9	jeden	jeden	3	jeden	jeden	3	jeden	jeden	9	jeden	jeden	3	jeden	jeden	3	jeden	jeden	9	jeden	jeden	3	jeden	jeden	3	jeden	jeden	9	jeden	jeden	3
deset	jeden	2	jeden	2	5	2	jeden	2	jeden	deset	jeden	2	jeden	2	5	2	jeden	2	jeden	deset	jeden	2	jeden	2	5	2	jeden	2	jeden	deset
jedenáct	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jedenáct	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jedenáct	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden
12	jeden	2	3	čtyři	jeden	6	jeden	čtyři	3	2	jeden	12	jeden	2	3	čtyři	jeden	6	jeden	čtyři	3	2	jeden	12	jeden	2	3	čtyři	jeden	6
13	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	13	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	13	jeden	jeden	jeden	jeden
čtrnáct	jeden	2	jeden	2	jeden	2	7	2	jeden	2	jeden	2	jeden	čtrnáct	jeden	2	jeden	2	jeden	2	7	2	jeden	2	jeden	2	jeden	čtrnáct	jeden	2
patnáct	jeden	jeden	3	jeden	5	3	jeden	jeden	3	5	jeden	3	jeden	jeden	patnáct	jeden	jeden	3	jeden	5	3	jeden	jeden	3	5	jeden	3	jeden	jeden	patnáct
16	jeden	2	jeden	čtyři	jeden	2	jeden	osm	jeden	2	jeden	čtyři	jeden	2	jeden	16	jeden	2	jeden	čtyři	jeden	2	jeden	osm	jeden	2	jeden	čtyři	jeden	2
17	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	17	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden
osmnáct	jeden	2	3	2	jeden	6	jeden	2	9	2	jeden	6	jeden	2	3	2	jeden	osmnáct	jeden	2	3	2	jeden	6	jeden	2	9	2	jeden	6
19	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	19	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden
dvacet	jeden	2	jeden	čtyři	5	2	jeden	čtyři	jeden	deset	jeden	čtyři	jeden	2	5	čtyři	jeden	2	jeden	dvacet	jeden	2	jeden	čtyři	5	2	jeden	čtyři	jeden	deset
21	jeden	jeden	3	jeden	jeden	3	7	jeden	3	jeden	jeden	3	jeden	7	3	jeden	jeden	3	jeden	jeden	21	jeden	jeden	3	jeden	jeden	3	7	jeden	3
22	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jedenáct	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	22	jeden	2	jeden	2	jeden	2	jeden	2
23	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	23	jeden	jeden	jeden	jeden	jeden	jeden	jeden
24	jeden	2	3	čtyři	jeden	6	jeden	osm	3	2	jeden	12	jeden	2	3	osm	jeden	6	jeden	čtyři	3	2	jeden	24	jeden	2	3	čtyři	jeden	6
25	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	5	jeden	jeden	jeden	jeden	25	jeden	jeden	jeden	jeden	5
26	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	13	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	2	jeden	26	jeden	2	jeden	2
27	jeden	jeden	3	jeden	jeden	3	jeden	jeden	9	jeden	jeden	3	jeden	jeden	3	jeden	jeden	9	jeden	jeden	3	jeden	jeden	3	jeden	jeden	27	jeden	jeden	3
28	jeden	2	jeden	čtyři	jeden	2	7	čtyři	jeden	2	jeden	čtyři	jeden	čtrnáct	jeden	čtyři	jeden	2	jeden	čtyři	7	2	jeden	čtyři	jeden	2	jeden	28	jeden	2
29	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	29	jeden
třicet	jeden	2	3	2	5	6	jeden	2	3	deset	jeden	6	jeden	2	patnáct	2	jeden	6	jeden	deset	3	2	jeden	6	5	2	3	2	jeden	třicet

Variace a zobecnění

Pojmy prvočísla , největšího společného dělitele a prvočíselných čísel přirozeně zobecňují na libovolné euklidovské kruhy , jako je polynomický kruh nebo Gaussova celá čísla . Zobecněním pojmu prvočíslo je „ neredukovatelný prvek “. Výše uvedená definice společných čísel není vhodná pro libovolný euklidovský kruh, protože v kruhu mohou být jednotkové dělitele ; konkrétně GCD je definováno až po násobení dělitelem jednoty. Proto by měla být upravena definice relativně prvočísel [6] .

O prvcích euklidovského kruhu se říká, že jsou coprime, pokud množina jejich největších společných dělitelů obsahuje pouze jednotkové dělitele.

Ekvivalentní formulace [6] :

Prvky euklidovského kruhu jsou coprime, pokud nemají žádné společné dělitele jiné než jednotkové.
( Bezoutův vztah ) Prvky euklidovského kruhu jsou koprimé právě tehdy , když existují prvky takové , že $a,b$ $K$ $u,v\in K$ $au+vb=1.$

Euklidovo lemma také platí .

Praktická aplikace

Vlastnost vzájemné jednoduchosti hraje důležitou roli nejen v teorii čísel a komutativní algebře , ale má řadu důležitých praktických aplikací, zejména počet zubů na řetězových kolech a počet článků řetězu v řetězovém pohonu bývá relativně prime, který zajišťuje rovnoměrné opotřebení: každý zub řetězového kola bude pracovat postupně se všemi články řetězu.

Poznámky

↑ 1 2 Coprime čísla. // Matematická encyklopedie (v 5 svazcích). - M .: Sovětská encyklopedie , 1977. - T. 1. - S. 690.
↑ R. Graham, D. Knuth, O. Patashnik. Konkrétní matematika . - M .: "Mir", 1998. - S. 139 . - 703 s. — ISBN 5-03-001793-3 .
↑ 1 2 Mikhelovič, 1967 , str. 28.
↑ Nesterenko Yu.V. Teorie čísel. - M . : Publikační středisko "Akademie", 2008. - S. 40. - 272 s. — ISBN 9785769546464 .
↑ Mikhelovič, 1967 , s. 64.
↑ 1 2 Larin S. V. Algebra a teorie čísel. Skupiny, kroužky a obory: učebnice. manuál pro akademické bakaláře. - 2. vyd. - M. : Yurait, 2018. - S. 92-93. — 160 s. — (Bakalářský. Akademický kurz). - ISBN 978-5-534-05567-2 .

Literatura

Coprime čísla // Velká sovětská encyklopedie : v 66 svazcích (65 svazků a 1 doplňkový) / kap. vyd. O. Yu Schmidt . - M .: Sovětská encyklopedie , 1926-1947.
Mikhelovič Sh. Kh. Teorie čísel. - 2. vyd. - M . : Vyšší škola, 1967. - 336 s.