Nesoudělná čísla - Coprime integers

v teorie čísel, dva celá čísla $A$ a $b$ jsou relativně prime, vzájemně připravit,^[1] nebo coprime pokud je jediné kladné celé číslo, které se rovnoměrně dělí (je a dělitel z) oba jsou 1. Jeden říká také $A$ je hlavní $b$ nebo $A$ je coprime s $b$ . V důsledku toho jakýkoli prvočíslo který rozděluje jednu z $A$ nebo $b$ nerozdělí druhého. To odpovídá jejich největší společný dělitel (gcd) je 1.^[2]

Čitatel a jmenovatel a redukovaný zlomek jsou coprime. Čísla 14 a 25 jsou coprime, protože 1 je jejich jediný společný dělitel. Na druhou stranu 14 a 21 nejsou coprime, protože jsou obě dělitelné 7.

Zápis a testování

Standardní notace pro relativně primární celá čísla $A$ a $b$ jsou: $gcd (A, b) = 1$ a $(A, b) = 1$ . V článku z roku 1989 Graham, Knuth, a Patashnik navrhl, že zápis ${displaystyle aperp b}$ k označení toho $A$ a $b$ jsou relativně prime a že termín "prime" může být použit místo coprime (jako v $A$ je primární na $b$ ).^[3]

Rychlý způsob, jak zjistit, zda jsou dvě čísla coprime, je dán Euklidovský algoritmus a jeho rychlejší varianty, jako je binární algoritmus GCD nebo Lehmerův GCD algoritmus.

Počet celých čísel společně s kladným celým číslem $n$ mezi 1 a $n$ , darováno Eulerova totientová funkce, známá také jako Eulerova funkce phi, $φ (n)$ .

A soubor celých čísel lze také volat coprime pokud jeho prvky nesdílejí žádný společný pozitivní faktor kromě 1. Silnější podmínka na množině celých čísel je dvojice coprime, což znamená, že $A$ a $b$ jsou coprime pro každý pár $(A, b)$ různých celých čísel v sadě. Sada ${2, 3, 4$ } je coprime, ale není to párový coprime, protože 2 a 4 nejsou relativně prime.

Vlastnosti

Čísla 1 a -1 jsou jediná celá čísla coprime s každým celým číslem a jsou to pouze celá čísla, která jsou coprime s 0.

Řada podmínek odpovídá $A$ a $b$ být coprime:

Ne prvočíslo rozděluje obě $A$ a $b$ .
Existují celá čísla $X$ a $y$ takhle $sekera + podle = 1$ (vidět Bézoutova identita ).
Celé číslo $b$ má multiplikativní inverzní modulo $A$ , což znamená, že existuje celé číslo $y$ takhle $podle \equiv 1 (mod A)$ . V kruhu-teoretický jazyk, $b$ je jednotka v prsten $Z / A Z$ z celá čísla modulo $A$ .
Každý pár kongruenční vztahy pro neznámé celé číslo $X$ , formuláře $X \equiv k (mod A)$ a $X \equiv m (mod b)$ , má řešení (Čínská věta o zbytku ); ve skutečnosti jsou řešení popsána jediným kongruenčním vztahem modulo $ab$ .
The nejmenší společný násobek z $A$ a $b$ se rovná jejich produktu $ab$ , tj. $lcm (A, b) = ab$ .^[4]

V důsledku třetího bodu, pokud A a b jsou coprime a br ≡ bs (mod A), pak r ≡ s (mod A).^[5] To znamená, že můžeme „rozdělit na b"při práci modulo A. Kromě toho, pokud b₁ a b₂ jsou oba coprime s A, pak také jejich produkt b₁b₂ (tj. modulo A je to produkt invertibilních prvků, a proto invertibilní);^[6] to rovněž vyplývá z prvního bodu Euklidovo lemma, který uvádí, že pokud je prvočíslo p rozděluje produkt před naším letopočtem, pak p rozděluje alespoň jeden z faktorů b, C.

V důsledku prvního bodu, pokud A a b jsou coprime, pak také jakékoli pravomoci A^k a b^m.

Li A a b jsou coprime a A rozděluje produkt před naším letopočtem, pak A rozděluje C.^[7] Lze to chápat jako zevšeobecnění Euklidova lematu.

Obrázek 1. Čísla 4 a 9 jsou coprime. Proto úhlopříčka mřížky 4 × 9 neprotíná žádnou jinou mřížové body

Dvě celá čísla A a b jsou coprime právě tehdy, když bod se souřadnicemi (A, b) v Kartézský souřadnicový systém je „viditelný“ z počátku (0,0), v tom smyslu, že na úsečce mezi počátkem a (A, b). (Viz obrázek 1.)

V jistém smyslu, který lze upřesnit, pravděpodobnost že dvě náhodně vybraná celá čísla jsou coprime, je 6 / π² (vidět pi ), což je přibližně 61%. Viz. níže.

Dva přirozená čísla A a b jsou coprime právě tehdy, když čísla 2^A - 1 a 2^b - 1 je coprime.^[8] Jako zevšeobecnění tohoto, snadno vyplývající z Euklidovský algoritmus v základna n > 1:

{displaystyle gcd left (n ^ {a} -1, n ^ {b} -1ight) = n ^ {gcd (a, b)} - 1.}

Coprimality v sadách

A soubor celých čísel S = {A₁, A₂, .... A_n} lze také volat coprime nebo setwise coprime pokud největší společný dělitel všech prvků množiny je 1. Například celá čísla 6, 10, 15 jsou coprime, protože 1 je jediné kladné celé číslo, které je všechny rozdělí.

Pokud je každý pár v množině celých čísel coprime, pak se říká, že množina je dvojice coprime (nebo párově relativně prime, vzájemně coprime nebo vzájemně relativně prime). Párová primalita je silnější podmínka než setimální primalita; každá párová coprime konečná množina je také setwise coprime, ale opak není pravdivý. Například celá čísla 4, 5, 6 jsou (setwise) coprime (protože jediné kladné celé dělení) Všechno z nich je 1), ale nejsou po párech coprime (protože gcd (4, 6) = 2).

Koncept párové komprimality je důležitý jako hypotéza u mnoha výsledků teorie čísel, jako je Čínská věta o zbytku.

Je možné pro nekonečná sada celých čísel, které mají být párové coprime. Pozoruhodné příklady zahrnují množinu všech prvočísel, množinu prvků v Sylvestrova sekvence a soubor všech Fermat čísla.

Coprimality v prstenových ideálech

Dva ideály A a B v komutativní prsten R jsou nazývány coprime (nebo komaximální) pokud A + B = R. To zobecňuje Bézoutova identita: s touto definicí, dva hlavní ideály (A) a (b) v kruhu celých čísel Z jsou coprime právě tehdy A a b jsou coprime. Pokud ideály A a B z R jsou tedy coprime AB = A∩B; dále, pokud C je třetí ideální takový A obsahuje před naším letopočtem, pak A obsahuje C. The Čínská věta o zbytku lze zobecnit na libovolný komutativní kruh pomocí ideálních principů.

Pravděpodobnost primitivity

Vzhledem k tomu, dvě náhodně vybraná celá čísla A a b, je rozumné se ptát, jak je to pravděpodobné A a b jsou coprime. V tomto stanovení je vhodné použít charakterizaci, která A a b jsou coprime právě tehdy, pokud je nerozdělí žádné prvočíslo (viz Základní věta o aritmetice ).

Neformálně pravděpodobnost, že jakékoli číslo je dělitelné prvočíslem (nebo ve skutečnosti jakýmkoli celým číslem) ${displaystyle p}$ je ${displaystyle 1 / p}$ ; například každé 7. celé číslo je dělitelné 7. Tudíž pravděpodobnost, že obě čísla jsou dělitelná p je ${displaystyle 1 / p ^ {2}}$ a pravděpodobnost, že alespoň jeden z nich není, je ${displaystyle 1-1 / p ^ {2}}$ . Jakákoli konečná sbírka dělitelných událostí spojených s odlišnými prvočísly je vzájemně nezávislá. Například v případě dvou událostí je číslo dělitelné prvočísly p a q právě když je dělitelný pq; druhá událost má pravděpodobnost 1 /pq. Pokud si člověk vytvoří heuristický předpoklad, že takové uvažování lze rozšířit na nekonečně mnoho dělicích událostí, vede se k odhadu, že pravděpodobnost, že dvě čísla jsou coprime, je dána součinem všech prvočísel,

{displaystyle prod _ {{ext {prime}} p} left (1- {frac {1} {p ^ {2}}} ight) = left (prod _ {{ext {prime}} p} {frac {1 } {1-p ^ {- 2}}} ight) ^ {- 1} = {frac {1} {zeta (2)}} = {frac {6} {pi ^ {2}}} cca 0,607927102 cca 61 \%.}

Tady ζ Odkazuje na Funkce Riemann zeta, totožnost vztahující se k produktu v prvočíslech ζ(2) je příkladem Produkt Euler a hodnocení ζ(2) jako π²/ 6 je Basilejský problém, vyřešeno Leonhard Euler v roce 1735.

Neexistuje způsob, jak náhodně zvolit kladné celé číslo, aby každé kladné celé číslo nastalo se stejnou pravděpodobností, ale výroky o „náhodně vybraných celých číslech“, jako jsou výše uvedená, lze formalizovat pomocí pojmu přirozená hustota. Pro každé kladné celé číslo N, nechť P_N je pravděpodobnost, že dvě náhodně vybraná čísla v ${displaystyle {1,2, ldots, N}}$ jsou coprime. Ačkoli P_N nikdy se nebude rovnat ${displaystyle 6 / pi ^ {2}}$ přesně, s prací^[9] jeden může ukázat, že v limitu jako ${displaystyle N o infty}$ , pravděpodobnost ${displaystyle P_ {N}}$ přístupy ${displaystyle 6 / pi ^ {2}}$ .

Obecněji pravděpodobnost k náhodně vybraná celá čísla jako coprime je ${displaystyle 1 / {zeta (k)}}$ .

Generování všech párů coprime

Pořadí generování párů coprime tímto algoritmem. První uzel (2,1) je označen červeně, jeho tři děti jsou zobrazeny oranžově, třetí generace je žlutá atd. V duhovém pořadí.

Všechny páry pozitivních čísel coprime ${displaystyle (m, n)}$ (s ${displaystyle m> n}$ ) lze uspořádat do dvou disjunktních úplných ternární stromy, jeden strom začíná od ${displaystyle (2,1)}$ (pro sudé-liché a liché-sudé páry),^[10] a další strom začíná od ${displaystyle (3,1)}$ (pro liché-liché páry).^[11] Děti každého vrcholu ${displaystyle (m, n)}$ jsou generovány následovně:

Pobočka 1: ${displaystyle (2m-n, m)}$
Větev 2: ${displaystyle (2m + n, m)}$
Větev 3: ${displaystyle (m + 2n, n)}$

Toto schéma je vyčerpávající a nepotřebné bez neplatných členů.

Aplikace

v konstrukce stroje rovnoměrná uniforma Ozubené kolo opotřebení se dosáhne výběrem počtu zubů obou ozubených kol, která jsou vzájemně spojena, aby byla relativně primitivní. Když je požadován převodový poměr 1: 1, může být mezi ně vloženo ozubené kolo relativně primární ke dvěma ozubeným kolům stejné velikosti.

V počítači kryptografie,nějaký Šifra Vernam stroje kombinovaly několik smyček pásky s klíčem různých délek. Mnoho rotorové stroje kombinovat rotory s různým počtem zubů.Takové kombinace fungují nejlépe, když je celá sada délek párově coprime.^[12]^[13]^[14]^[15]

Viz také

Superpartientní číslo

Poznámky

^ Eaton, James S. Pojednání o aritmetice. 1872. Lze stáhnout z: https://archive.org/details/atreatiseonarit05eatogoog
^ Hardy & Wright 2008, str. 6
^ Graham, R.L .; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics / A Foundation for Computer Science, Addison-Wesley, str. 115, ISBN 0-201-14236-8
^ Ruda 1988, str. 47
^ Niven & Zuckerman 1966, str. 22, Věta 2.3 (b)
^ Niven & Zuckerman 1966, str. 6, Věta 1.8
^ Niven & Zuckerman 1966, s. 7, Věta 1.10
^ Rosen 1992, str. 140
^ Tuto větu prokázal Ernesto Cesàro v roce 1881. Důkaz viz Hardy & Wright 2008 Věta 332
^ Saunders, Robert & Randall, Trevor (červenec 1994), „Rodokmen pythagorejských trojčat znovu navštíven“, Matematický věstník, 78: 190–193, doi:10.2307/3618576.
^ Mitchell, Douglas W. (červenec 2001), „Alternativní charakterizace všech primitivních pythagorovských trojic“, Matematický věstník, 85: 273–275, doi:10.2307/3622017.
^ Klaus Pommerening.„Kryptologie: klíčové generátory s dlouhými obdobími“.
^ David Mowry.„Německé šifrovací stroje druhé světové války“.2014.p. 16; p. 22.
^ Dirk Rijmenants."Počátky jednorázové podložky".
^ Gustavus J. Simmons.„Šifra Vernam-Vigenère“.

Reference

Hardy, G.H.; Wright, E.M. (2008), Úvod do teorie čísel (6. vydání), Oxford University Press, ISBN 978-0-19-921986-5
Niven, Ivan; Zuckerman, Herbert S. (1966), Úvod do teorie čísel (2. vyd.), John Wiley & Sons
Ore, Oystein (1988) [1948], Teorie čísel a její historieDover, ISBN 978-0-486-65620-5
Rosen, Kenneth H. (1992), Teorie elementárních čísel a její aplikace (3. vyd.), Addison-Wesley, ISBN 978-0-201-57889-8

Další čtení

Lord, Nick (březen 2008), „Jednotná konstrukce některých nekonečných sekvencí coprime“, Matematický věstník, 92: 66–70.

[1] Eaton, James S. Pojednání o aritmetice. 1872. Lze stáhnout z: https://archive.org/details/atreatiseonarit05eatogoog

[2] Hardy & Wright 2008, str. 6

[3] Graham, R.L .; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics / A Foundation for Computer Science, Addison-Wesley, str. 115, ISBN 0-201-14236-8

[4] Ruda 1988, str. 47

[5] Niven & Zuckerman 1966, str. 22, Věta 2.3 (b)

[6] Niven & Zuckerman 1966, str. 6, Věta 1.8

[7] Niven & Zuckerman 1966, s. 7, Věta 1.10

[8] Rosen 1992, str. 140

[9] Tuto větu prokázal Ernesto Cesàro v roce 1881. Důkaz viz Hardy & Wright 2008 Věta 332

[10] Saunders, Robert & Randall, Trevor (červenec 1994), „Rodokmen pythagorejských trojčat znovu navštíven“, Matematický věstník, 78: 190–193, doi:10.2307/3618576.

[11] Mitchell, Douglas W. (červenec 2001), „Alternativní charakterizace všech primitivních pythagorovských trojic“, Matematický věstník, 85: 273–275, doi:10.2307/3622017.

[12] Klaus Pommerening.„Kryptologie: klíčové generátory s dlouhými obdobími“.

[13] David Mowry.„Německé šifrovací stroje druhé světové války“.2014.p. 16; p. 22.

[14] Dirk Rijmenants."Počátky jednorázové podložky".

[15] Gustavus J. Simmons.„Šifra Vernam-Vigenère“.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]