Liczby względnie pierwsze

Liczby względnie pierwsze – liczby całkowite, których największym wspólnym dzielnikiem jest jeden^[1]. Symbolicznie dla liczb ${\displaystyle a,b,c,\dots d}$ zapisuje się to: ${\displaystyle {\mbox{NWD}}(a,b,c,\dots ,d)=1.}$ 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ż 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		${\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

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.}$

Przedostatnie twierdzenie nie uogólnia się na większą liczbę czynników; przykładowo ${\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_{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 φ

Przypisy

Bibliografia

• WładysławW. Narkiewicz WładysławW., Teoria liczb, wyd. 3, Warszawa: Wydawnictwo Naukowe PWN, 2003, ISBN 83-01-14015-1, OCLC 749285993 [dostęp 2022-07-13] .
• AdamA. Neugebauer AdamA., Matematyka olimpijska 1. Algebra i teoria liczb, wyd. 1, Kraków: Wydawnictwo Szkolne OMEGA, 2018, ISBN 978-83-7267-710-5, OCLC 1055646686 [dostęp 2022-07-13] .

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Relatively Prime, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-02-02].
• Mutually-prime numbers (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].