Liczby względnie pierwsze

Liczby względnie pierwsze – relacja między liczbami naturalnymi i innymi całkowitymi, definiowana przez podzielność. Największy wspólny dzielnik (NWD) liczb względnie pierwszych wynosi jeden^[1]. Symbolicznie:

${\displaystyle {\begin{aligned}&a,b,c,\dots ,d\in \mathbb {Z} ,\\{\mbox{NWD}}(&a,b,c,\dots ,d)=1.\end{aligned}}}$

W przypadku dwóch liczb ${\displaystyle a,b}$ używa się też znaku prostopadłości^[2]: ${\displaystyle a\perp b.}$

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

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 pierwsze^{[potrzebny przypis]}: ${\displaystyle \forall a,b\in A:a\neq b\Rightarrow a\perp 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ż w algebrze abstrakcyjnej, w kontekście niektórych pierścieni, 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		${\displaystyle \perp }$
1	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$
2		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$
3		${\displaystyle \perp }$	${\displaystyle \perp }$		${\displaystyle \perp }$	${\displaystyle \perp }$		${\displaystyle \perp }$	${\displaystyle \perp }$
4		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$
5		${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$		${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$
6		${\displaystyle \perp }$				${\displaystyle \perp }$		${\displaystyle \perp }$
7		${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$	${\displaystyle \perp }$		${\displaystyle \perp }$	${\displaystyle \perp }$
8		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$		${\displaystyle \perp }$
9		${\displaystyle \perp }$	${\displaystyle \perp }$		${\displaystyle \perp }$	${\displaystyle \perp }$		${\displaystyle \perp }$	${\displaystyle \perp }$

Własności

Przypadek par liczb

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ż ${\displaystyle 1\perp 1;}$
• jest symetryczna, ponieważ NWD jest działaniem przemiennym;
• nie jest przechodnia (tranzytywna); przykładowo ${\displaystyle 2\perp 3}$ i ${\displaystyle 3\perp 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ą ${\displaystyle (1\perp 1).}$
• implikuje, że ich najmniejsza wspólna wielokrotność tych liczb równa się ich iloczynowi^{[potrzebny przypis]}: ${\displaystyle a\perp b\Rightarrow {\mbox{NWW}}(a,b)=ab.}$
• warunkiem równoważnym względnej pierwszości liczb ${\displaystyle a,b}$ jest, aby istniały liczby całkowite ${\displaystyle x}$ i ${\displaystyle y}$ spełniające równanie^[4]: ${\displaystyle ax+by=1.}$

Przypadek ogólny

Przedostatnie twierdzenie nie uogólnia się na większą liczbę czynników; przykładowo:

${\displaystyle {\begin{aligned}{\mbox{NWD}}(4,6,9)&=1,\\{\mbox{NWW}}(4,6,9)&=36,\\4\cdot 6\cdot 9&=216.\end{aligned}}}$

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

${\displaystyle k_{1}a_{1}+\ldots +k_{n}a_{n}=1.}$

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ć^{[potrzebny przypis]}.

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

Zobacz też

• funkcja φ