Liczby względnie pierwsze

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

Liczby względnie pierwsze – liczby całkowite, których największym wspólnym dzielnikiem jest jeden[1]. Symbolicznie dla liczb a,b,c,…d zapisuje się to: NWD(a,b,c,…,d)=1. W przypadku dwóch liczb a,b używa się też znaku prostopadłości[2]: a⊥b.

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

Zbiory o więcej niż dwóch elementach mogą mieć własność względnej pierwszości parami – kiedy każde dwie różne liczby są względnie pierwszeSzablon:Fakt: ∀a,b∈A:a≠b⇒a⊥b. Względna pierwszość całego zbioru jest logicznie słabsza od tej parami; przykładowo liczby ze zbioru {2,3,4} są względnie pierwsze, ale nie są względnie pierwsze parami, ponieważ 2|4.

Relację względnej pierwszości definiuje się też dla ideałów w ogólnych pierścieniach, co opisuje dalsza sekcja.

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).

Poniższa tabela zaznacza względną pierwszość liczb z zakresu 0–9:

0 1 2 3 4 5 6 7 8 9
0 ⊥
1 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
2 ⊥ ⊥ ⊥ ⊥ ⊥
3 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
4 ⊥ ⊥ ⊥ ⊥ ⊥
5 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
6 ⊥ ⊥ ⊥
7 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
8 ⊥ ⊥ ⊥ ⊥ ⊥
9 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥

Własności

Względna pierwszość jako relacja dwuargumentowa ma szereg własności:

  • nie jest zwrotna; żadna liczba większa od jedynki nie jest względnie pierwsza ze sobą;
  • nie jest też przeciwzwrotna, ponieważ 1⊥1;
  • jest symetryczna, ponieważ NWD jest działaniem przemiennym;
  • nie jest przechodnia (tranzytywna); przykładowo 2⊥3 i 3⊥2, ale dwójka nie jest względnie pierwsza ze sobą;
  • nie jest też przeciwprzechodnia (atranzytywna) ze względu na względną pierwszość jedynki ze sobą samą (1⊥1).
  • implikuje, że ich najmniejsza wspólna wielokrotność tych liczb równa się ich iloczynowiSzablon:Fakt: a⊥b⇒NWW(a,b)=ab.
  • warunkiem równoważnym względnej pierwszości liczb a,b jest, aby istniały liczby całkowite x i y spełniające równanie[4]: ax+by=1.

Przedostatnie twierdzenie nie uogólnia się na większą liczbę czynników; przykładowo NWD(4,6,9)=1,NWW(4,6,9)=36, 4⋅6⋅9=216.

Na to, aby liczby a1,…,an były względnie pierwsze, potrzeba i wystarcza, aby istniały liczby całkowite k1,…,kn spełniające równanie[4]:

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[4].

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ćSzablon:Potrzebny przypis.

Liczby względnie pierwsze generują ideały względnie pierwsze w ℤ (bo ℤ jest dziedziną ideałów głównych)Szablon:Potrzebny przypis.

Zobacz też

Przypisy

Szablon:Przypisy

Bibliografia

Linki zewnętrzne

Szablon:Teoria liczb

Szablon:Kontrola autorytatywna

  1. ↑ Szablon:Encyklopedia PWN
  2. ↑ 2,0 2,1 Szablon:Odn
  3. ↑ Szablon:Cytuj
  4. ↑ 4,0 4,1 4,2 Szablon:Odn
Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Liczby_względnie_pierwsze&oldid=405”