Liczby względnie pierwsze

Liczby względnie pierwsze – liczby całkowite, których największym wspólnym dzielnikiem jest jeden^[1].

Jeżeli liczby ${\displaystyle a,b}$ są względnie pierwsze zapisuje się to symbolicznie jako ${\displaystyle a\perp b}$ lub ${\displaystyle {\mbox{NWD}}(a,b)=1}$^[2].

Liczby parami względnie pierwsze – liczby całkowite, wśród których każde dwie różne są względnie pierwsze.

Fakt, że liczby ${\displaystyle a,b,c,...d}$ są parami względnie pierwsze, zapisuje się symbolicznie ${\displaystyle {\mbox{NWD}}(a,b,c,\dots ,d)=1.}$

Szybkim sposobem określenia, czy dwie liczby są względnie pierwsze jest algorytm Euklidesa^[3]. Funkcja Eulera dodatniej liczby całkowitej ${\displaystyle n}$ jest liczbą liczb naturalnych między 1 a ${\displaystyle n,}$ które są względnie pierwsze z ${\displaystyle n}$^[2].

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łasnoś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, co pokazuje przykład: ${\displaystyle {\mbox{NWD}}(4,6,9)=1,{\mbox{NWW}}(4,6,9)=36,\ 4\cdot 6\cdot 9=216.}$

Na to, aby liczby ${\displaystyle a,b}$ były względnie pierwsze, potrzeba i wystarcza, aby istniały liczby całkowite ${\displaystyle x}$ i ${\displaystyle y}$ spełniające równanie

${\displaystyle ax+by=1.}$

Ogólniej:
Na to, aby liczby ${\displaystyle a_{1},...,a_{n}}$ były względnie pierwsze, potrzeba i wystarcza, aby istniały liczby całkowite ${\displaystyle k_{1},...,k_{n}}$ spełniające równanie

${\displaystyle k_{1}a_{1}+...+k_{n}a_{n}=1}$^[4].

Uogólnienie

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

W dziedzinach ideałów głównych można przyjąć następującą definicję elementów względnie pierwszych: ${\displaystyle a}$ i ${\displaystyle b}$ są względnie pierwsze jeśli z faktu, że pewien element ${\displaystyle d}$ dzieli ${\displaystyle a}$ i dzieli ${\displaystyle b}$ wynika, że ${\displaystyle 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 ${\displaystyle \mathbb {Z} }$ (bo ${\displaystyle \mathbb {Z} }$ jest dziedziną ideałów głównych).

Zobacz też

• algorytm Euklidesa
• funkcja φ
• liczby pierwsze

Przypisy