Za chwilę zapoznasz się z artykułem jednego z prowadzących kurs do Olimpiady Matematycznej w Indeksie w Kieszeni! Nauka z IWK co roku pozwala setkom uczniów z całej Polski na zdobycie tytułów finalisty, laureata, a nawet zwycięzcy olimpiady! Sprawdź sam na czym polegają nasze przygotowania.
Jednym z pierwszych pojęć związanych z matematyką, które poznajemy w życiu, są liczby całkowite. Towarzyszą nam one od zawsze, odpowiadając na pytania typu ile? lub który? Mimo pozornej prostoty matematycy od wieków badają ich strukturę i własności w ramach gałęzi matematyki zwanej teorią liczb. Wraz z geometrią, kombinatoryką i algebrą stanowi ona jeden z czterech fundamentalnych działów, w które pogrupowane są zadania olimpijskie. Jest to też dziedzina, w której proste fakty, cierpliwość i spójne rozumowanie logiczne potrafią łatwo otworzyć drogę do rozwiązania. Przyjrzymy się dzisiaj pokrótce pewnej grupie funkcji, które są w stanie ułatwić i ustrukturyzować dowody oparte na analizowaniu podzielności liczb całkowitych – wykładnikom p-adycznym.
Wykładnik p-adyczny nieujemnej liczby całkowitej $n$, gdzie $p$ jest liczbą pierwszą, definiujemy jako największą liczbę całkowitą $k$, dla której zachodzi $p^k | n$. Oznaczamy go jako $v_p(n)$. Innymi słowy, $v_p(n) = k$ wtedy i tylko wtedy, gdy liczba pierwsza $p$ wchodzi do rozkładu $n$ na czynniki pierwsze z potęgą $k$. W celu uspójnienia definicji kładziemy $v_p(0) = +\infty$.
Przedstawimy teraz ważne własności wykładników $p$-adycznych. Czytelnika zachęcam do próby udowodnienia każdego z tych faktów samemu:
\[n = \prod_{p \in \mathbb{P}} p^{v_p(n)}.\]
Iloczyn rozciąga się tutaj po wszystkich liczbach pierwszych, ale tylko skończenie wiele z nich dzieli $n$, więc tylko dla skończenie wielu $p$ zachodzi $v_p(n) \neq 0$, zatem nieskończony iloczyn jest dobrze zdefiniowany.
Dowód. Z definicji.
\[\forall_{p \in \mathbb{P}} \ v_p(a) \le v_p(b).\]
Dowód. ($\Longrightarrow$) Z własności 1. otrzymujemy $a = \prod_{p \in \mathbb{P}} p^{v_p(a)}$. Stąd jeżeli $a$ dzieli $b$, to dla dowolnego $p \in \mathbb{P}$ zachodzi $p^{v_p(a)} | b$. Ale z definicji wykładnika $p$-adycznego $p^{v_p(b)} \ge p^{v_p(a)}$.
($\Longleftarrow$) Korzystając z własności 1. otrzymujemy
\[\frac{b}{a} = \frac{\prod_{p \in \mathbb{P}} p^{v_p(b)}}{\prod_{p \in \mathbb{P}} p^{v_p(a)}} = \prod_{p \in \mathbb{P}} p^{v_p(b) – v_p(a)},\]
ale $v_p(b) – v_p(a) \ge 0$, więc $\frac{b}{a}$ jest iloczynem liczb całkowitych, czyli jest liczbą całkowitą.
\[\text{NWD}(a, b) = \prod_{p \in \mathbb{P}} p^{\min\{v_p(a), v_p(b)\}}.\]
Dowód. Oznaczmy $d = \text{NWD}(a, b)$. Korzystając z własności 1. zapiszmy $d = \prod_{p \in \mathbb{P}} p^{v_p(d)}$. Wiemy, że $d$ dzieli zarówno $a$ jak i $b$, więc korzystając z własności 2. otrzymujemy
\[v_p(d) \le v_p(a) \quad \text{oraz} \quad v_p(d) \le v_p(b),\]
co daje nam
\[v_p(d) \le \min\{v_p(a), v_p(b)\}.\]
Wynika stąd, że
\[d \le \prod_{p \in \mathbb{P}} p^{\min\{v_p(a), v_p(b)\}},\]
ale z kolei korzystając z własności 2. zauważamy, że $\prod_{p \in \mathbb{P}} p^{\min\{v_p(a), v_p(b)\}}$ dzieli $a$ oraz $b$, więc musi zachodzić
\[d = \prod_{p \in \mathbb{P}} p^{\min\{v_p(a), v_p(b)\}}.\]
\[\text{NWW}(a, b) = \prod_{p \in \mathbb{P}} p^{\max\{v_p(a), v_p(b)\}}.\]
Dowód. Oznaczmy $d = \text{NWW}(a, b)$. Korzystając z własności 1. zapiszmy $d = \prod_{p \in \mathbb{P}} p^{v_p(d)}$. Wiemy, że $d$ jest podzielne przez zarówno $a$ jak i $b$, więc korzystając z własności 2. otrzymujemy
\[v_p(d) \ge v_p(a) \quad \text{oraz} \quad v_p(d) \ge v_p(b),\]
co daje nam
\[v_p(d) \ge \max\{v_p(a), v_p(b)\}.\]
Wynika stąd, że
\[d \ge \prod_{p \in \mathbb{P}} p^{\max\{v_p(a), v_p(b)\}},\]
ale znowu korzystając z własności 2. zauważamy, że $\prod_{p \in \mathbb{P}} p^{\max\{v_p(a), v_p(b)\}}$ jest podzielne przez $a$ oraz $b$, więc musi zachodzić
\[d = \prod_{p \in \mathbb{P}} p^{\max\{v_p(a), v_p(b)\}}.\]
\[v_p(ab) = v_p(a) + v_p(b).\]
Dowód. Wobec własności 1. otrzymujemy
\[\prod_{p \in \mathbb{P}} p^{v_p(ab)} = ab = \prod_{p \in \mathbb{P}} p^{v_p(a)} \prod_{p \in \mathbb{P}} p^{v_p(b)} = \prod_{p \in \mathbb{P}} p^{v_p(a) + v_p(b)}.\]
\[v_p(a + b) \ge \min\{v_p(a), v_p(b)\},\]
przy czym równość otrzymujemy przy $v_p(a) \neq v_p(b)$. \\ \\
Dowód. Niech $a = p^{v_p(a)} a_1$ oraz $b = p^{v_p(b)} b_1$. Zauważmy, że $a_1$ oraz $b_1$ nie dzielą się przez $p$. Dodatkowo połóżmy $k = \min\{v_p(a), v_p(b)\}$. Wtedy
\[a + b = p^{v_p(a)} a_1 + p^{v_p(b)} b_1 = p^{k} (p^{v_p(a) – k} a_1 + p^{v_p(b) – k} b_1).\]
Wynika stąd, że $a + b$ dzieli się co najmniej przez $p^k$, więc $v_p(a + b) \ge k$. Zauważmy teraz, że gdy $v_p(a) \neq v_p(b)$, to dokładnie jedna z liczb $v_p(a) – k$, $v_p(b) – k$ jest równa zero. Bez straty ogólności założmy, że $v_p(a) – k = 0$. Wtedy
\[p^{v_p(a) – k} a_1 + p^{v_p(b) – k} b_1 = a_1 + p^{v_p(b) – k} b_1,\] ale $a_1$ nie dzieli się przez $p$, więc $a_1 + p^{v_p(b) – k}$ też nie dzieli się przez $p$, zatem $v_p(a + b)$ jest równe dokładnie $k$.
\[\forall_{p \in \mathbb{P}} \ k | v_p(a).\]
Dowód. ($\Longrightarrow$) Niech $a = b^k$. Wobec własności 1. otrzymujemy
\[\prod_{p \in \mathbb{P}} p^{v_p(a)} = a = b^k = (\prod_{p \in \mathbb{P}} p^{v_p(b)})^k = \prod_{p \in \mathbb{P}} p^{kv_p(b)}.\]
Korzystając z twierdzenia o jednoznaczności rozkładu na czynniki pierwsze otrzymujemy, że równość
\[\prod_{p \in \mathbb{P}} p^{v_p(a)} = \prod_{p \in \mathbb{P}} p^{kv_p(b)}\]
implikuje równość wykładników, skąd dla każdego $p \in \mathbb{P}$ zachodzi $v_p(a) = k v_p(b)$, czyli $k$ dzieli $v_p(a)$.
($\Longleftarrow$) Dla każdego $p \in \mathbb{P}$ oznaczmy $v_p(a) = kr_p$. Wtedy korzystając z własności 1. otrzymujemy
\[a = \prod_{p \in \mathbb{P}} p^{v_p(a)} = \prod_{p \in \mathbb{P}} p^{kr_p} = (\prod_{p \in \mathbb{P}} p^{r_p})^k.\]
W charakterze najważniejszego ćwiczenia powinieneś uważnie przestudiować te dowody, a najlepiej udowodnić te twierdzenia samodzielnie. Warto również, abyś rozważył rozszerzenie definicji wykładników $p$-adycznych oraz faktów ich dotyczących na wszystkie liczby całkowite, a nawet wymierne. Następnie polecam zabrać się za następujące zadania (według rosnącego stopnia trudności):
1. Niech $a, b \in \mathbb{Z}_{+}$ będą takie, że dla każdego $n \ge 1$ zachodzi $a^n | b^{n+1}$.
Udowodnić, że $a | b$.
2. Niech $a, b \in \mathbb{Z}_{+}$ będą takie, że $a | b^2, \ b^2 | a^3, \ a^3 | b^4, \ …$.
Udowodnić, że $a = b$.
3. Rozwiązać w liczbach całkowitych równanie
\[x^{2000} + 2000^{1999} = x^{1999} + 2000^{2000}.\]
4. Wyznaczyć wszystkie trójki $(x, y, n)$ liczb całkowitych dodatnich spełniające równanie
\[(x – y)^n = xy.\]
Po rozwiązania zadań opisanych w artykule zgłoś się na nasz jedyny w swoim rodzaju kurs olimpijski prowadzony przez laureatów najwyższych miejsc poprzednich edycji! Wszystkie szczegóły znajdziesz na dedykowanej podstronie.
Autor artykułu: Jasiek Kociniak
Strona przygotowana przez Zyskowni.pl