Liczby względnie pierwsze - Polski Serwis Naukowy

Liczby względnie pierwsze – liczby całkowite, które nie mają innych poza jedynką wspólnych dzielników w rozkładzie na czynniki pierwsze lub, równoważnie, ich największym wspólnym dzielnikiem jest jedność; te, w których żadna para nie ma wspólnych dzielników w rozkładzie poza jedynką lub, równoważnie, których największy wspólny dzielnik dla dowolnej pary wynosi jeden, nazywa się parami względnie pierwszymi.

Algorytm Euklidesa – algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Nie wymaga rozkładania liczb na czynniki pierwsze. Algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go w swoim dziele Elementy.

Największy wspólny dzielnik – dla danych dwóch (lub więcej) liczb całkowitych największa liczba naturalna dzieląca każdą z nich. Pojęcie to ma wiele uogólnień, które przedstawiono w dalszej części artykułu.

Szybkim sposobem określenia, czy dwie liczby są względnie pierwsze jest algorytm Euklidesa. Funkcja Eulera (tocjent lub phi Eulera) dodatniej liczby całkowitej n jest liczbą liczb naturalnych między 1 a n, które są względnie pierwsze z n.

Przykłady

Liczby 6 i 35 są względnie pierwsze, ale 6 i 27 nie są, gdyż obie są podzielne przez 3.

Liczba 1 jest względnie pierwsza z każdą liczbą całkowitą.

Liczby 10, 12 i 15 są względnie pierwsze, ale nie są parami względnie pierwsze (najmniejsza wspólna wielokrotność tych liczb wynosi 60, a nie 10·12·15 = 1800).

Właściwości

Jeżeli dwie liczby są względnie pierwsze, to ich najmniejsza wspólna wielokrotność równa jest ich iloczynowi. Twierdzenie to nie uogólnia się na większą liczbę czynników.

Ideał – w algebrze abstrakcyjnej podzbiór pierścienia o pewnych szczególnych własnościach. Pojęcie ideału zostało wprowadzone przez Dedekinda, jako uogólnienie pojęcia liczb idealnych rozważanych przez Kummera. Badania Dedekinda były kontynuowane przez Hilberta i szczególnie przez Emmę Noether.

Warunkiem równoważnym względnej pierwszości dwóch liczb jest: jeśli liczby a i b są względnie pierwsze, to istnieją liczby całkowite x i y, że ax + by = 1.

Ogólniej: jeśli liczby a1, ..., an są liczbami względnie pierwszymi, to istnieją liczby całkowite k1, ..., kn, że k1a1 + ... + knan = 1.

Uogólnienie

W pierścieniu przemiennym z jedynką $R$ ideały $I$ i $J$ nazywamy względnie pierwszymi, jeśli ich suma algebraiczna $I + J$ jest całym pierścieniem.

W dziedzinach ideałów głównych można przyjąć następującą definicję elementów względnie pierwszych: $a$ i $b$ są względnie pierwsze jeśli z faktu, że pewien element $d$ dzieli $a$ i dzieli $b$ wynika, że $d$ jest odwracalny. Jest ona równoważna temu, że ideały generowane przez te elementy są względnie pierwsze. W pierścieniach niebędących dziedzinami ideałów głównych te pojęcia nie muszą się pokrywać.

Liczby względnie pierwsze generują ideały względnie pierwsze w $\mathbb{Z}$ (bo $\mathbb{Z}$ jest dziedziną ideałów głównych).

Zobacz też

liczby pierwsze

algorytm Euklidesa

funkcja φ