Różnica pomiędzy stronami "Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera" i "Henryk Dąbrowski"

Z Henryk Dąbrowski
(Różnica między stronami)
Przejdź do nawigacji Przejdź do wyszukiwania
 
 
Linia 1: Linia 1:
−
<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.12.2023</div>
+
<div style="text-align:right; font-size: 90%; font-style: italic; ">Wolność nie czyni ludzi szczęśliwymi, czyni ich po prostu ludźmi</div>
  
−
__FORCETOC__
 
  
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Powitanie|Hide=Powitanie}}
−
== Największy wspólny dzielnik ==
+
*[[WOLNOŚĆ, PRAWDA, SPRAWIEDLIWOŚĆ, HONOR, MIŁOŚĆ, ...]]
−
 
 
−
<span id="H1" style="font-size: 110%; font-weight: bold;">Definicja H1</span><br/>
 
−
Niech będą dane dwie liczby całkowite <math>a</math> i <math>b</math> niebędące jednocześnie zerami. Największym wspólnym dzielnikiem<ref name="GCD1"/> liczb <math>a</math> i <math>b</math> będziemy nazywali liczbę całkowitą <math>D</math> taką, że
 
−
 
 
−
:#&nbsp;&nbsp;<math> D \mid a \quad \text{i} \quad D \mid b</math>
 
−
:#&nbsp;&nbsp;<math>\,\, d \mid a \quad \text{i} \quad \; d \mid b \qquad \Longrightarrow \qquad d \leqslant D</math>
 
−
 
 
−
gdzie <math>d</math> jest dowolną liczbą całkowitą.
 
−
 
 
−
 
 
−
 
 
−
<span id="H2" style="font-size: 110%; font-weight: bold;">Uwaga H2</span><br/>
 
−
Tak zdefiniowaną liczbę <math>D</math> będziemy oznaczali przez <math>\gcd (a, b)</math>. Ponieważ <math>1 \mid a \;</math> i <math>\; 1 \mid b</math>, to z&nbsp;definicji wynika natychmiast, że <math>\gcd (a, b) \geqslant 1</math>.
 
−
 
 
−
 
 
−
 
 
−
<span id="H3" style="font-size: 110%; font-weight: bold;">Zadanie H3</span><br/>
 
−
Pokazać, że
 
−
 
 
−
::<math>d \mid \gcd (a, b) \qquad \Longleftrightarrow \qquad d \mid a \quad \text{i} \quad d \mid b</math>
 
−
 
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
 
 
−
<math>\Large{\Longrightarrow}</math>
 
−
 
 
−
Z założenia <math>d \mid \gcd (a, b)</math>. Z&nbsp;definicji największego wspólnego dzielnika <math>\gcd (a, b) \mid a</math>, zatem <math>d \mid a</math>. Analogicznie pokazujemy, że <math>d \mid b</math>.
 
−
 
 
−
<math>\Large{\Longleftarrow}</math>
 
−
 
 
−
Z założenia <math>a = r d</math>, <math>b = s d</math>. Z&nbsp;lematu Bézouta (zobacz C73) istnieją takie liczby całkowite <math>x, y</math>, że
 
−
 
 
−
::<math>\gcd (a, b) = a x + b y = r d x + s d y = d (r x + s y)</math>
 
−
 
 
−
Zatem <math>d \mid \gcd (a, b)</math>.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
 +
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Brak kary śmierci w kodeksie karnym jest pogardą dla ofiar|Hide=Brak kary śmierci w kodeksie karnym jest pogardą dla ofiar}}
 +
<br/><div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Prawa ustanowione są dla sprawiedliwych nie dlatego, by nie popełniali nieprawości, lecz by jej nie doznawali.</div>
 +
[[File:Epikur83x100.png|50px]]<span style="font-size: 90%; line-height: 1.1em; font-style: italic; font-weight: bold; color: #808080;">&nbsp;&nbsp;Epikur</span><br/><br/>
  
 +
<div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Jestem głosem zamordowanych. Jestem głosem tych, których godność i prawo do życia uczyniono mniej znaczącymi od godności i prawa do życia morderców. Jestem głosem tych, którzy nie mogą się już bronić. Jestem głosem niezgody na Twoje milczenie.</div><br/>
  
−
<span id="H4" style="font-size: 110%; font-weight: bold;">Twierdzenie H4</span><br/>
+
*[[NIE!]]
−
Jeżeli liczby całkowite <math>a, b</math> nie są jednocześnie równe zero i <math>\gcd (a, b) = a x + b y</math>, to <math>\gcd (x, y) = 1</math>.
+
*[[Brak kary śmierci w kodeksie karnym jest pogardą dla ofiar]]
−
 
+
*[[Śmierć i Sprawiedliwość (Edward I. Koch)]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+
*[[Pamiętajmy, że to co tolerujemy na nic więcej nie zasługuje]]
−
Z lematu Bézouta (zobacz C73) wiemy, że liczby całkowite <math>x, y</math> zawsze istnieją. Niech <math>\gcd (a, b) = d > 0</math>, zatem <math>a = d k</math> i <math>b = d m</math>, czyli
+
*[[Strzeżcie się fałszywych proroków]]
−
 
+
*[[Dlaczego Jezus, przybywszy do świątyni, powywracał kupcom stoły?]]
−
::<math>(d k) x + (d m) y = d</math>
+
*[[Rozmowa Chrześcijanina i Człowieka Postępu o karze śmierci]]
−
 
+
*[[Bezcenne czy przecenione?]]
−
Co oznacza, że <math>k x + m y = 1</math>, ale <math>\gcd (x, y)</math> jest dzielnikiem <math>k x + m y</math> (bo jest dzielnikiem <math>x</math> i <math>y</math>), zatem <math>\gcd (x, y) \mid 1</math>, czyli <math>\gcd (x, y) = 1</math>. Co należało pokazać.<br/>
+
*[[Porozmawiajmy o argumentach (1)]]
−
&#9633;
+
*[[Porozmawiajmy o argumentach (2)]]
−
{{\Spoiler}}
+
*[[Porozmawiajmy o argumentach (3)]]
−
 
+
*[[Porozmawiajmy o argumentach (4)]]
−
 
+
*[[Porozmawiajmy o argumentach (5)]]
 +
*[[Porozmawiajmy o argumentach – „Rozważania… ” Camusa]]
 +
*[[Albert Camus – fobia czy rzeczywistość?]]
 +
*[[George Orwell – uraz psychiczny czy rzeczywistość?]]
 +
*[[Księga powtórnie powtórzonego prawa]]
 +
*[[CBOS – czy poznamy stosunek Polaków do kary śmierci?]]
 +
*[[Jak postęp zapewnił bezpieczeństwo mordercom i zbrodniarzom]]
 +
*[[Jak to z moratorium było|Jak to z moratorium było - uzupełnienie!]]
 +
*[[Kara śmierci: topór kontra karabin maszynowy (USA)]]
 +
*[[Morderstwa, egzekucje, odstraszanie - amerykański eksperyment]]
 +
*[[Stany Zjednoczone, Murzyni, zabójstwa, kara śmierci i odstraszanie]]
 +
*[[Kara śmierci w Stanach Zjednoczonych]]
 +
*[[Czy kara śmierci ratuje życie?]]
 +
*[[Kara śmierci: topór kontra karabin maszynowy (Japonia)]]
 +
*[[Kara śmierci: kto nie ma topora, a kto ma karabin (Polska)]]
 +
*[[Kara śmierci: lista państw świata według wskaźnika reakcji]]
 +
*[[Czy kara śmierci odstrasza?]]
 +
*[[Pomyłki sądowe – mordercy którym pozwolono zabić ponownie]]
 +
*[[Za drugą szansę zabójcy możesz zapłacić życiem]]
 +
*[[Lepiej, aby zginęło stu niewinnych, niż gdyby jeden winny miał zginąć]]
 +
*[[Crime International – Polska 2015]]
 +
*[[Crime International – Polska 2016]]
 +
*[[Crime International – Polska 2017]]
 +
*[[Crime International – Polska 2018]]
 +
*[[Wielokrotni mordercy – typologia i przykłady]]
 +
*[[Prawie niewinni mordercy. Co jeszcze jesteś gotów dla nich uczynić?]]
 +
*[[Prawa człowieka czy prawa bandyty? Przyrodzona godność ludzka]]
 +
*[[Arthur Schopenhauer: godność ludzka czyli nowe szaty króla]]
 +
*[[Prawo do życia, czyli zwycięstwo hipokryzji]]
 +
*[[Sąd Najwyższy USA: czarne jest najpiękniejsze]]
 +
*[[Pomyłka sądowa – prawie niewinny morderca Marlene Miller]]
 +
*[[Banalizacja zła]]
 +
*[[Krótkie historie o zabijaniu]]
 +
*[[Kara śmierci – cytaty]]
  
−
<span id="H5" style="font-size: 110%; font-weight: bold;">Twierdzenie H5</span><br/>
 
−
Niech <math>a, b, k \in \mathbb{Z}</math>. Prawdziwy jest wzór
 
  
−
::<math>\gcd (a + k b, b) = \gcd (a, b)</math>
 
  
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+
[https://drive.google.com/uc?export=download&id=0B1HrFK-3gYNvRC1JT0Q2T2dyeVU Pobierz artykuły dotyczące kary śmierci – plik PDF]
−
Niech <math>d_1 = \gcd (a + k b, b) \;</math> i <math>\; d_2 = \gcd (a, b)</math>.
 
  
−
Z definicji <math>d_1 \mid (a + k b) \;</math> i <math>\; d_1 \mid b</math>, zatem <math>a + k b = x d_1 \;</math> i <math>\; b = y d_1</math>, czyli <math>a + k x d_1 = x d_1</math>, skąd natychmiast wynika, że <math>d_1 \mid a</math>. Ponieważ <math>d_1 \mid b</math>, to <math>d_1 \mid d_2</math> (zobacz&nbsp;[[#H3|H3]]).
 
  
−
Z definicji <math>d_2 \mid a \;</math> i <math>\; d_2 \mid b</math>, zatem <math>d_2 \mid (a + k b) \;</math> i <math>\; d_2 \mid b</math>, czyli <math>d_2 \mid d_1</math>.
 
  
−
Ponieważ <math>d_1 \mid d_2 \;</math> i <math>\; d_2 \mid d_1</math>, to <math>| d_1 | = | d_2 |</math>. Co kończy dowód.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Historia|Hide=Historia}}
−
 
+
*[[Hańba i chwała - II Rzeczpospolita]]
−
<span id="H6" style="font-size: 110%; font-weight: bold;">Twierdzenie H6</span><br/>
+
*[[Hańba i chwała - II Wojna Światowa]]
−
Niech <math>a, b, m \in \mathbb{Z}</math>. Prawdziwa jest następująca równoważność
+
*[[Hańba i chwała – Powstanie Warszawskie]]
−
 
+
*[[Hańba i chwała – Stalin'44]]
−
::<math>\gcd (a, m) = 1 \quad  \text{i} \quad \gcd (b, m) = 1 \quad \qquad \Longleftrightarrow \quad \qquad \gcd (a b, m) = 1</math>
+
*[[Hańba i chwała – sieroty po II RP]]
−
 
+
*[[Hańba i chwała – policzmy głosy]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+
*[[Czy niemiecką mordownię z lat 1939-45 można nazywać okupacją?]]
−
 
+
*[[Niemiecka Mordownia 1939-1945]]
−
<math>\Large{\Longrightarrow}</math>
+
*[[Bandyci, mordercy i towarzysze]]
−
 
+
*[[Poeci, pisarze i towarzysze]]
−
Niech <math>\gcd (a b, m) = d</math>. Z&nbsp;definicji <math>d \mid a b</math> i <math>d \mid m</math>. Gdyby było <math>d > 1</math>, to istniałaby liczba pierwsza <math>p</math> taka, że <math>p \mid d</math> i&nbsp;mielibyśmy <math>p \mid a b</math> i <math>p \mid m</math>. Jeżeli <math>p \mid a b</math>, to <math>p \mid a</math> lub <math>p \mid b</math> (zobacz C74). W&nbsp;przypadku, gdy <math>p \mid a</math> dostajemy <math>\gcd (a, m) \geqslant p > 1</math>, wbrew założeniu, że <math>\gcd (a, m) = 1</math>. Analogicznie pokazujemy sprzeczność, gdy <math>p \mid b</math>.
+
*[[Szymborska – ciszej nad tą trumną]]
−
 
 
−
<math>\Large{\Longleftarrow}</math>
 
−
 
 
−
Niech <math>\gcd (a, m) = d</math>. Z&nbsp;definicji <math>d \mid a</math> i <math>d \mid m</math>, zatem również <math>d \mid a b</math> i <math>d \mid m</math>. Mamy stąd
 
−
 
 
−
::<math>1 = \gcd (a b, m) \geqslant d \geqslant 1</math>
 
−
 
 
−
Czyli musi być <math>d = 1</math>. Analogicznie pokazujemy, że <math>\gcd (b, m) = 1</math>.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
 +
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Powstanie Warszawskie|Hide=Powstanie Warszawskie}}
 +
<br/><div style="font-size: 110%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Celem wojny nie jest śmierć za ojczyznę, ale sprawienie, aby tamci skurwiele umierali za swoją.</div>
 +
[[File:Patton94x133.png|45px]]<span style="font-size: 110%; line-height: 1.1em; font-style: italic; font-weight: bold; color: #808080;"> gen. George Patton</span><br/><br/>
  
−
 
+
*[[POMNIK TRUPA]]
−
<span id="H7" style="font-size: 110%; font-weight: bold;">Twierdzenie H7</span><br/>
+
*[[Hańba i chwała – Powstanie Warszawskie]]
−
Dla <math>a, b, m \in \mathbb{Z}</math> jest
+
*[[Hańba i chwała – Stalin'44]]
−
 
+
*[[Hańba i chwała – sieroty po II RP]]
−
::<math>\gcd (a b, m) \mid \gcd (a, m) \cdot \gcd (b, m)</math>
+
*[[Hańba i chwała – policzmy głosy]]
−
 
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Wprowadźmy oznaczenia
 
−
 
 
−
::<math>r = \gcd (a b, m)</math>
 
−
 
 
−
::<math>s = \gcd (a, m)</math>
 
−
 
 
−
::<math>t = \gcd (b, m)</math>
 
−
 
 
−
Z lematu Bézouta (zobacz C73) istnieją takie liczby <math>x, y, X, Y</math>, że
 
−
 
 
−
::<math>s = a x + m y</math>
 
−
 
 
−
::<math>t = b X + m Y</math>
 
−
 
 
−
Zatem
 
−
 
 
−
::<math>s t = (a x + m y) (b X + m Y) = a b x X + a m x Y + m b y X + m^2 y Y</math>
 
−
 
 
−
ale <math>r \mid a b</math> i <math>r \mid m</math>, skąd otrzymujemy, że <math>r \mid s t</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Polska|Hide=Polska}}
−
 
+
*[[Manewry polityczne i nie tylko]]
−
<span id="H8" style="font-size: 110%; font-weight: bold;">Twierdzenie H8</span><br/>
+
*[[Referendum, wybory, jednomandatowe okręgi wyborcze (1)]]
−
Jeżeli liczby <math>a, b</math> są względnie pierwsze, to
+
*[[Referendum, wybory, jednomandatowe okręgi wyborcze (2)]]
−
 
+
*[[Referendum, wybory, jednomandatowe okręgi wyborcze (3)]]
−
::<math>\gcd (a b, m) = \gcd (a, m) \cdot \gcd (b, m)</math>
+
*[[Refleksje]]
−
 
+
*[[Kreacja pieniądza. Rząd vs. banki.]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+
*[[III RP – kraj w którym żyjesz]]
−
Wprowadźmy oznaczenia
+
*[[III RP - krajem faszystów]]
−
 
+
*[[Konsultacje KRRiT - odpowiedź]]
−
::<math>r = \gcd (a b, m)</math>
+
*[[Co stało by się ze światem, gdyby krowy zrozumiały, że potrafią latać?]]
−
 
+
*[[Pełnosprawni też mają prawa!]]
−
::<math>s = \gcd (a, m)</math>
+
*[[Smoleńskie pytania]]
−
 
+
*[[Dlaczego należy zlikwidować abonament RTV]]
−
::<math>t = \gcd (b, m)</math>
+
*[[Bajki o braniu odpowiedzialności]]
−
 
+
*[[Nieudolność może być przestępstwem]]
−
Z założenia <math>\gcd (a, b) = 1</math>. Ponieważ <math>s \mid a</math> oraz <math>t \mid b</math>, to <math>\gcd (s, t) = 1</math>, zatem (zobacz C75)
+
*[[Panie premierze, coś trzeba zrobić!]]
−
 
+
*[[Nie jestem Charlie]]
−
::<math>s \mid a \qquad \,\, \text{i} \qquad t \mid b \qquad \qquad \;\, \Longrightarrow \qquad \qquad s t \mid a b</math>
+
*[[Polska – Chiny. Szokujące porównanie.]]
−
 
+
*[[Nadzwyczajne przemówienie]]
−
::<math>s \mid m \qquad \text{i} \qquad t \mid m \qquad \qquad \Longrightarrow \qquad \qquad s t \mid m</math>
+
*[[Europa czy dyktatura ciemniaków?]]
−
 
+
*[[HejtStop kontra Pudzianowski]]
−
Wynika stąd, że <math>s t \mid \gcd (a b, m)</math>, czyli <math>s t \mid r</math>. Z&nbsp;poprzedniego twierdzenia wiemy, że <math>r \mid s t</math>, zatem <math>|r| = |s t|</math>. Co kończy dowód.<br/>
+
*[[Demokracja czy dyktatura Sądu Najwyższego?]]
−
&#9633;
+
*[[Witaj w świecie obrońców zygot i przyjaciół morderców]]
 +
*[[Ksenofobia może uratować ci życie]]
 +
*[[UE – 27 milczących ludzi]]
 +
*[[Przemówienie prezydenta Donalda Trumpa w Warszawie]]
 +
*[[Wieluń]]
 +
*[[Bezpłodność. Feminizm. Homoseksualizm. Czy damy radę?]]
 +
*[[Murzyni. Czy czarne jest piękne?]]
 +
*[[IQ, rozkład Gaussa i czarno-białe konsekwencje]]
 +
*[[Aborcja – orzeczenie Trybunału Konstytucyjnego z 1997 roku]]
 
{{\Spoiler}}
 
{{\Spoiler}}
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Prawo – artykuł 257 kodeksu karnego|Hide=Prawo – artykuł 257 kodeksu karnego}}
−
 
+
*[[Co nam jeszcze wolno powiedzieć?]]
−
<span id="H9" style="font-size: 110%; font-weight: bold;">Twierdzenie H9</span><br/>
+
*[[Artykuł 257 kodeksu karnego – dalsze rozważania]]
−
Jeżeli liczby <math>b, m</math> są względnie pierwsze, to
+
*[[Małpy w zoo]]
−
 
+
*[[HejtStop kontra Pudzianowski]]
−
::<math>\gcd (a b, m) = \gcd (a, m)</math>
 
−
 
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Wprowadźmy oznaczenia
 
−
 
 
−
::<math>r = \gcd (a b, m)</math>
 
−
 
 
−
::<math>s = \gcd (a, m)</math>
 
−
 
 
−
Z lematu Bézouta istnieją takie liczby <math>x, y</math>, że
 
−
 
 
−
::<math>r = a b x + m y</math>
 
−
 
 
−
Ale <math>s \mid a \;</math> i <math>\; s \mid m</math>, zatem <math>s \mid r</math>.
 
−
 
 
−
Z założenia <math>\gcd (b, m) = 1</math>, zatem z&nbsp;twierdzenia [[#H7|H7]] wynika natychmiast, że <math>r \mid s</math>. Ponieważ <math>s \mid r \;</math> i <math>\; r \mid s</math>, to <math>| r | = | s |</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
 +
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Lewactwo|Hide=Lewactwo}}
 +
<br/><div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Nie logika, lecz chęć szczera zrobi z ciebie myśliciela.</div><br/>
  
 +
<div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Nam bajki trzeba pisać. Powiem więcej: brednie... Niech przy naszych bajkach nawet prawda zblednie.</div><br/>
  
−
<span id="H10" style="font-size: 110%; font-weight: bold;">Twierdzenie H10</span><br/>
+
<div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Ślepi prowadzą ociemniałych ku świetlanej przyszłości.</div><br/>
−
Jeżeli liczby <math>a, b</math> nie są jednocześnie równe zero i <math>m \neq 0</math>, to
 
−
 
 
−
::<math>\gcd (a m, b m) = | m | \cdot \gcd (a, b)</math>
 
−
 
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Oznaczmy <math>d = \gcd (a, b) \;</math> i <math>\; D = \gcd (a m, b m)</math>. Pokażemy, że <math>d m \mid D</math>.
 
  
−
<div style="margin-top: 1.5em; margin-bottom: 1em;">
+
<div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Czytasz: "Dla nas najważniejszy jest człowiek" i myślisz, że to o Tobie mówią? To błąd. Człowiek to pederasta, lesbijka, zboczeniec, morderca, gwałciciel, złodziej, bandyta, feministka, uchodźca, imigrant, a w ostateczności niepełnosprawny. Jeśli nie zaliczasz się do wymienionych, to nie o Tobie mówią...</div><br/>
−
::<math>
 
−
\begin{array}{llll}
 
−
  d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d \mid a \quad \text{i} \quad d \mid b & \text{(zobacz H3)} \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & d m \mid a m \quad \text{i} \quad d m \mid b m & \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & d m \mid \gcd (a m, b m) & \text{(zobacz H3)} \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & d m \mid D & \\
 
−
\end{array}
 
−
</math>
 
−
</div>
 
  
−
Pokażemy, że <math>D \mid d m</math>.
+
<div style="font-size: 95%; line-height: 1.1em; font-style: italic; font-weight: bold;color: #808080;">Nawet Kościół nie obieca wam takiego raju w niebie, jaki lewactwo obieca wam na ziemi.</div><br/>
  
−
<div style="margin-top: 1.5em; margin-bottom: 1em;">
+
*[[Zrówność jako podstawa lewackiej ideologii]]
−
::<math>
+
*[[Lewactwo – przyczyny politycznego obłędu (Lyle Rossiter)]]
−
\begin{array}{llll}
+
*[[Bezpłodność. Feminizm. Homoseksualizm. Czy damy radę?]]
−
  d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d = a x + b y & \text{(lemat Bézouta C73)} \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & d m = a m x + b m y & \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & D \mid d m & \\
 
−
\end{array}
 
−
</math>
 
−
</div>
 
−
 
 
−
Ostatnia implikacja korzysta z&nbsp;tego, że <math>D \mid a m \;</math> i <math>\; D \mid b m</math> (zobacz [[#H3|H3]]). Ponieważ <math>d m \mid D \;</math> i <math>\; D \mid d m</math>, to <math>| D | = | d m |</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Pederaści, lesbijki i homopropaganda|Hide=Pederaści, lesbijki i homopropaganda}}
−
 
+
*[[Marsz ku tęczy]]
−
<span style="font-size: 110%; font-weight: bold;">Zadanie H11</span><br/>
+
*[[Pederaści i lesbijki – cud uzdrowienia]]
−
Pokazać, że jeżeli liczby <math>a, b</math> nie są jednocześnie równe zero, to
+
*[[Domagajmy się ustawy zakazującej homopropagandy!]]
−
 
+
*[[Czy już idą po Cejrowskiego?]]
−
::<math>\gcd \left( {\small\frac{a}{\gcd (a, b)}}, {\small\frac{b}{\gcd (a, b)}} \right) = 1</math>
+
*[[Zrówność jako podstawa lewackiej ideologii]]
−
 
+
*[[Homopropaganda – 10 zasad prowadzenia debaty (Scott Lively)]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
+
*[[Jak pokonać homopropagandę? (Scott Lively)]]
−
Z twierdzenia H10 otrzymujemy
+
*[[Jeśli kochasz swoje dzieci, protestuj przeciwko homopropagandzie]]
−
 
+
*[[Bezpłodność. Feminizm. Homoseksualizm. Czy damy radę?]]
−
::<math>\gcd (a, b) = \gcd \left( \gcd (a, b) \cdot {\small\frac{a}{\gcd (a, b)}}, \gcd (a, b) \cdot {\small\frac{b}{\gcd (a, b)}} \right)</math>
+
*[[Komu zagraża tęczowa zaraza?]]
−
 
 
−
::::<math>\;\;\;\; = \gcd (a, b) \cdot \gcd \left( {\small\frac{a}{\gcd (a, b)}}, {\small\frac{b}{\gcd (a, b)}} \right)</math>
 
−
 
 
−
Zatem
 
−
 
 
−
::<math>\gcd \left( {\small\frac{a}{\gcd (a, b)}}, {\small\frac{b}{\gcd (a, b)}} \right) = 1</math>
 
−
 
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Wiersze|Hide=Wiersze}}
−
 
+
*[[NIE!]]
−
<span id="H12" style="font-size: 110%; font-weight: bold;">Zadanie H12</span><br/>
+
*[[ONI]]
−
Pokazać, że <math>a \mid b</math> wtedy i&nbsp;tylko wtedy, gdy <math>a \mid \gcd (a, b)</math>.
+
*[[Historia się powtarza]]
−
 
+
*[[MÓJ NARODZIE]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
+
*[[Marsz ku tęczy]]
−
 
+
*[[Ludziom honoru]]
−
<math>\Large{\Longrightarrow}</math>
+
*[[POMNIK TRUPA]]
−
 
+
*[[Przyzwoitość]]
−
Zakładając, że <math>a \mid b</math>, dostajemy
+
*[[Wieluń]]
−
 
 
−
<div style="margin-top: 1.5em; margin-bottom: 1em;">
 
−
::<math>
 
−
\begin{array}{llll}
 
−
  a \mid b & \qquad \Longrightarrow \qquad & b = k a & \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & \gcd (a, b) = \gcd (a, k a) = | a | \cdot \gcd (1, k) = | a | & \qquad \text{(zobacz H10)} \\
 
−
  &  &  & \\
 
−
  & \qquad \Longrightarrow \qquad & a \mid \gcd (a, b) & \\
 
−
\end{array}
 
−
</math>
 
−
</div>
 
−
 
 
−
<math>\Large{\Longleftarrow}</math>
 
−
 
 
−
Jeżeli <math>a \mid \gcd (a, b)</math>, to <math>a \mid b</math> (zobacz [[#H3|H3]]). Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
 
−
 
 
−
 
 
−
<span id="H13" style="font-size: 110%; font-weight: bold;">Zadanie H13</span><br/>
 
−
Niech <math>\gcd (a, d) = 1</math>. Pokazać, że <math>d \nmid a b</math> wtedy i&nbsp;tylko wtedy, gdy <math>d \nmid b</math>.
 
−
 
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Korzystając z&nbsp;rezultatu pokazanego w&nbsp;zadaniu [[#H12|H12]], dostajemy
 
−
 
 
−
<div style="margin-top: 1.5em; margin-bottom: 1em;">
 
−
::<math>
 
−
\begin{array}{llll}
 
−
  d \nmid a b & \qquad \Longleftrightarrow \qquad & d \nmid \gcd (d, a b) & \\
 
−
  &  &  & \\
 
−
  & \qquad \Longleftrightarrow \qquad & d \nmid \gcd (d, b) & \text{(zobacz H9)} \\
 
−
  &  &  & \\
 
−
  & \qquad \Longleftrightarrow \qquad & d \nmid b & \\
 
−
\end{array}
 
−
</math>
 
−
</div>
 
−
 
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
−
 
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Edukacja|Hide=Edukacja}}
−
 
+
*[[Twierdzenie Czebyszewa o funkcji π(n)|A. Twierdzenie Czebyszewa o funkcji <math>\pi (n)</math>]]
−
<span id="H14" style="font-size: 110%; font-weight: bold;">Twierdzenie H14</span><br/>
+
*[[Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n|B. Twierdzenie Czebyszewa o liczbie pierwszej między <math>n</math> i <math>2 n</math>]]
−
Jeżeli dodatnie liczby <math>a, b</math> są względnie pierwsze, to każdy dzielnik <math>d</math> iloczynu <math>a b</math> można przedstawić jednoznacznie w&nbsp;postaci <math>d = d_1 d_2</math>, gdzie <math>d_1 \mid a ,</math> <math>\; d_2 \mid b \;</math> <math>\text{i} \; \gcd (d_1, d_2) = 1</math>.
+
*[[Ciągi liczbowe|C. Ciągi liczbowe]]
−
 
+
*[[Szeregi liczbowe|D. Szeregi liczbowe]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+
*[[Wzór Eulera-Maclaurina|E. Wzór Eulera-Maclaurina]]
−
Niech <math>d_1 = \gcd (d, a) \;</math> i <math>\; d_2 = \gcd (d, b)</math>. Z&nbsp;twierdzenia [[#H8|H8]] mamy
+
*[[Całkowanie numeryczne. Metoda Simpsona|F. Całkowanie numeryczne. Metoda Simpsona]]
−
 
+
*[[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera|H. Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera]]
−
::<math>d_1 d_2 = \gcd (d, a) \cdot \gcd (d, b) = \gcd (d, a b) = d</math>
+
*[[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego|J. CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego]]
−
 
+
*[[Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia|K. Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia]]
−
Bo z&nbsp;założenia <math>d \mid a b</math>. Z&nbsp;definicji największego wspólnego dzielnika i&nbsp;zadania [[#H3|H3]] dostajemy
+
*[[Rząd liczby modulo i generatory modulo. Kongruencje wielomianowe. Lemat Hensela|L. Rząd liczby modulo i generatory modulo. Kongruencje wielomianowe. Lemat Hensela]]
−
 
+
*[[Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze|M. Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze]]
−
::<math>\gcd (d_1, d_2) = e \qquad \Longrightarrow \qquad e \mid d_1 \quad \text{i} \quad e \mid d_2</math>
+
*[[Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW|N. Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW]]
−
 
+
*[[Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju|P. Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju]]
−
::::::::<math>\, \Longrightarrow \qquad e \mid \gcd (d, a) \quad \text{i} \quad e \mid \gcd (d, b)</math>
+
*[[Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy|Q. Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy]]
−
 
+
*[[Liczby losowe – metoda odwracania dystrybuanty]]
−
::::::::<math>\, \Longrightarrow \qquad e \mid a \quad \text{i} \quad e \mid b</math>
+
*[[Nadciśnienie tętnicze – leki]]
−
 
+
*[[Dynamika rozprzestrzeniania się koronawirusa SARS-CoV-2 w Polsce]]
−
::::::::<math>\, \Longrightarrow \qquad e \mid \gcd (a, b)</math>
+
*[[LibreOffice Calc – makra – przykłady]]
−
 
+
*[[Kalendarz juliański i kalendarz gregoriański]]
−
::::::::<math>\, \Longrightarrow \qquad \gcd (a, b) \geqslant e</math>
 
−
 
 
−
Gdyby było <math>\gcd (d_1, d_2) = e > 1</math>, to mielibyśmy <math>\gcd (a, b) \geqslant e > 1</math>. Wbrew założeniu, że <math>\gcd (a, b) = 1</math>. Co kończy dowód.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
 
−
 
 
−
 
 
−
<span id="H15" style="font-size: 110%; font-weight: bold;">Twierdzenie H15</span><br/>
 
−
Jeżeli <math>a, m, n \in \mathbb{Z}_+</math>, to
 
−
 
 
−
::<math>\gcd (a^m - 1, a^n - 1) = a^{\gcd (m, n)} - 1</math>
 
−
 
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Pokażemy najpierw, że jeżeli <math>d</math> jest dzielnikiem lewej strony dowodzonej równości, to jest również dzielnikiem prawej strony i&nbsp;odwrotnie.
 
−
 
 
−
<math>\Large{\Longrightarrow}</math>
 
−
 
 
−
Z założenia <math>d</math> jest dzielnikiem <math>\gcd (a^m - 1, a^n - 1)</math>, czyli <math>d \mid (a^m - 1) \;</math> i <math>\; d \mid (a^n - 1)</math>, co możemy zapisać w&nbsp;postaci
 
−
 
 
−
::<math>a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d}</math>
 
−
 
 
−
Z lematu Bézouta (zobacz C73) wiemy, że istnieją takie liczby <math>x, y</math>, że <math>\gcd (m, n) = m x + n y</math>. Łatwo znajdujemy, że
 
−
 
 
−
::<math>a^{\gcd (m, n)} \equiv a^{m x + n y} \equiv (a^m)^x \cdot (a^n)^y \equiv 1^x \cdot 1^y \equiv 1 \!\! \pmod{d}</math>
 
−
 
 
−
Czyli <math>d \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right)</math>.
 
−
 
 
−
<math>\Large{\Longleftarrow}</math>
 
−
 
 
−
Z założenia <math>d \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right)</math>, czyli
 
−
 
 
−
::<math>a^{\gcd (m, n)} \equiv 1 \!\! \pmod{d}</math>
 
−
 
 
−
Zatem
 
−
 
 
−
::<math>a^m \equiv \left[ a^{\gcd (m, n)} \right]^{\tfrac{m}{\gcd (m, n)}} \equiv 1 \!\! \pmod{d}</math>
 
−
 
 
−
Podobnie otrzymujemy
 
−
 
 
−
::<math>a^n \equiv 1 \!\! \pmod{d}</math>
 
−
 
 
−
Zatem <math>d</math> dzieli <math>a^m - 1 \;</math> i <math>\; a^n - 1</math>, czyli
 
−
 
 
−
::<math>d \mid \gcd (a^m - 1, a^n - 1)</math>
 
−
 
 
−
 
 
−
W szczególności wynika stąd, że
 
−
 
 
−
:*&nbsp;&nbsp;&nbsp;<math>\gcd (a^m - 1, a^n - 1) \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right)</math>
 
−
 
 
−
:*&nbsp;&nbsp;&nbsp;<math>\left( a^{\gcd (m, n)} - 1 \right) \, \biggr\rvert \, \gcd (a^m - 1, a^n - 1)</math>
 
−
 
 
−
Czyli <math>\left| \gcd (a^m - 1, a^n - 1) \right| = \left| a^{\gcd (m, n)} - 1 \right|</math>. Co kończy dowód.<br/>
 
−
&#9633;
 
 
{{\Spoiler}}
 
{{\Spoiler}}
  
  
  
−
<span id="H16" style="font-size: 110%; font-weight: bold;">Uwaga H16</span><br/>
+
{{Spoiler|Style=font-size:1.5em; color:#000|Show=Najnowsze artykuły|Hide=Najnowsze artykuły}}
−
W dowodzie twierdzenia [[#H15|H15]] pominęliśmy milczeniem fakt, że jedna z&nbsp;liczb <math>x, y</math> może być (i często jest) ujemna. Choć rezultat jest prawidłowy, to nie wiemy, co oznacza zapis
+
*[[Rząd liczby modulo i generatory modulo. Kongruencje wielomianowe. Lemat Hensela]]
−
 
+
*[[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera]]
−
::<math>a^{- 1000} \equiv 1^{- 10} \equiv 1 \!\! \pmod{d}</math>
+
*[[Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy]]
−
 
+
*[[Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju]]
−
Omówimy ten problem w&nbsp;następnej sekcji. Zauważmy, wyprzedzając materiał, że z&nbsp;kongruencji
+
*[[Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia]]
−
 
+
*[[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego]]
−
::<math>a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d}</math>
+
*[[Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW]]
−
 
+
*[[Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze]]
−
wynika, że <math>\gcd (a, d) = 1</math> i&nbsp;liczba <math>a</math> ma element odwrotny modulo <math>d</math>.
+
*[[Przemówienie premiera Viktora Orbána na 31. Letnim Wolnym Uniwersytecie Bálványos]]
−
 
+
*[[Całkowanie numeryczne. Metoda Simpsona]]
−
 
+
*[[Wzór Eulera-Maclaurina]]
−
 
+
*[[Szeregi liczbowe]]
−
 
+
*[[Ciągi liczbowe]]
−
 
+
*[[Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n|Twierdzenie Czebyszewa o liczbie pierwszej między <math>n</math> i <math>2 n</math>]]
−
== Element odwrotny modulo <math>m</math> ==
+
*[[Twierdzenie Czebyszewa o funkcji π(n)|Twierdzenie Czebyszewa o funkcji <math>\pi (n)</math>]]
−
 
+
*[[Prawo do życia, czyli zwycięstwo hipokryzji]]
−
<span id="H17" style="font-size: 110%; font-weight: bold;">Twierdzenie H17</span><br/>
+
*[[Krótkie historie o zabijaniu]]
−
Niech <math>m \in \mathbb{Z}_+</math>. Dla liczby <math>a \in \mathbb{Z}</math> istnieje taka liczba <math>x</math>, że
+
*[[LibreOffice Calc – makra – przykłady]]
−
 
+
*[[Dynamika rozprzestrzeniania się koronawirusa SARS-CoV-2 w Polsce]]
−
::<math>a x \equiv 1 \!\! \pmod{m}</math>
+
*[[Liczby losowe – metoda odwracania dystrybuanty]]
−
 
+
*[[Aborcja – orzeczenie Trybunału Konstytucyjnego z 1997 roku]]
−
wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (a, m) = 1</math>.
+
*[[Nadciśnienie tętnicze – leki]]
−
 
+
*[[Kara śmierci – cytaty]]
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+
*[[Jak to z moratorium było|Jak to z moratorium było - uzupełnienie!]]
−
 
+
*[[Porozmawiajmy o argumentach – „Rozważania… ” Camusa]]
−
<math>\Large{\Longrightarrow}</math>
+
*[[Komu zagraża tęczowa zaraza?]]
−
 
+
*[[George Orwell – uraz psychiczny czy rzeczywistość?]]
−
Z założenia istnieje taka liczba <math>x</math>, że
+
*[[Albert Camus – fobia czy rzeczywistość?]]
−
 
+
*[[Crime International – Polska 2018]]
−
::<math>a x \equiv 1 \!\! \pmod{m}</math>
+
*[[Banalizacja zła]]
−
 
+
*[[IQ, rozkład Gaussa i czarno-białe konsekwencje]]
−
Zatem dla pewnego <math>k \in \mathbb{Z}</math> jest
+
*[[Pomyłka sądowa – prawie niewinny morderca Marlene Miller]]
−
 
+
*[[Sąd Najwyższy USA: czarne jest najpiękniejsze]]
−
::<math>a x = 1 + k m</math>
+
*[[Arthur Schopenhauer: godność ludzka czyli nowe szaty króla]]
−
 
+
*[[Kalendarz juliański i kalendarz gregoriański]]
−
Czyli <math>a x - k m = 1</math>. Wynika stąd, że <math>\gcd (a, m)</math> dzieli <math>1</math>, co oznacza, że <math>\gcd (a, m) = 1</math>.
+
*[[Crime International – Polska 2017]]
−
 
+
*[[Prawa człowieka czy prawa bandyty? Przyrodzona godność ludzka]]
−
<math>\Large{\Longleftarrow}</math>
+
*[[Prawie niewinni mordercy. Co jeszcze jesteś gotów dla nich uczynić?]]
−
 
+
*[[Murzyni. Czy czarne jest piękne?]]
−
Z założenia <math>\gcd (a, m) = 1</math>. Z&nbsp;lematu Bézouta (zobacz C73) wynika, że istnieją takie liczby całkowite <math>x, y</math>, że
+
*[[Bezpłodność. Feminizm. Homoseksualizm. Czy damy radę?]]
−
 
+
*[[Wieluń]]
−
::<math>a x + m y = 1</math>
+
*[[Jeśli kochasz swoje dzieci, protestuj przeciwko homopropagandzie]]
−
 
+
*[[Przemówienie prezydenta Donalda Trumpa w Warszawie]]
−
Zatem modulo <math>m</math> dostajemy
+
*[[Wielokrotni mordercy – typologia i przykłady]]
−
 
+
*[[Przyzwoitość]]
−
::<math>a x \equiv 1 \!\! \pmod{m}</math>
+
*[[Za drugą szansę zabójcy możesz zapłacić życiem]]
−
 
+
*[[UE – 27 milczących ludzi]]
−
Co kończy dowód.<br/>
+
*[[Crime International – Polska 2016]]
−
&#9633;
+
*[[Lewactwo – przyczyny politycznego obłędu (Lyle Rossiter)]]
 +
*[[Ksenofobia może uratować ci życie]]
 +
*[[Jak pokonać homopropagandę? (Scott Lively)]]
 +
*[[Homopropaganda – 10 zasad prowadzenia debaty (Scott Lively)]]
 +
*[[Zrówność jako podstawa lewackiej ideologii]]
 +
*[[Crime International – Polska 2015]]
 +
*[[Witaj w świecie obrońców zygot i przyjaciół morderców]]
 +
*[[Demokracja czy dyktatura Sądu Najwyższego?]]
 +
*[[HejtStop kontra Pudzianowski]]
 +
*[[Stany Zjednoczone, Murzyni, zabójstwa, kara śmierci i odstraszanie]]
 +
*[[Kara śmierci w Stanach Zjednoczonych]]
 +
*[[Europa czy dyktatura ciemniaków?]]
 +
*[[Czy kara śmierci ratuje życie?]]
 +
*[[Morderstwa, egzekucje, odstraszanie - amerykański eksperyment]]
 +
*[[Nadzwyczajne przemówienie]]
 +
*[[Kara śmierci: kto nie ma topora, a kto ma karabin (Polska)]]
 +
*[[Polska – Chiny. Szokujące porównanie.]]
 +
*[[Lepiej, aby zginęło stu niewinnych, niż gdyby jeden winny miał zginąć]]
 +
*[[Pomyłki sądowe – mordercy którym pozwolono zabić ponownie]]
 +
*[[Czy kara śmierci odstrasza?]]
 +
*[[Kara śmierci: lista państw świata według wskaźnika reakcji]]
 +
*[[Śmierć i Sprawiedliwość (Edward I. Koch)]]
 +
*[[Kara śmierci: topór kontra karabin maszynowy (Japonia)]]
 +
*[[Kara śmierci: topór kontra karabin maszynowy (USA)]]
 +
*[[Nie jestem Charlie]]
 +
*[[Jak postęp zapewnił bezpieczeństwo mordercom i zbrodniarzom]]
 +
*[[Księga powtórnie powtórzonego prawa]]
 +
*[[CBOS – czy poznamy stosunek Polaków do kary śmierci?]]
 +
*[[POMNIK TRUPA]]
 
{{\Spoiler}}
 
{{\Spoiler}}
  
  
  
−
<span id="H18" style="font-size: 110%; font-weight: bold;">Definicja H18</span><br/>
+
{|style="border-left:solid 15px #9FFB88; border-right:solid 15px #9FFB88; border-top:solid 10px #9FFB88; border-bottom:solid 10px #9FFB88; text-align:justify; font-size: 90%; font-style: italic; background-color: #9FFB88; font-weight: bold; "
−
Niech <math>m \in \mathbb{Z}_+</math>. Liczbę <math>x</math> taką, że
+
|
 +
Drogi Czytelniku!<br/><br/>
 +
Przygotowanie niektórych artykułów wymagało nawet kilkudziesięciu godzin pracy. Większość tekstów to nie są felietony, a&nbsp;opracowania i&nbsp;tłumaczenia, których próżno szukać w&nbsp;mediach głównego nurtu. Jeśli chciałbyś dobrowolnie wesprzeć ten wysiłek i&nbsp;pomóc w&nbsp;rozwoju strony, proszę o&nbsp;dokonanie wpłaty na podane niżej konto bankowe.<br/><br/>
 +
Dziękuję za Twoją życzliwą pomoc!<br/>
 +
Henryk Dąbrowski
  
−
::<math>a \cdot x \equiv 1 \!\! \pmod{m}</math>
 
  
−
będziemy nazywali elementem odwrotnym liczby <math>a</math> modulo <math>m</math> i&nbsp;oznaczali jako <math>a^{- 1}</math>.
 
  
  
 +
<html>
 +
<form action="https://www.paypal.com/cgi-bin/webscr" method="post" target="_top">
 +
<input type="hidden" name="cmd" value="_s-xclick">
 +
<input type="hidden" name="hosted_button_id" value="Y2RF4E2DLZL6Y">
 +
<input type="image" src="https://www.paypalobjects.com/pl_PL/PL/i/btn/btn_donate_LG.gif" border="0" name="submit" alt="PayPal – Płać wygodnie i bezpiecznie">
 +
<img alt="" border="0" src="https://www.paypalobjects.com/pl_PL/i/scr/pixel.gif" width="1" height="1">
 +
</form>
 +
</html>
  
−
<span id="H19" style="font-size: 110%; font-weight: bold;">Uwaga H19</span><br/>
+
[[Konto bankowe|Dane konta bankowego do wykonania wpłaty]]
−
Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli <math>b \mid a</math> oraz <math>b</math> ma element odwrotny modulo <math>m</math>, to prawdziwa jest kongruencja
 
  
−
::<math>{\small\frac{a}{b}} \equiv a b^{- 1} \!\! \pmod{m}</math>
 
  
−
Istotnie
+
[[Wpłaty]]
−
 
 
−
::<math>{\small\frac{a}{b}} = {\small\frac{a}{b}} \cdot 1 \equiv {\small\frac{a}{b}} \cdot b b^{- 1} \equiv a b^{- 1} \!\! \pmod{m}</math>
 
−
 
 
−
W PARI/GP odwrotność liczby <math>a</math> modulo <math>m</math> znajdujemy, wpisując <code>Mod(a, m)^(-1)</code>.
 
−
 
 
−
 
 
−
 
 
−
<span id="H20" style="font-size: 110%; font-weight: bold;">Twierdzenie H20</span><br/>
 
−
Niech <math>a, k \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math>. Poniższa tabelka przedstawia elementy odwrotne do elementu <math>a</math> w&nbsp;przypadku niektórych modułów <math>m</math>. W&nbsp;szczególności, jeżeli moduł <math>m</math> jest liczbą nieparzystą, to <math>2^{- 1} \equiv {\small\frac{m + 1}{2}} \!\! \pmod{m}</math>.
 
−
 
 
−
::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
 
−
|-
 
−
!  || postać <br/> modułu <math>\boldsymbol{m}</math> || odwrotność <br/> elementu <math>\boldsymbol{a}</math> || uwagi
 
−
|-
 
−
| <math>1.</math> || <math>m = 2</math> || <math>1</math> || rowspan = 3 | liczba <math>a</math> <br/> jest liczbą <br/> nieparzystą
 
−
|-
 
−
| <math>2.</math> || <math>m = 4</math> || <math>R_4(a)</math>
 
−
|-
 
−
| <math>3.</math> || <math>m = 8</math> || <math>R_8(a)</math>
 
−
|-
 
−
| <math>4.</math> || <math>m = a k - 1</math> || <math>{\small\frac{m + 1}{a}}</math> || <math></math>
 
−
|-
 
−
| <math>5.</math> || <math>m = a k + 1</math> || <math>- {\small\frac{m - 1}{a}}</math> || <math></math>
 
−
|-
 
−
| <math>6.</math> || <math>m = a k - 2</math> || <math>{\small\frac{m + 1}{2}} \cdot {\small\frac{m + 2}{a}}</math> || rowspan = 2 | liczby <math>a , m</math> <br/> są liczbami <br/> nieparzystymi
 
−
|-
 
−
| <math>7.</math> || <math>m = a k + 2</math> || <math>{\small\frac{m - 1}{2}} \cdot {\small\frac{m - 2}{2}}</math>
 
 
|}
 
|}
  
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
 
−
'''Punkty 1. - 3.'''
 
−
 
−
Ponieważ dla liczb nieparzystych jest
 
−
 
−
::<math>a^2 \equiv 1 \!\! \pmod{2}</math>
 
−
 
−
::<math>a^2 \equiv 1 \!\! \pmod{4}</math>
 
−
 
−
::<math>a^2 \equiv 1 \!\! \pmod{8}</math>
 
−
 
−
to liczba nieparzysta <math>a</math> jest swoją odwrotnością modulo <math>2</math>, <math>4</math> i <math>8</math>. Ponieważ element odwrotny jest definiowany modulo, zatem możemy napisać
 
−
 
−
::<math>a^{- 1} \equiv R_2 (a) \!\! \pmod{2}</math>
 
−
 
−
::<math>a^{- 1} \equiv R_4 (a) \!\! \pmod{4}</math>
 
−
 
−
::<math>a^{- 1} \equiv R_8 (a) \!\! \pmod{8}</math>
 
−
 
−
W pierwszym przypadku wynik jest oczywisty, bo <math>R_2 (a) = 1</math>.
 
−
 
−
'''Punkt 4.'''
 
−
 
−
Zauważmy, że
 
−
 
−
::<math>\gcd (a, m) = \gcd (a, a k - 1) = \gcd (a, - 1) = 1</math>
 
−
 
−
oraz <math>a \mid (m + 1)</math>. Zatem
 
−
 
−
::<math>a \cdot a^{- 1} = a \cdot {\small\frac{m + 1}{a}} = m + 1 \equiv 1 \!\! \pmod{m}</math>
 
−
 
−
'''Punkt 5.'''
 
−
 
−
Zauważmy, że
 
−
 
−
::<math>\gcd (a, m) = \gcd (a, a k + 1) = \gcd (a, 1) = 1</math>
 
−
 
−
oraz <math>a \mid (m - 1)</math>. Zatem
 
−
 
−
::<math>a \cdot a^{- 1} = a \cdot \left[ - \left( {\small\frac{m - 1}{a}} \right) \right] = - m + 1 \equiv 1 \!\! \pmod{m}</math>
 
−
 
−
'''Punkt 6.'''
 
−
 
−
Ponieważ zakładamy, że <math>2 \mid (m + 1)</math>, to <math>m</math> musi być liczbą nieparzystą, czyli <math>a</math> też musi być liczbą nieparzystą. Zauważmy, że
 
−
 
−
::<math>\gcd (a, m) = \gcd (a, a k - 2) = \gcd (a, - 2) = 1</math>
 
−
 
−
oraz <math>a \mid (m + 2)</math>. Zatem
 
−
 
−
::<math>a \cdot a^{- 1} = a \cdot \left( {\small\frac{m + 1}{2}} \cdot {\small\frac{m + 2}{a}} \right) = {\small\frac{m + 1}{2}} \cdot (m + 2) \equiv {\small\frac{m + 1}{2}} \cdot 2 \equiv m + 1 \equiv 1 \!\! \pmod{m}</math>
 
−
 
−
Podobnie pokazujemy punkt 7. Co kończy dowód.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H21" style="font-size: 110%; font-weight: bold;">Twierdzenie H21</span><br/>
 
−
Niech <math>a, b \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math> i&nbsp;liczba <math>a</math> ma element odwrotny modulo <math>m</math>. Jeżeli liczby <math>u_1, u_2, \ldots, u_r</math> są liczbami różnymi modulo <math>m</math>, to liczby
 
−
 
−
::1.&nbsp;&nbsp;&nbsp;<math>a u_1, a u_2, \ldots, a u_r</math>
 
−
 
−
::2.&nbsp;&nbsp;&nbsp;<math>a u_1 + b, a u_2 + b, \ldots, a u_r + b</math>
 
−
 
−
są liczbami różnymi modulo <math>m</math>. Jeżeli ponadto liczby <math>u_1, u_2, \ldots, u_r</math> są względnie pierwsze z <math>m</math>, to również liczby
 
−
 
−
::3.&nbsp;&nbsp;&nbsp;<math>u^{- 1}_1, u^{- 1}_2, \ldots, u^{- 1}_r</math>
 
−
 
−
są liczbami różnymi modulo <math>m</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
 
−
'''Punkt 1.'''
 
−
 
−
Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki <math>i, j</math>, że
 
−
 
−
::<math>a u_i \equiv a u_j \!\! \pmod{m}</math>
 
−
 
−
Z założenia liczba <math>a</math> ma element odwrotny modulo <math>m</math>, zatem mnożąc obie strony kongruencji przez <math>a^{- 1}</math>, otrzymujemy
 
−
 
−
::<math>u_i \equiv u_j \!\! \pmod{m}</math>
 
−
 
−
dla <math>i \neq j</math>, wbrew założeniu, że liczby <math>u_1, u_2, \ldots, u_r</math> są różne modulo <math>m</math>. Dowód punktu 2. jest analogiczny.
 
−
 
−
'''Punkt 3.'''
 
−
 
−
Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki <math>i, j</math>, że
 
−
 
−
::<math>u^{- 1}_i \equiv u^{- 1}_j \!\! \pmod{m}</math>
 
−
 
−
::<math>u_j u^{- 1}_i \equiv 1 \!\! \pmod{m}</math>
 
−
 
−
::<math>u_j u^{- 1}_i u_i \equiv u_i \!\! \pmod{m}</math>
 
−
 
−
::<math>u_j \equiv u_i \!\! \pmod{m}</math>
 
−
 
−
Ponownie otrzymujemy <math>u_i \equiv u_j \!\! \pmod{m}</math> dla <math>i \neq j</math>, wbrew założeniu, że liczby <math>u_1, u_2, \ldots, u_r</math> są różne modulo <math>m</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H22" style="font-size: 110%; font-weight: bold;">Zadanie H22</span><br/>
 
−
Niech <math>p</math> będzie liczbą pierwszą. Pokazać, że dla <math>k \in [0, p - 1]</math> prawdziwa jest kongruencja
 
−
 
−
::<math>\binom{p - 1}{k} \equiv (- 1)^k \pmod{p}</math>
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Zauważmy, że modulo <math>p</math> mamy
 
−
 
−
::<math>\binom{p - 1}{k} = {\small\frac{(p - 1) !}{k! \cdot (p - 1 - k) !}}</math>
 
−
 
−
::::<math>\;\;\;\; = {\small\frac{(p - 1) (p - 2) \cdot \ldots \cdot (p - k)}{k!}}</math>
 
−
 
−
::::<math>\;\;\;\; \equiv (p - 1) (p - 2) \cdot \ldots \cdot (p - k) \cdot (k!)^{- 1}</math>
 
−
 
−
::::<math>\;\;\;\; \equiv (- 1)^k \cdot k! \cdot (k!)^{- 1}</math>
 
−
 
−
::::<math>\;\;\;\; \equiv (- 1)^k \pmod{p}</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H23" style="font-size: 110%; font-weight: bold;">Zadanie H23</span><br/>
 
−
Niech <math>A</math> i <math>B</math> będą zbiorami skończonymi. Pokazać, że jeżeli <math>A \subseteq B \;\; \text{i} \;\; | A | = | B |</math>, to <math>\; A = B</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
<span style="border-bottom-style: double;">Pierwszy sposób</span><br/><br/>
 
−
Z definicji zbiory <math>A</math> i <math>B</math> są równe wtedy i&nbsp;tylko wtedy, gdy jednocześnie spełnione są warunki
 
−
 
−
:#&nbsp;&nbsp;<math>x \in A \qquad \Longrightarrow \qquad x \in B</math>
 
−
:#&nbsp;&nbsp;<math>x \in B \qquad \Longrightarrow \qquad x \in A</math>
 
−
 
−
Z założenia <math>A \subseteq B</math>, zatem warunek 1. jest spełniony. Przypuśćmy, że istnieje taki element <math>x</math>, że <math>x \in B</math>, ale <math>x \notin A</math>. Jeśli tak, to
 
−
 
−
::<math>| B | = | A | + 1</math>
 
−
 
−
Co jest sprzeczne z&nbsp;założeniem, że <math>| A | = | B |</math>.
 
−
 
−
'''Uwaga'''<br/>
 
−
Łatwo zauważyć, że wybierając z&nbsp;trzech warunków <math>A \subseteq B</math>, <math>B \subseteq A</math> i <math>| A | = | B |</math> dowolne dwa, zawsze otrzymamy z&nbsp;nich trzeci. Oczywiście nie dotyczy to zbiorów nieskończonych. Przykładowo liczby parzyste stanowią podzbiór liczb całkowitych, liczb parzystych jest tyle samo, co liczb całkowitych<ref name="cardinality1"/>, ale zbiór liczb całkowitych nie jest podzbiorem zbioru liczb parzystych.
 
−
 
−
 
−
<span style="border-bottom-style: double;">Drugi sposób</span><br/><br/>
 
−
Ponieważ zbiór <math>A</math> jest z&nbsp;założenia podzbiorem zbioru <math>B</math>, to zbiór <math>B</math> można przedstawić w&nbsp;postaci sumy zbioru <math>A</math> i&nbsp;pewnego zbioru <math>C</math> takiego, że żaden element zbioru <math>C</math> nie jest elementem zbioru <math>A</math>. Zatem
 
−
 
−
::<math>B = A \cup C \qquad \text{i} \qquad A \cap C = \varnothing</math>
 
−
 
−
Ponieważ zbiory <math>A</math> i <math>C</math> są rozłączne, to wiemy, że
 
−
 
−
::<math>| A \cup C | = | A | + | C |</math>
 
−
 
−
Czyli
 
−
 
−
::<math>| B | = | A \cup C | = | A | + | C |</math>
 
−
 
−
Skąd wynika, że <math>| C | = 0</math>, zatem zbiór <math>C</math> jest zbiorem pustym i&nbsp;otrzymujemy natychmiast <math>B = A</math>. Co należało pokazać.
 
−
 
−
'''Uwaga (przypadek zbiorów skończonych)'''<br/>
 
−
Najczęściej prawdziwe jest jedynie oszacowanie <math>| A \cup C | \leqslant | A | + | C |</math>, bo niektóre elementy mogą zostać policzone dwa razy. Elementy liczone dwukrotnie to te, które należą do iloczynu zbiorów <math>| A |</math> i <math>| C |</math>, zatem od sumy <math>| A | + | C |</math> musimy odjąć liczbę elementów iloczynu zbiorów <math>| A |</math> i <math>| C |</math>. Co daje ogólny wzór<ref name="sumazbiorow"/>
 
−
 
−
::<math>| A \cup C | = | A | + | C | - | A \cap C |</math><br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H24" style="font-size: 110%; font-weight: bold;">Definicja H24</span><br/>
 
−
Niech elementy każdego ze zbiorów <math>A = \{ a_1, a_2, \ldots, a_r \}</math> oraz <math>B = \{ b_1, b_2, \ldots, b_r \}</math> będą różne modulo <math>m</math>. Powiemy, że zbiory <math>A, B</math> są równe modulo <math>m</math>, jeżeli dla każdego <math>k = 1, \ldots, r</math> istnieje takie <math>j = 1, \ldots, r</math>, że prawdziwa jest kongruencja <math>a_k \equiv b_j \!\! \pmod{m}</math>.
 
−
 
−
 
−
 
−
<span id="H25" style="font-size: 110%; font-weight: bold;">Twierdzenie H25</span><br/>
 
−
Niech elementy każdego ze zbiorów <math>A = \{ a_1, a_2, \ldots, a_r \}</math> oraz <math>B = \{ b_1, b_2, \ldots, b_r \}</math> będą różne modulo <math>m</math>. Zbiory <math>A, B</math> są równe modulo <math>m</math> wtedy i&nbsp;tylko wtedy, gdy zbiory <math>A' = \{ R_m (a_1), R_m (a_2), \ldots, R_m (a_r) \}</math> i <math>B' = \{ R_m (b_1), R_m (b_2), \ldots, R_m (b_r) \}</math> są równe.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
 
−
<math>\Large{\Longrightarrow}</math>
 
−
 
−
Ponieważ elementy każdego ze zbiorów <math>A, B</math> są różne modulo <math>m</math>, to elementy zbiorów <math>A'</math> i <math>B'</math> są wszystkie różne. Czyli <math>| A' | = | B' | = r</math>. Ponieważ warunek
 
−
 
−
::<math>a_k \equiv b_j \!\! \pmod{m}</math>
 
−
 
−
oznacza, że reszty z&nbsp;dzielenia liczb <math>a_k</math> i <math>b_j</math> przez <math>m</math> są równe, to z&nbsp;założenia dla każdego <math>k = 1, \ldots, r</math> istnieje takie <math>j = 1, \ldots, r</math>, że
 
−
 
−
::<math>R_m (a_k) = R_m (b_j)</math>
 
−
 
−
A to oznacza, że każdy element zbioru <math>A'</math> należy do zbioru <math>B'</math>, czyli <math>A' \subseteq B'</math>. Wynika stąd, że <math>A' = B'</math> (zobacz [[#H23|H23]]). Co należało pokazać.
 
−
 
−
<math>\Large{\Longleftarrow}</math>
 
−
 
−
Ponieważ zbiory <math>A', B'</math> są równe, to zbiór <math>A'</math> jest podzbiorem zbioru <math>B'</math>, czyli dla każdego elementu <math>R_m (a_k) \in A'</math> istnieje taki element <math>R_m (b_j) \in B'</math>, że
 
−
 
−
::<math>R_m (a_k) = R_m (b_j)</math>
 
−
 
−
Ponieważ równość reszt oznacza równość modulo, zatem
 
−
 
−
::<math>a_k \equiv b_j \!\! \pmod{m}</math>
 
−
 
−
Wynika stąd, że dla każdego <math>k = 1, \ldots, r</math> istnieje takie <math>j = 1, \ldots, r</math>, że prawdziwa jest kongruencja
 
−
 
−
::<math>a_k \equiv b_j \!\! \pmod{m}</math>
 
−
 
−
czyli zbiory <math>A, B</math> są równe modulo <math>m</math>. Co kończy dowód.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H26" style="font-size: 110%; font-weight: bold;">Twierdzenie H26</span><br/>
 
−
Niech będą dane zbiory <math>A = \{ 1, 2, \ldots, p - 1 \}</math>, <math>B = \{ b_1, b_2, \ldots, b_{p - 1} \}</math>, gdzie <math>p</math> jest liczbą pierwszą. Jeżeli wszystkie elementy zbioru <math>B</math> są różne modulo <math>p</math> i&nbsp;żadna z&nbsp;liczb <math>b_k \in B</math> nie jest podzielna przez <math>p</math>, to zbiory <math>A, B, C = \{ b^{- 1}_1, b^{- 1}_2, \ldots, b^{- 1}_{p - 1} \}</math> są równe modulo <math>p</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Z definicji zbioru <math>A</math> wszystkie elementy tego zbioru są różne modulo <math>p</math>. Łatwo zauważamy, że
 
−
 
−
::<math>A = \{ 1, 2, \ldots, p - 1 \} = \{ R_p (1), R_p (2), \ldots, R_p (p - 1) \} = A'</math>
 
−
 
−
Ponieważ wszystkie liczby <math>b_k \in B</math>, gdzie <math>k = 1, \ldots, p - 1</math> są różne modulo <math>p</math> i&nbsp;nie są podzielne przez <math>p</math>, to reszty <math>R_p (b_1), R_p (b_2), \ldots, R_p (b_{p - 1})</math> są wszystkie dodatnie i&nbsp;różne, a&nbsp;ponieważ jest ich <math>p - 1</math>, czyli dokładnie tyle, ile jest różnych i&nbsp;dodatnich reszt z&nbsp;dzielenia przez liczbę <math>p</math>, to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z&nbsp;dzielenia przez <math>p</math>, czyli ze zbiorem <math>A</math>. Zatem mamy
 
−
 
−
::<math>A = A' = \{ R_p (b_1), R_p (b_2), \ldots, R_p (b_{p - 1}) \} = B'</math>
 
−
 
−
Na mocy twierdzenia [[#H25|H25]] zbiory <math>A</math> i <math>B</math> są równe modulo <math>p</math>.
 
−
 
−
Z twierdzenia [[#H21|H21]] wiemy, że wszystkie liczby <math>b^{- 1}_k \in C</math> są różne modulo <math>p</math>. Zauważmy, że każda z&nbsp;tych liczb jest względnie pierwsza z <math>p</math>, zatem nie może być podzielna przez <math>p</math>. Wynika stąd, że reszty <math>R_p (b^{- 1}_1), R_p (b^{- 1}_2), \ldots, R_p (b^{- 1}_{p - 1})</math> są wszystkie dodatnie i&nbsp;różne, a&nbsp;ponieważ jest ich <math>p - 1</math>, czyli dokładnie tyle, ile jest różnych i&nbsp;dodatnich reszt z&nbsp;dzielenia przez liczbę <math>p</math>, to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z&nbsp;dzielenia przez <math>p</math>, czyli ze zbiorem <math>A</math>. Zatem mamy
 
−
 
−
::<math>A = A' = \{ R_p (b^{- 1}_1), R_p (b^{- 1}_2), \ldots, R_p (b^{- 1}_{p - 1}) \} = C'</math>
 
−
 
−
Na mocy twierdzenia [[#H25|H25]] zbiory <math>A</math> i <math>C</math> są równe modulo <math>p</math>. Ponieważ <math>A' = B'</math> i <math>A' = C'</math>, to <math>B' = C'</math> i&nbsp;ponownie na mocy twierdzenia [[#H25|H25]] zbiory <math>B</math> i <math>C</math> są równe modulo <math>p</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H27" style="font-size: 110%; font-weight: bold;">Zadanie H27</span><br/>
 
−
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że suma <math>\sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}}</math> jest podzielna przez <math>p</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Zauważmy najpierw, że modulo <math>p</math> następujące sumy są równe
 
−
 
−
::<math>\sum_{k = 1}^{p - 1} k \equiv \sum_{k = 1}^{p - 1} k^{- 1} \!\! \pmod{p}</math>
 
−
 
−
Istotnie, jeśli przyjmiemy w&nbsp;twierdzeniu [[#H26|H26]], że zbiór <math>B = \{ 1, 2, \ldots, p - 1 \}</math>, to zbiór <math>C</math> będzie zbiorem liczb, które są odwrotnościami liczb <math>1, 2, \ldots, p - 1</math> modulo <math>p</math> i&nbsp;możemy napisać
 
−
 
−
::<math>\sum_{x \in B} x \equiv \sum_{y \in C} y \!\! \pmod{p}</math>
 
−
 
−
bo
 
−
 
−
:* gdy <math>x</math> przebiega kolejne wartości <math>b_k</math>, to <math>x</math> przyjmuje kolejno wartości <math>1, 2, \ldots, p - 1</math>
 
−
 
−
:* gdy <math>y</math> przebiega kolejne wartości <math>b_k^{- 1}</math>, to <math>y</math> (modulo <math>p</math>) przyjmuje wszystkie wartości ze zbioru <math>A = \{ 1, 2, \ldots, p - 1 \}</math>, czyli liczba <math>y</math> (modulo <math>p</math>) przyjmuje wszystkie wartości <math>1, 2, \ldots, p - 1</math>, ale w&nbsp;innej kolejności
 
−
 
−
Ponieważ kolejność sumowania tych samych składników nie wpływa na wartość sumy, to prawdziwa jest wyżej wypisana równość sum modulo <math>p</math>.
 
−
 
−
Zatem modulo <math>p</math> otrzymujemy
 
−
 
−
::<math>\sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}} \equiv \sum_{k = 1}^{p - 1} (p - 1)! \cdot k^{- 1}</math>
 
−
 
−
:::::<math>\;\;\: \equiv (p - 1) ! \cdot \sum_{k = 1}^{p - 1} k^{- 1}</math>
 
−
 
−
:::::<math>\;\;\: \equiv (p - 1) ! \cdot \sum_{k = 1}^{p - 1} k</math>
 
−
 
−
:::::<math>\;\;\: \equiv (p - 1) ! \cdot {\small\frac{(p - 1) p}{2}}</math>
 
−
 
−
:::::<math>\;\;\: \equiv (p - 1) ! \cdot {\small\frac{p - 1}{2}} \cdot p</math>
 
−
 
−
:::::<math>\;\;\: \equiv 0 \!\! \pmod{p}</math>
 
−
 
−
Należy zauważyć, że dla liczby pierwszej nieparzystej <math>p</math> liczba <math>{\small\frac{p - 1}{2}}</math> jest liczbą całkowitą.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
 
−
 
−
== Funkcje multiplikatywne ==
 
−
 
−
<span id="H28" style="font-size: 110%; font-weight: bold;">Definicja H28</span><br/>
 
−
Powiemy, że funkcja <math>f(n)</math> określona w&nbsp;zbiorze liczb całkowitych dodatnich jest funkcją multiplikatywną, jeżeli <math>f(1) = 1</math> i&nbsp;dla względnie pierwszych liczb <math>a, b</math> spełniony jest warunek <math>f(a b) = f (a) f (b)</math>.
 
−
 
−
 
−
 
−
<span id="H29" style="font-size: 110%; font-weight: bold;">Uwaga H29</span><br/>
 
−
Założenie <math>f(1) = 1</math> możemy równoważnie zastąpić założeniem, że funkcja <math>f(n)</math> nie jest tożsamościowo równa zero.
 
−
Gdyby <math>f(n)</math> spełniała jedynie warunek <math>f(a b) = f (a) f (b)</math> dla względnie pierwszych liczb <math>a, b</math>, to mielibyśmy
 
−
 
−
::a)&nbsp;&nbsp;&nbsp;<math>f(n)</math> jest tożsamościowo równa zeru wtedy i&nbsp;tylko wtedy, gdy <math>f(1) = 0</math>
 
−
 
−
::b)&nbsp;&nbsp;&nbsp;<math>f(n)</math> nie jest tożsamościowo równa zeru wtedy i&nbsp;tylko wtedy, gdy <math>f(1) = 1</math>
 
−
 
−
Ponieważ <math>f(1) = f (1 \cdot 1) = f (1) f (1)</math>, zatem <math>f(1) = 0</math> lub <math>f (1) = 1</math>.
 
−
 
−
Jeżeli <math>f(1) = 0</math>, to dla dowolnego <math>n</math> mamy
 
−
 
−
::<math>f(n) = f (n \cdot 1) = f (n) f (1) = 0</math>
 
−
 
−
Czyli <math>f(n)</math> jest funkcją tożsamościowo równą zero.
 
−
 
−
Jeżeli <math>f(n)</math> nie jest funkcją tożsamościowo równą zero, to istnieje taka liczba <math>a \in \mathbb{Z}_+</math>, że <math>f(a) \neq 0</math>. Zatem
 
−
 
−
::<math>f(a) = f (a \cdot 1) = f (a) f (1)</math>
 
−
 
−
I dzieląc obie strony przez <math>f(a) \neq 0</math>, dostajemy <math>f(1) = 1</math>.
 
−
 
−
 
−
 
−
<span id="H30" style="font-size: 110%; font-weight: bold;">Przykład H30</span><br/>
 
−
Ponieważ <math>\gcd (1, c) = 1</math>, to <math>\gcd (n, c)</math> rozpatrywana jako funkcja <math>n</math>, gdzie <math>c</math> jest ustaloną liczbą całkowitą, jest funkcją multiplikatywną (zobacz [[#H8|H8]]).
 
−
 
−
 
−
 
−
<span id="H31" style="font-size: 110%; font-weight: bold;">Twierdzenie H31</span><br/>
 
−
Jeżeli funkcja <math>f(n)</math> jest funkcją multiplikatywną, to funkcja
 
−
 
−
::<math>F(n) = \sum_{d \mid n} f (d)</math>
 
−
 
−
gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby <math>n</math>, jest również funkcją multiplikatywną.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Ponieważ
 
−
 
−
::<math>F(1) = \sum_{d \mid 1} f (d) = f (1) = 1</math>
 
−
 
−
to funkcja <math>F(n)</math> spełnia pierwszy warunek definicji [[#H28|H28]].
 
−
 
−
Niech <math>a, b</math> będą względnie pierwszymi liczbami dodatnimi. Każdy dzielnik dodatni iloczynu <math>a b</math> można zapisać w&nbsp;postaci <math>d = d_1 d_2</math>, gdzie <math>d_1 \mid a</math>, <math>\; d_2 \mid b \,</math> oraz <math>\, \gcd (d_1, d_2) = 1</math> (zobacz [[#H14|H14]]). Niech zbiory
 
−
 
−
::<math>S_a = \{ d \in \mathbb{Z}_+ : d \mid a \}</math>
 
−
 
−
::<math>S_b = \{ d \in \mathbb{Z}_+ : d \mid b \}</math>
 
−
 
−
::<math>S_{a b} = \{ d \in \mathbb{Z}_+ : d \mid a b \}</math>
 
−
 
−
będą zbiorami dzielników dodatnich liczb <math>a, b</math> i <math>a b</math>. Dla przykładu
 
−
 
−
::<math>S_5 = \{ 1, 5 \}</math>
 
−
 
−
::<math>S_7 = \{ 1, 7 \}</math>
 
−
 
−
::<math>S_{35} = \{ 1, 5, 7, 35 \}</math>
 
−
 
−
Dla dowolnego <math>d_1 \in S_a \,</math> i <math>\, d_2 \in S_b</math> musi być <math>\gcd (d_1, d_2) = 1</math>, bo gdyby było <math>\gcd (d_1, d_2) = g > 1</math>, to
 
−
 
−
::<math>g \mid d_1 \quad \; \text{i} \quad \; d_1 \mid a \qquad \quad \Longrightarrow \qquad \quad g \mid a</math>
 
−
 
−
::<math>g \mid d_2 \quad \; \text{i} \quad \; d_2 \mid b \qquad \quad \Longrightarrow \qquad \quad g \mid b</math>
 
−
 
−
Zatem <math>g \mid \gcd (a, b)</math> i&nbsp;mielibyśmy <math>\gcd (a, b) \geqslant g > 1</math>, wbrew założeniu.
 
−
 
−
Przekształcając, otrzymujemy
 
−
 
−
::<math>F(a b) = \sum_{d \mid a b} f (d)</math>
 
−
 
−
:::<math>\;\;\;\;\: = \sum_{d \in S_{a b}} f (d)</math>
 
−
 
−
:::<math>\;\;\;\;\: = \underset{d_2 \in S_{b}}{\sum_{d_1 \in S_{a}}} f (d_1 d_2)</math>
 
−
 
−
:::<math>\;\;\;\;\: = \underset{d_2 \in S_{b}}{\sum_{d_1 \in S_{a}}} f (d_1) f (d_2)</math>
 
−
 
−
:::<math>\;\;\;\;\: = \sum_{d_1 \in S_{a}} f (d_1) \sum_{d_2 \in S_{b}} f (d_2)</math>
 
−
 
−
:::<math>\;\;\;\;\: = \sum_{d_1 \mid a} f (d_1) \sum_{d_2 \mid b} f (d_2)</math>
 
−
 
−
:::<math>\;\;\;\;\: = F (a) F (b)</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
 
−
 
−
== Funkcja Eulera <math>\varphi (n)</math> ==
 
−
 
−
<span id="H32" style="font-size: 110%; font-weight: bold;">Definicja H32</span><br/>
 
−
Funkcja Eulera <math>\varphi (n)</math><ref name="Euler1"/> jest równa ilości liczb całkowitych dodatnich nie większych od <math>n</math> i&nbsp;względnie pierwszych z <math>n</math>.
 
−
 
−
 
−
 
−
<span id="H33" style="font-size: 110%; font-weight: bold;">Twierdzenie H33</span><br/>
 
−
Funkcja Eulera <math>\varphi (n)</math> jest multiplikatywna, czyli dla względnie pierwszych liczb <math>m, n</math> jest <math>\varphi (m n) = \varphi (m) \varphi (n)</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Niech <math>m, n</math> będą dodatnimi liczbami całkowitymi takimi, że <math>\gcd (m, n) = 1</math>. Twierdzenie jest prawdziwe dla <math>n = 1</math>, zatem nie zmniejszając ogólności, możemy założyć, że <math>n > 1</math>. Wypiszmy w&nbsp;tabeli wszystkie liczby od <math>1</math> do <math>m n</math>.
 
−
 
−
::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
 
−
|-
 
−
| <math>1</math> || <math>2</math> || <math>…</math> || <math>k</math> || <math>…</math> || <math>m</math>
 
−
|-
 
−
| <math>m + 1</math> || <math>m + 2</math> || <math>…</math> || <math>m + k</math> || <math>…</math> || <math>2 m</math>
 
−
|-
 
−
| <math>2 m + 1</math> || <math>2 m + 2</math> || <math>…</math> || <math>2 m + k</math> || <math>…</math> || <math>3 m</math>
 
−
|-
 
−
| <math>…</math> || <math>…</math> || <math>…</math> || <math>…</math> || <math></math> || <math></math>
 
−
|-
 
−
| <math>(n - 1) m + 1</math> || <math>(n - 1) m + 2</math> || <math>…</math> || <math>(n - 1) m + k</math> || <math>…</math> || <math>n m</math>
 
−
|}
 
−
 
−
'''1.''' Natychmiast widzimy, że w&nbsp;pierwszym wierszu mamy <math>\varphi (m)</math> liczb względnie pierwszych z <math>m</math>. Tak samo jest w&nbsp;każdym kolejnym wierszu, bo (zobacz [[#H5|H5]])
 
−
 
−
::<math>\gcd (r m + k, m) = \gcd (k, m)</math>
 
−
 
−
Zatem mamy dokładnie <math>\varphi (m)</math> kolumn liczb względnie pierwszych z <math>m</math>.
 
−
 
−
 
−
'''2.''' Załóżmy, że liczba <math>k</math> jest jedną z&nbsp;liczb względnie pierwszych z <math>m</math>, czyli <math>\gcd (k, m) = 1</math>. Przy tym założeniu <math>k</math>-ta kolumna (pokazana w&nbsp;tabeli) jest kolumną liczb względnie pierwszych z <math>m</math>.
 
−
 
−
 
−
'''3.''' Zauważmy, że reszty z&nbsp;dzielenia liczb wypisanych w <math>k</math>-tej kolumnie przez <math>n</math> są wszystkie różne. Gdyby tak nie było, to dla pewnych <math>i, j</math>, gdzie <math>0 \leqslant i, j \leqslant n - 1</math>, różnica liczb <math>i m + k</math> oraz <math>j m + k</math> byłaby podzielna przez <math>n</math>. Mielibyśmy
 
−
 
−
::<math>n \mid ((i m + k) - (j m + k))</math>
 
−
 
−
Skąd wynika natychmiast
 
−
 
−
::<math>n \mid (i - j) m</math>
 
−
 
−
Ponieważ założyliśmy, że <math>\gcd (n, m) = 1</math>, to musi być <math>n \mid (i - j)</math> (zobacz C74), ale
 
−
 
−
::<math>0 \leqslant | i - j | \leqslant n - 1</math>
 
−
 
−
Czyli <math>n</math> może dzielić <math>i - j</math> tylko w&nbsp;przypadku, gdy <math>i = j</math>. Wbrew naszemu przypuszczeniu, że istnieją różne liczby dające takie same reszty przy dzieleniu przez <math>n</math>.
 
−
 
−
 
−
'''4.''' Ponieważ w <math>k</math>-tej kolumnie znajduje się dokładnie <math>n</math> liczb i&nbsp;reszty z&nbsp;dzielenia tych liczb przez <math>n</math> są wszystkie różne, to reszty te tworzą zbiór <math>S = \{ 0, 1, \ldots, n - 1 \}</math>. Wynika stąd, że liczby wypisane w <math>k</math>-tej kolumnie mogą być zapisane w&nbsp;postaci
 
−
 
−
::<math>a_r = b_r \cdot n + r</math>
 
−
 
−
gdzie <math>r = 0, 1, \ldots, n - 1</math> i <math>b_r \in \mathbb{Z}</math>.
 
−
 
−
Zauważmy, że następujące ilości liczb są sobie równe
 
−
 
−
:*&nbsp;&nbsp;&nbsp;ilość liczb w <math>k</math>-tej kolumnie względnie pierwszych z <math>n</math>
 
−
 
−
:*&nbsp;&nbsp;&nbsp;ilość liczb <math>r</math> względnie pierwszych z <math>n</math>, gdzie <math>r = 0, \ldots, n - 1</math>, bo <math>\gcd (b_r \cdot n + r, n) = \gcd (r, n)</math>
 
−
 
−
:*&nbsp;&nbsp;&nbsp;ilość liczb <math>r</math> względnie pierwszych z <math>n</math>, gdzie <math>r = 1, \ldots, n</math>, bo <math>\gcd (n, n) = \gcd (0, n) = | n | > 1</math>
 
−
 
−
Ostatnia ilość liczb jest równa <math>\varphi (n)</math>, co wynika wprost z&nbsp;definicji funkcji <math>\varphi (n)</math>.
 
−
 
−
 
−
'''5.''' Zbierając: mamy w&nbsp;wypisanej tabeli dokładnie <math>\varphi (m) \varphi (n)</math> liczb <math>u \in [1, m n]</math>, dla których jednocześnie jest
 
−
 
−
::<math>\gcd (u, m) = 1 \quad  \text{i} \quad \gcd (u, n) = 1</math>
 
−
 
−
Z twierdzenia [[#H6|H6]] wynika, że w&nbsp;tabeli jest dokładnie <math>\varphi (m) \varphi (n)</math> liczb <math>u \in [1, m n]</math>, dla których jest
 
−
 
−
::<math>\gcd (u, m n) = 1</math>
 
−
 
−
Zatem <math>\varphi (m n) = \varphi (m) \varphi (n)</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H34" style="font-size: 110%; font-weight: bold;">Twierdzenie H34</span><br/>
 
−
Dla dowolnej liczby całkowitej dodatniej <math>n</math> jest
 
−
 
−
::<math>\varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right)</math>
 
−
 
−
gdzie iloczyn obliczamy po wszystkich liczbach pierwszych <math>p</math>, będących dzielnikami liczby <math>n</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Ponieważ wszystkie liczby naturalne mniejsze od liczby pierwszej <math>p</math> są jednocześnie pierwsze względem <math>p</math>, to <math>\varphi (p) = p - 1</math>.
 
−
 
−
Równie łatwo znajdujemy wartość funkcji <math>\varphi (n)</math> w&nbsp;przypadku gdy <math>n</math> jest potęgą liczby pierwszej <math>n = p^k</math>. Wystarczy zauważyć, że w&nbsp;ciągu kolejnych liczb
 
−
 
−
::<math>1, 2, 3, 4, \ldots, p^k - 1, p^k</math>
 
−
 
−
jedynymi liczbami, które nie są pierwsze względem <math>p^k</math>, są te, które dzielą się przez <math>p</math> i&nbsp;jest ich <math>p^{k - 1}</math>, co widać natychmiast po ich bezpośrednim wypisaniu
 
−
 
−
::<math>1 \cdot p, 2 \cdot p, 3 \cdot p, \ldots, (p^{k - 1} - 1) \cdot p, p^{k - 1} \cdot p</math>
 
−
 
−
Zatem
 
−
 
−
::<math>\varphi (p^k) = p^k - p^{k - 1} = p^k \left( 1 - {\small\frac{1}{p}} \right)</math>
 
−
 
−
Ponieważ <math>\varphi (n)</math> jest funkcją multiplikatywną, to dla <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math> otrzymujemy
 
−
 
−
::<math>\varphi (n) = \prod^s_{k = 1} \varphi (p^{\alpha_k}_k)</math>
 
−
 
−
:::<math>\;\;\; = \prod^s_{k = 1} p^{\alpha_k}_k \left( 1 - {\small\frac{1}{p_k}} \right)</math>
 
−
 
−
:::<math>\;\;\; = \left[ \prod^s_{k = 1} p^{\alpha_k}_k \right] \cdot \left[ \prod^s_{k = 1} \left( 1 - {\small\frac{1}{p_k}} \right) \right]</math>
 
−
 
−
:::<math>\;\;\; = n \cdot \prod^s_{k = 1} \left( 1 - {\small\frac{1}{p_k}} \right)</math>
 
−
 
−
:::<math>\;\;\; = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right)</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H35" style="font-size: 110%; font-weight: bold;">Twierdzenie H35</span><br/>
 
−
Niech <math>n \in \mathbb{Z}_+</math>. Jeżeli <math>q</math> jest liczbą pierwszą, to
 
−
 
−
::<math>\varphi (q n) = \left\{ \begin{array}{rl}
 
−
  (q - 1) \varphi (n) & \quad \text{gdy} \quad q \nmid n \\
 
−
  q \varphi (n) & \quad \text{gdy} \quad q \mid n \\
 
−
\end{array} \right.</math>
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Jeżeli <math>q \nmid m</math>, to <math>\gcd (q, m) = 1</math>, zatem <math>\varphi (q m) = \varphi (q) \varphi (m) = (q - 1) \varphi (m)</math>. Jeżeli <math>q \mid m</math>, to liczby <math>m</math> oraz <math>q m</math> mają taki sam zbiór dzielników pierwszych, zatem
 
−
 
−
::<math>\varphi (q m) = q m \prod_{p \mid q m} \left( 1 - {\small\frac{1}{p}} \right) = q \cdot \left[ m \prod_{p \mid m} \left( 1 - {\small\frac{1}{p}} \right) \right] = q \varphi (m)</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H36" style="font-size: 110%; font-weight: bold;">Zadanie H36</span><br/>
 
−
Niech <math>q \in \mathbb{P}</math> i <math>a, b, m, n \in \mathbb{Z}_+</math>. Pokazać, że
 
−
 
−
:*&nbsp;&nbsp;&nbsp;<math>\varphi (q^{a + b}) = q^a \varphi (q^b)</math>
 
−
 
−
:*&nbsp;&nbsp;&nbsp;<math>\varphi (n^m) = n^{m - 1} \varphi (n)</math>
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
'''Punkt 1.'''
 
−
 
−
::<math>\varphi (q^{a + b}) = (q - 1) q^{a + b - 1} = q^a \cdot (q - 1) q^{b - 1} = q^a \varphi (q^b)</math>
 
−
 
−
'''Punkt 2.'''
 
−
 
−
Niech <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>
 
−
 
−
::<math>\varphi (n^m) = \varphi (p^{m \alpha_1}_1 \cdot \ldots \cdot p^{m \alpha_s}_s)</math>
 
−
 
−
::::<math>\, = \varphi (p^{m \alpha_1}_1) \cdot \ldots \cdot \varphi (p^{m \alpha_s}_s)</math>
 
−
 
−
::::<math>\, = \varphi (p^{(m - 1) \alpha_1 + \alpha_1}_1) \cdot \ldots \cdot \varphi (p^{(m - 1) \alpha_s + \alpha_s}_s)</math>
 
−
 
−
::::<math>\, = p^{(m - 1) \alpha_1}_1 \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot p^{(m - 1) \alpha_s}_s \varphi (p^{\alpha_s}_s)</math>
 
−
 
−
::::<math>\, = p^{(m - 1) \alpha_1}_1 \cdot \ldots \cdot p^{(m - 1) \alpha_s}_s \cdot \varphi (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s)</math>
 
−
 
−
::::<math>\, = n^{m - 1} \varphi (n)</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H37" style="font-size: 110%; font-weight: bold;">Twierdzenie H37</span><br/>
 
−
Niech <math>m, n \in \mathbb{Z}_+</math>. Jeżeli <math>m \mid n</math>, to <math>\varphi (m) \mid \varphi (n)</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Niech <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>. Ponieważ założyliśmy, że <math>m \mid n</math>, to <math>m</math> musi być postaci <math>m = p^{\beta_1}_1 \cdot \ldots \cdot p^{\beta_s}_s</math>, gdzie <math>0 \leqslant \beta_i \leqslant \alpha_i</math>, dla <math>i = 1, \ldots, s</math>. Łatwo zauważamy, że
 
−
 
−
:*&nbsp;&nbsp;&nbsp;jeżeli <math>\beta_i = 0</math>, to <math>\varphi (p^{\beta_i}_i) = 1</math> i&nbsp;dzieli <math>\varphi (p^{\alpha_i}_i)</math>
 
−
 
−
:*&nbsp;&nbsp;&nbsp;jeżeli <math>1 \leqslant \beta_i \leqslant \alpha_i</math>, to <math>(p_i - 1) p_i^{\beta_i - 1} \mid (p_i - 1) p_i^{\alpha_i - 1}</math>, zatem <math>\varphi (p^{\beta_i}_i) \mid \varphi (p^{\alpha_i}_i)</math>
 
−
 
−
Skąd natychmiast wynika, że <math>\varphi (p^{\beta_1}_1) \cdot \ldots \cdot \varphi (p^{\beta_s}_s)</math> dzieli <math>\varphi (p^{\alpha_1}_1) \cdot \ldots \cdot \varphi (p^{\alpha_s}_s)</math>, czyli <math>\varphi (m) \mid \varphi (n)</math>.
 
−
 
−
Zauważmy, że twierdzenie odwrotne nie jest prawdziwe, bo <math>\varphi (7) \mid \varphi (19)</math>, ale <math>7 \nmid 19</math>.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H38" style="font-size: 110%; font-weight: bold;">Zadanie H38</span><br/>
 
−
Dla <math>n \geqslant 3</math> wartości <math>\varphi (n)</math> są liczbami parzystymi.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Jeżeli liczba <math>n \geqslant 3</math> jest podzielna przez liczbę pierwszą nieparzystą <math>p</math>, zaś <math>k</math> jest wykładnikiem, z&nbsp;jakim <math>p</math> wchodzi do rozwinięcia <math>n</math> na czynniki pierwsze, to
 
−
 
−
::<math>\varphi (n) = \varphi \left( p^k \cdot {\small\frac{n}{p^k}} \right) = (p - 1) p^{k  - 1} \cdot \varphi \left( {\small\frac{n}{p^k}} \right)</math>
 
−
 
−
zatem <math>\varphi (n)</math> jest liczbą parzystą, ponieważ <math>p - 1</math> jest liczbą parzystą.
 
−
 
−
Jeżeli żadna liczba nieparzysta nie dzieli <math>n</math>, to liczba <math>n</math> jest postaci <math>n = 2^a</math> i <math>\varphi (n) = 2^{a - 1}</math>, ale z&nbsp;założenia <math>n \geqslant 3</math>, zatem <math>a \geqslant 2</math> i <math>\varphi (n)</math> jest liczbą parzystą.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H39" style="font-size: 110%; font-weight: bold;">Twierdzenie H39</span><br/>
 
−
Jeżeli <math>n</math> jest liczbą złożoną, to <math>\varphi (n) \leqslant n - \sqrt{n}</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
<span style="border-bottom-style: double;">Pierwszy sposób</span><br/>
 
−
Niech <math>n = a b</math>, gdzie <math>1 < a \leqslant b < n</math>. Liczby <math>1 \cdot a, 2 \cdot a, 3 \cdot a, \ldots, b \cdot a</math> są nie większe od <math>n</math> i&nbsp;nie są względnie pierwsze z <math>n</math>, zatem
 
−
 
−
::<math>\varphi (n) \leqslant n - b</math>
 
−
 
−
Ponieważ <math>b \geqslant a</math>, to <math>b^2 \geqslant a b = n</math> i <math>b \geqslant \sqrt{n}</math>. Wynika stąd, że
 
−
 
−
::<math>\varphi (n) \leqslant n - b \leqslant n - \sqrt{n}</math>
 
−
 
−
<br/><span style="border-bottom-style: double;">Drugi sposób</span><br/>
 
−
Niech <math>q</math> oznacza najmniejszy dzielnik pierwszy liczby złożonej <math>n</math>, zatem <math>q^2 \leqslant n</math>, czyli <math>q \leqslant \sqrt{n}</math>, a&nbsp;stąd <math>{\small\frac{n}{q}} \geqslant \sqrt{n}</math> i
 
−
 
−
::<math>\varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right) \leqslant n \left( 1 - {\small\frac{1}{q}} \right) = n - {\small\frac{n}{q}} \leqslant n - \sqrt{n}</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H40" style="font-size: 110%; font-weight: bold;">Twierdzenie H40</span><br/>
 
−
Dla <math>n \geqslant 1</math> prawdziwe jest oszacowanie <math>\varphi (n) > {\small\frac{\sqrt{n}}{2}}</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Dla <math>k \geqslant 3</math> jest
 
−
 
−
::<math>\left( 1 - {\small\frac{1}{k}} \right)^2 > {\small\frac{1}{k}}</math>
 
−
 
−
Wynika stąd, że jeżeli <math>m \geqslant 3</math> jest liczbą nieparzystą, to
 
−
 
−
::<math>\varphi (m)^2 = m^2 \prod_{p|m} \left( 1 - {\small\frac{1}{p}} \right)^2 > m^2 \prod_{p|m} {\small\frac{1}{p}} \geqslant m</math>
 
−
 
−
bo
 
−
 
−
::<math>\prod_{p|m} p \leqslant m</math>
 
−
 
−
Czyli dla nieparzystych liczb <math>m \geqslant 3</math> mamy
 
−
 
−
::<math>\varphi (m) > \sqrt{m} > {\small\frac{\sqrt{m}}{2}}</math>
 
−
 
−
 
−
Jeżeli <math>d = 2^a</math>, gdzie <math>a \geqslant 1</math>, to
 
−
 
−
::<math>\varphi (d) = \varphi (2^a) = 2^{a - 1} > {\small\frac{\sqrt{2^a}}{2}} = {\small\frac{\sqrt{d}}{2}}</math>
 
−
 
−
 
−
W przypadku ogólnym, gdy <math>n</math> jest iloczynem liczby nieparzystej <math>m \geqslant 3</math> i&nbsp;potęgi liczby <math>2</math>, dostajemy
 
−
 
−
::<math>\varphi (n) = \varphi (2^a m) = \varphi (2^a) \varphi (m) > {\small\frac{\sqrt{2^a}}{2}} \cdot \sqrt{m} = {\small\frac{\sqrt{2^a m}}{2}} = {\small\frac{\sqrt{n}}{2}}</math>
 
−
 
−
Oczywiście nierówność <math>\varphi (n) > {\small\frac{\sqrt{n}}{2}}</math> jest również prawdziwa dla <math>n = 1</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H41" style="font-size: 110%; font-weight: bold;">Zadanie H41</span><br/>
 
−
Pokazać, że dla <math>n \geqslant 7</math> prawdziwe jest oszacowanie <math>\varphi (n) > \sqrt{n}</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Zauważmy, że
 
−
 
−
::<math>n - 1 > \sqrt{n} \qquad \qquad \;\, \text{dla} \; n \geqslant 3</math>
 
−
 
−
::<math>n - 1 > \sqrt{2 n} \qquad \qquad \text{dla} \; n \geqslant 4</math>
 
−
 
−
 
−
Zatem dla liczby pierwszej <math>p</math> i <math>k \geqslant 1</math> jest
 
−
 
−
::<math>\varphi (p^k) = (p - 1) p^{k - 1} > \sqrt{p} \cdot p^{k - 1} = p^{k - \tfrac{1}{2}} \geqslant p^{\tfrac{k}{2}} = \sqrt{p^k} \qquad \qquad \qquad \qquad \quad \; \text{dla} \;\: p \geqslant 3</math>
 
−
 
−
::<math>\varphi (p^k) = (p - 1) p^{k - 1} > \sqrt{2 p} \cdot p^{k - 1} = \sqrt{2} \cdot p^{k - \tfrac{1}{2}} \geqslant \sqrt{2} \cdot p^{\tfrac{k}{2}} = \sqrt{2 p^k} \qquad \qquad \text{dla} \;\, p \geqslant 5</math>
 
−
 
−
 
−
'''1. Przypadek, gdy <math>\boldsymbol{n \geqslant 3}</math> jest liczbą nieparzystą'''
 
−
 
−
Liczba <math>n</math> jest iloczynem czynników pierwszych nieparzystych, zatem
 
−
 
−
::<math>\varphi (n) = \varphi (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) = \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot \varphi (p^{\alpha_s}_s) > \sqrt{p^{\alpha_1}_1} \cdot \ldots \cdot \sqrt{p^{\alpha_s}_s} = \sqrt{n}</math>
 
−
 
−
 
−
'''2. Przypadek, gdy <math>\boldsymbol{n = 2^a m} \;</math> i <math>\; \boldsymbol{q \mid m ,} \;</math> gdzie <math>\; \boldsymbol{q \geqslant 5}</math>'''
 
−
 
−
Z założenia <math>n = 2^a m = 2^a q^b r</math>, gdzie <math>r \geqslant 1</math> jest liczbą nieparzystą. Zauważmy, że <math>\varphi (r) \geqslant \sqrt{r}</math>, bo może być <math>r = 1</math>.
 
−
 
−
::<math>\varphi (n) = \varphi (2^a q^b r)</math>
 
−
 
−
:::<math>\;\;\,\, = \varphi (2^a) \varphi (q^b) \varphi (r)</math>
 
−
 
−
:::<math>\;\;\,\, > 2^{a - 1} \sqrt{2 q^b} \sqrt{r}</math>
 
−
 
−
:::<math>\;\;\,\, = 2^{a - \tfrac{1}{2}} \sqrt{q^b} \sqrt{r}</math>
 
−
 
−
:::<math>\;\;\,\, \geqslant 2^{\tfrac{a}{2}} \sqrt{q^b r}</math>
 
−
 
−
:::<math>\;\;\,\, = \sqrt{2^a q^b r}</math>
 
−
 
−
:::<math>\;\;\,\, = \sqrt{n}</math>
 
−
 
−
 
−
'''3. Przypadek, gdy <math>\boldsymbol{n = 2^a m} \;</math> i <math>\; \boldsymbol{q \nmid m ,} \;</math> gdzie <math>\; \boldsymbol{q \geqslant 5}</math>'''
 
−
 
−
Jeżeli żadna liczba pierwsza <math>q \geqslant 5</math> nie dzieli <math>m</math>, to możliwe są tylko dwie sytuacje: <math>n = 2^a \,</math> i <math>\, n = 2^a 3^b</math>.
 
−
 
−
'''3a. Przypadek, gdy <math>\boldsymbol{n = 2^a}</math>'''
 
−
 
−
::<math>\varphi (n) = \varphi (2^a) = 2^{a - 1} > \sqrt{2^a} = \sqrt{n} \qquad \qquad \;\, \text{dla} \; a \geqslant 3</math>
 
−
 
−
Twierdzenie nie jest prawdziwe dla <math>n = 2 \,</math> i <math>\, n = 4 \,\,</math> (gdy <math>a = 1 \,</math> lub <math>\, a = 2</math>).
 
−
 
−
'''3b. Przypadek, gdy <math>\boldsymbol{n = 2^a 3^b}</math>'''
 
−
 
−
::<math>\varphi (n) = \varphi (2^a 3^b) = \varphi (2^a) \varphi (3^b) = 2^{a - 1} \cdot 2 \cdot 3^{b - 1} = 2^a 3^{b - 1} = \sqrt{2^a 3^b} \cdot {\small\frac{\sqrt{2^a 3^b}}{3}} > \sqrt{2^a 3^b}</math>
 
−
 
−
Ostatnia nierówność jest prawdziwa, o&nbsp;ile <math>\sqrt{2^a 3^b} > 3</math>, czyli gdy <math>2^a 3^b > 9</math>, co ma miejsce, gdy <math>a \geqslant 2</math> lub <math>b \geqslant 2</math>.
 
−
 
−
Twierdzenie nie jest prawdziwe dla <math>n = 6 \;</math> (gdy <math>a = 1 \,</math> i <math>\, b = 1</math>).
 
−
 
−
 
−
Zbierając uzyskane wyniki, otrzymujemy: oszacowanie <math>\varphi (n) > \sqrt{n}</math> nie jest prawdziwe dla <math>n = 1, 2, 4, 6</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H42" style="font-size: 110%; font-weight: bold;">Zadanie H42</span><br/>
 
−
Pokazać, że dla <math>n \geqslant 2</math> prawdziwe jest oszacowanie <math>\varphi (n) > {\small\frac{n}{3 \log n}}</math>. Korzystając z&nbsp;tego wyniku, pokazać, że <math>\varphi (n) > n^{2 / 3}</math> dla <math>n \geqslant 43</math> oraz że <math>\varphi (n) > n^{3 / 4}</math> dla <math>n \geqslant 211</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Niech <math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>, a <math>n' = q_1 \cdot \ldots \cdot q_s</math> oznacza liczbę, będącą iloczynem dokładnie '''tych samych''' czynników pierwszych, jakie występują w&nbsp;liczbie <math>n</math>, natomiast <math>n^{\!\ast} = p_1 \cdot \ldots \cdot p_s</math> oznacza liczbę, będącą iloczynem dokładnie '''tej samej ilości''' czynników pierwszych, przy czym <math>p_i</math> oznacza teraz <math>i</math>-tą liczbę pierwszą.
 
−
 
−
Ponieważ
 
−
 
−
::<math>{\small\frac{\varphi (n)}{n}} = \prod_{p \mid n} \left( 1 - {\small\frac{1}{p}} \right)</math>
 
−
 
−
to
 
−
 
−
::<math>{\small\frac{\varphi (n)}{n}} = {\small\frac{\varphi (n')}{n'}} \geqslant {\small\frac{\varphi (n^{\!\ast})}{n^{\!\ast}}} = \prod^s_{i = 1} \left( 1 - {\small\frac{1}{p_i}} \right) \geqslant \prod^{p_s}_{k = 2} \left( 1 - {\small\frac{1}{k}} \right) = {\small\frac{1}{p_s}}</math>
 
−
 
−
Ostatnia równość wynika z&nbsp;prostego wzoru
 
−
 
−
::<math>\prod^m_{k = 2} \left( 1 - {\small\frac{1}{k}} \right) = {\small\frac{1}{2}} \cdot {\small\frac{2}{3}} \cdot {\small\frac{3}{4}} \cdot \ldots \cdot {\small\frac{m - 2}{m - 1}} \cdot {\small\frac{m - 1}{m}} = {\small\frac{1}{m}}</math>
 
−
 
−
 
−
Musimy oszacować wartość liczby <math>p_s</math>. Z&nbsp;twierdzenia B31 wynika, że dla <math>m \geqslant 2</math> jest <math>P(m) \geqslant 2^{m / 2}</math>, gdzie funkcja <math>P(m)</math> jest równa iloczynowi wszystkich liczb pierwszych nie większych od <math>m</math>. Zatem dla <math>p_s \geqslant 2</math> jest
 
−
 
−
::<math>n^{\!\ast} = p_1 \cdot \ldots \cdot p_s = P (p_s) \geqslant 2^{p_s / 2}</math>
 
−
 
−
Logarytmując, otrzymujemy
 
−
 
−
::<math>p_s \leqslant {\small\frac{2 \log n^{\!\ast}}{\log 2}}</math>
 
−
 
−
Ponieważ <math>n \geqslant n' \geqslant n^{\!\ast}</math>, to
 
−
 
−
::<math>{\small\frac{\varphi (n)}{n}} \geqslant {\small\frac{1}{p_s}} \geqslant {\small\frac{\log 2}{2 \log n^{\!\ast}}} \geqslant {\small\frac{\log 2}{2 \log n}} > {\small\frac{1}{3 \log n}}</math>
 
−
 
−
Ostatecznie otrzymujemy
 
−
 
−
::<math>\varphi (n) > {\small\frac{n}{3 \log n}}</math>
 
−
 
−
Co należało pokazać.
 
−
 
−
 
−
Rozwiązując drugą część zadania, wystarczy znaleźć, dla jakich <math>n</math> prawdziwa jest nierówność
 
−
 
−
::<math>{\small\frac{n}{3 \log n}} > n^{2 / 3}</math>
 
−
 
−
Przebieg funkcji <math>{\small\frac{n}{3 \log n}} \,</math> i <math>\, n^{2 / 3}</math> przedstawiliśmy na wykresie
 
−
 
−
::[[File: Euler1.png|1100px|none]]
 
−
 
−
Punkt przecięcia tych funkcji znajdujemy, wpisując w&nbsp;PARI/GP polecenie
 
−
 
−
<span style="font-size: 90%; color:black;">'''solve'''(n = 10, 10^5, n/(3*'''log'''(n)) - n^(2/3))</span>
 
−
 
−
Otrzymujemy
 
−
 
−
::<math>n = 29409.965</math>
 
−
 
−
Zatem <math>{\small\frac{n}{3 \log n}} > n^{2 / 3}</math> dla <math>n > 2.95 \cdot 10^4</math>.
 
−
 
−
Poleceniem
 
−
 
−
<span style="font-size: 90%; color:black;">'''for'''(n = 1, 3*10^4, '''if'''( '''eulerphi'''(n) <= n^(2/3), '''print'''(n) ))</span>
 
−
 
−
sprawdzamy, że oszacowanie <math>\varphi (n) > n^{2 / 3}</math> jest prawdziwe dla <math>n \geqslant 43</math>.
 
−
 
−
 
−
Postępując analogicznie jak wyżej, znajdujemy, dla jakich <math>n</math> prawdziwa jest nierówność
 
−
 
−
::<math>{\small\frac{n}{3 \log n}} > n^{3 / 4}</math>
 
−
 
−
Wpisując w&nbsp;PARI/GP polecenie
 
−
 
−
<span style="font-size: 90%; color:black;">'''solve'''(n = 10, 10^7, n/(3*'''log'''(n)) - n^(3/4))</span>
 
−
 
−
otrzymujemy
 
−
 
−
::<math>n = 4447862.680</math>
 
−
 
−
Zatem <math>{\small\frac{n}{3 \log n}} > n^{3 / 4}</math> dla <math>n > 4.45 \cdot 10^6</math>
 
−
 
−
Poleceniem
 
−
 
−
<span style="font-size: 90%; color:black;">'''for'''(n = 1, 5*10^6, '''if'''( '''eulerphi'''(n) <= n^(3/4), '''print'''(n) ))</span>
 
−
 
−
sprawdzamy, że oszacowanie <math>\varphi (n) > n^{3 / 4}</math> jest prawdziwe dla <math>n \geqslant 211</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H43" style="font-size: 110%; font-weight: bold;">Twierdzenie H43</span><br/>
 
−
Niech <math>n \in \mathbb{Z}_+</math>. Liczba <math>n</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy <math>\varphi (n) = n - 1</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Dla liczb złożonych <math>n \geqslant 4</math> nigdy nie będzie <math>\varphi (n) = n - 1</math>, bo
 
−
 
−
::<math>\varphi (n) \leqslant n - \sqrt{n} \leqslant n - 2</math>
 
−
 
−
Dla <math>n = 1, 2, 3</math> sprawdzamy bezpośrednio: <math>\varphi (1) = 1 \neq 1 - 1</math>, <math>\varphi (2) = 1 = 2 - 1</math>, <math>\varphi (3) = 2 = 3 - 1</math>. Co kończy dowód.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H44" style="font-size: 110%; font-weight: bold;">Twierdzenie H44</span><br/>
 
−
Dla dowolnej liczby całkowitej dodatniej <math>n</math> jest
 
−
 
−
::<math>n = \sum_{d \mid n} \varphi (d) = \sum_{d \mid n} \varphi \left( {\small\frac{n}{d}} \right)</math>
 
−
 
−
gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby <math>n</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
 
−
Ponieważ <math>\varphi (n)</math> jest funkcją multiplikatywną, to funkcja
 
−
 
−
::<math>F(n) = \sum_{d \mid n} \varphi (d)</math>
 
−
 
−
też jest funkcją multiplikatywną (zobacz [[#H31|H31]]). Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla <math>n = 1</math>. Niech <math>n > 1</math>. Jeżeli <math>n =
 
−
p^{\alpha}</math> jest potęgą liczby pierwszej, to otrzymujemy
 
−
 
−
::<math>F (p^{\alpha}) = \sum_{d \mid p^{\alpha}} \varphi (d)</math>
 
−
 
−
::::<math>= \varphi (1) + \varphi (p) + \varphi (p^2) + \ldots + \varphi (p^{\alpha}) =</math>
 
−
 
−
::::<math>= 1 + (p - 1) + p (p - 1) + \ldots + p^{\alpha - 1} (p - 1) =</math>
 
−
 
−
::::<math>= 1 + (p - 1) + (p^2 - p) + \ldots + (p^{\alpha} - p^{\alpha - 1})</math>
 
−
 
−
::::<math>= p^{\alpha}</math>
 
−
 
−
Jeżeli <math>n</math> jest postaci <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to
 
−
 
−
::<math>F(n) = F (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) =</math>
 
−
 
−
:::<math>\;\;\;\, = F (p^{\alpha_1}_1) \cdot \ldots \cdot F (p^{\alpha_s}_s) =</math>
 
−
 
−
:::<math>\;\;\;\, = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>
 
−
 
−
:::<math>\;\;\;\, = n</math>
 
−
 
−
Niech <math>1 < d_1 < d_2 < \ldots < n</math> będą dzielnikami liczby <math>n</math>. Zauważmy, że kiedy <math>d</math> przebiega zbiór dzielników <math>\{ 1, d_1, d_2, \ldots, n \}</math>, to <math>e = {\small\frac{n}{d}}</math> przebiega wszystkie te liczby tylko w&nbsp;odwrotnej kolejności. Zatem
 
−
 
−
::<math>\sum_{d \mid n} \varphi (d) = \sum_{d \mid n} \varphi \left( {\small\frac{n}{d}} \right)</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H45" style="font-size: 110%; font-weight: bold;">Zadanie H45</span><br/>
 
−
Niech <math>n \geqslant 2</math>. Pokazać, że suma liczb całkowitych dodatnich nie większych od <math>n</math> i&nbsp;względnie pierwszych z <math>n</math> jest równa <math>{\small\frac{1}{2}} n \varphi (n)</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Łatwo sprawdzamy, że wzór jest prawdziwy dla <math>n = 2</math> i&nbsp;odtąd będziemy przyjmowali, że <math>n \geqslant 3</math>. Zatem wartości <math>\varphi (n)</math> są liczbami parzystymi i&nbsp;niech <math>c = {\small\frac{1}{2}} \varphi (n)</math>. Zauważmy, że jeżeli liczba <math>a</math> jest względnie pierwsza z <math>n</math>, to liczba <math>n - a</math> jest również względnie pierwsza z <math>n</math>, bo <math>\gcd (a, n) = \gcd (n - a, n)</math>. Wypiszmy wszystkie liczby całkowite dodatnie nie większe od <math>n</math> i&nbsp;względnie pierwsze z <math>n</math> w&nbsp;kolejności rosnącej, a&nbsp;pod spodem w&nbsp;kolejności malejącej
 
−
 
−
::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
 
−
|-
 
−
| <math>1</math> || <math>a_2</math> || <math>…</math> || <math>a_c</math> || <math>n - a_c</math> || <math>…</math> || <math>n - a_2</math> || <math>n - 1</math>
 
−
|-
 
−
| <math>n - 1</math> || <math>n - a_2</math> || <math>…</math> || <math>n - a_c</math> || <math>a_c</math> || <math>…</math> || <math>a_2</math> || <math>1</math>
 
−
|}
 
−
 
−
Suma liczb w&nbsp;każdej kolumnie jest równa <math>n</math>. Ponieważ ilość liczb względnie pierwszych z <math>n</math> jest równa <math>\varphi (n)</math>, to podwojona suma liczb całkowitych nie większych od <math>n</math> i&nbsp;pierwszych względem <math>n</math> wynosi <math>n \varphi (n)</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H46" style="font-size: 110%; font-weight: bold;">Zadanie H46</span><br/>
 
−
Pokazać, że dla liczb naturalnych nieparzystych <math>n \geqslant 5</math> prawdziwe jest oszacowanie <math>\varphi (n) > \pi (n)</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
'''1.''' Jeżeli <math>n \geqslant 5</math> jest liczbą pierwszą, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze mniejsze od <math>n</math> oraz liczby <math>1, 4</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - 1 + 2 > \pi (n)</math>.
 
−
 
−
'''2.''' Jeżeli <math>n = p^a</math>, gdzie <math>a \geqslant 2</math>, jest potęgą liczby pierwszej nieparzystej, to <math>n \geqslant 9</math> i&nbsp;liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczby <math>p</math>) oraz liczby <math>1, 4, 8</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - 1 + 3 > \pi (n)</math>.
 
−
 
−
'''3.''' Jeżeli <math>n</math> ma więcej niż jeden dzielnik pierwszy nieparzysty, to <math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>, gdzie <math>s \geqslant 2</math>. Zauważmy, że
 
−
 
−
::<math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \geqslant q_1 \cdot \ldots \cdot q_s \geqslant 3 \cdot 5^{s - 1} > 2^{2 s - 1}</math>
 
−
 
−
Liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb <math>q_1, \ldots, q_s</math>) oraz liczby <math>1, 2^2, 2^3, \ldots, 2^{2 s - 1}</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - s + 2 s - 1 = \pi (n) + s - 1 > \pi (n)</math>
 
−
 
−
Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H47" style="font-size: 110%; font-weight: bold;">Zadanie H47</span><br/>
 
−
Pokazać, że dla liczb naturalnych <math>n \geqslant 91</math> prawdziwe jest oszacowanie <math>\varphi (n) > \pi (n)</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Ponieważ <math>p_{2 s} > 1</math> i <math>p_{2 s} \geqslant p_{s + 1}</math>, to z&nbsp;zadania A40 natychmiast wynika nierówność
 
−
 
−
::<math>p_1 p_2 \cdot \ldots \cdot p_s > p_{s + 1} p_{2 s}</math>
 
−
 
−
która jest prawdziwa dla <math>n \geqslant 4</math>.
 
−
 
−
Pokażemy najpierw, że dla każdej liczby naturalnej mającej nie mniej niż cztery dzielniki pierwsze nierówność <math>\varphi (n) > \pi (n)</math> jest zawsze prawdziwa.
 
−
 
−
Przez <math>p_1, p_2, \ldots, p_k, \ldots</math> oznaczymy kolejne liczby pierwsze. Niech <math>n \geqslant 2</math> będzie liczbą naturalną i <math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>, gdzie <math>q_i</math> oznaczają dowolne (nie muszą być kolejne) liczby pierwsze.
 
−
 
−
Wśród kolejnych <math>2 s</math> liczb pierwszych znajduje się przynajmniej <math>s</math> liczb pierwszych '''różnych''' od każdej z&nbsp;liczb <math>q_1, \ldots, q_s</math>. Jeśli oznaczymy te liczby (w rosnącej kolejności) przez <math>r_1, \ldots, r_s</math>, to łatwo zauważymy, że prawdziwe są dla nich następujące oszacowania
 
−
 
−
:*&nbsp;&nbsp;&nbsp;dla najmniejszej liczby <math>r_1 \leqslant p_{s + 1}</math>
 
−
 
−
:*&nbsp;&nbsp;&nbsp;dla wszystkich liczb <math>r_j \leqslant p_{2 s}</math> dla <math>j = 1, \ldots, s</math>.
 
−
 
−
Korzystając z&nbsp;wypisanej na początku dowodu nierówności, dla <math>s \geqslant 4</math> mamy
 
−
 
−
::<math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \geqslant q_1 \cdot \ldots \cdot q_s \geqslant p_1 \cdot \ldots \cdot p_s > p_{s + 1} p_{2 s} \geqslant r_1 \cdot r_j</math>
 
−
 
−
gdzie <math>j = 1, \ldots, s</math>.
 
−
 
−
Wynika stąd, że jeśli <math>s \geqslant 4</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb pierwszych <math>q_1, \ldots, q_s</math>) oraz liczby <math>1</math> i <math>r_1 r_j</math>, gdzie <math>j = 1, \ldots, s</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - s + s + 1> \pi (n)</math>
 
−
 
−
Co mieliśmy pokazać.
 
−
 
−
 
−
Uwzględniając rezultat pokazany w&nbsp;zadaniu [[#H46|H46]], pozostaje sprawdzić przypadki gdy <math>n = 2^a</math>, <math>n = 2^a p^b</math>, <math>n = 2^a p^b q^c</math>, gdzie <math>a, b, c \in \mathbb{Z}_+</math>.
 
−
 
−
'''1.''' Niech <math>n = 2^a</math>. Jeśli <math>n \geqslant 16</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczby <math>2</math>) oraz liczby <math>1, 9, 15</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - 1 + 3 > \pi (n)</math>
 
−
 
−
'''2.''' Niech <math>n = 2^a p^b</math>, zaś <math>r</math> będzie najmniejszą liczbą pierwszą nieparzystą różną od <math>p</math>. Oczywiście <math>r \in \{ 3, 5 \}</math> i&nbsp;jeśli tylko <math>n > 5^3 = 125</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb pierwszych <math>2</math> i <math>p</math>) oraz liczby <math>1, r^2, r^3</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - 2 + 3 > \pi (n)</math>
 
−
 
−
'''3.''' Niech <math>n = 2^a p^b q^c</math>, zaś <math>r</math> będzie najmniejszą liczbą pierwszą nieparzystą różną od <math>p</math> oraz różną od <math>q</math>. Oczywiście <math>r \in \{ 3, 5, 7 \}</math> i&nbsp;jeśli <math>n > 7^4 = 2401</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb pierwszych <math>2</math>, <math>p</math> i <math>q</math>) oraz liczby <math>1, r^2, r^3, r^4</math>. Zatem
 
−
 
−
::<math>\varphi (n) \geqslant \pi (n) - 3 + 4 > \pi (n)</math>
 
−
 
−
Zbierając: pozostaje sprawdzić bezpośrednio przypadki, gdy <math>n</math> jest liczbą parzystą i <math>n \leqslant 2401</math>. W&nbsp;GP/PARI wystarczy napisać polecenie
 
−
 
−
<span style="font-size: 90%; color:black;">for(n = 1, 2500, if( eulerphi(n) <= primepi(n), print(n) ))</span>
 
−
 
−
Nierówność <math>\varphi (n) > \pi (n)</math> nie jest prawdziwa dla <math>n \in \{ 2, 3, 4, 6, 8, 10, 12, 14, 18, 20, 24, 30, 42, 60, 90 \}</math>. Co kończy dowód.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span id="H48" style="font-size: 110%; font-weight: bold;">Zadanie H48</span><br/>
 
−
Pokazać, że <math>\varphi (n) = 2^a</math> wtedy i&nbsp;tylko wtedy, gdy <math>n = 2^b q_1 \cdot \ldots \cdot q_s</math>, gdzie <math>q_1, \ldots, q_s</math> są liczbami pierwszymi Fermata: <math>3, 5, 17, 257, 65537</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
W przypadku, gdy <math>2 \mid n</math>, łatwo zauważamy, że liczba <math>2</math> może występować w&nbsp;dowolnej potędze, bo <math>\varphi (2^b) = 2^{b - 1}</math>.
 
−
 
−
W przypadku, gdy <math>p \mid n</math>, gdzie <math>p</math> jest liczbą pierwszą nieparzystą, mamy <math>\varphi (p^k) = (p - 1) p^{k - 1}</math> i&nbsp;równie łatwo zauważmy, że musi być <math>k = 1</math>, a&nbsp;liczba <math>p - 1</math> musi być potęgą liczby <math>2</math>. Zatem liczba pierwsza <math>p</math> musi być postaci <math>p = 2^t + 1</math>, co jest możliwe tylko wtedy, gdy <math>t</math> jest potęgą liczby <math>2</math> (zobacz C48), czyli <math>p</math> musi być liczbą pierwszą Fermata. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span style="font-size: 110%; font-weight: bold;">Zadanie H49</span><br/>
 
−
Pokazać, że funkcja Eulera spełnia warunek <math>\varphi (n) = \frac{n}{2}</math> wtedy i tylko wtedy, gdy <math>n = 2^k</math>.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Zauważmy, że <math>n</math> musi być liczbą parzystą, zatem <math>n = 2^k m</math>, gdzie <math>m</math> jest liczbą nieparzystą. Otrzymujemy
 
−
 
−
::<math>\varphi (n) = \varphi (2^k m) = \varphi (2^k) \varphi (m) = 2^{k - 1} \varphi (m) = \frac{2^k m}{2} \cdot \frac{\varphi (m)}{m} = \frac{n}{2} \cdot \frac{\varphi (m)}{m}</math>
 
−
 
−
ale <math>\frac{\varphi (m)}{m} = 1</math> wtedy i tylko wtedy, gdy <math>m = 1</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
<span style="font-size: 110%; font-weight: bold;">Zadanie H50</span><br/>
 
−
Pokazać, że funkcja Eulera spełnia warunek <math>\varphi (n) = \frac{n}{2} - 1</math> wtedy i tylko wtedy, gdy <math>n = 2 q</math>, gdzie <math>q \geqslant 3</math> jest liczbą pierwszą.
 
−
 
−
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
 
−
Oczywiście <math>n</math> musi być liczbą parzystą, zatem <math>n = 2^k m</math>, gdzie <math>m</math> jest liczbą nieparzystą. Możemy teraz zapisać warunek <math>\varphi (n) = \frac{n}{2} - 1</math> w postaci
 
−
 
−
::<math>\varphi (n) = \varphi (2^k m) = \varphi (2^k) \varphi (m) = 2^{k - 1} \varphi (m) = 2^{k - 1} m - 1</math>
 
−
 
−
Ponieważ <math>\varphi (n)</math> dla <math>n \geqslant 3</math> jest liczbą parzystą (zobacz H38), to nie może być <math>k \geqslant 2</math>, bo strony równania miałyby różną parzystość. Zatem musi być <math>n = 2 m</math>, gdzie <math>m</math> jest liczbą nieparzystą
 
−
 
−
::<math>\varphi (n) = \varphi (2 m) = \varphi (2) \varphi (m) = \varphi (m) = m - 1</math>
 
−
 
−
Z twierdzenia H43 wynika natychmiast, że <math>m</math> musi być liczbą pierwszą. Ponieważ najmniejszymi liczbami, dla których warunek <math>\varphi (n) = \frac{n}{2} - 1</math> jest spełniony są <math>n = 6, 10, 14, \ldots</math>, to musi być <math>m \geqslant 3</math>. Co należało pokazać.<br/>
 
−
&#9633;
 
−
{{\Spoiler}}
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
 
−
== Przypisy ==
 
−
 
−
<references>
 
−
 
−
<ref name="GCD1">Wikipedia, ''Największy wspólny dzielnik'', ([https://pl.wikipedia.org/wiki/Najwi%C4%99kszy_wsp%C3%B3lny_dzielnik Wiki-pl]), ([https://en.wikipedia.org/wiki/Greatest_common_divisor Wiki-en])</ref>
 
−
 
−
<ref name="cardinality1">Wikipedia, ''Moc zbioru'', ([https://pl.wikipedia.org/wiki/Moc_zbioru Wiki-pl]), ([https://en.wikipedia.org/wiki/Cardinality Wiki-en])</ref>
 
−
 
−
<ref name="sumazbiorow">Wikipedia, ''Zasada włączeń i&nbsp;wyłączeń'', ([https://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84 Wiki-pl]), ([https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Wiki-en])</ref>
 
−
 
−
<ref name="Euler1">Wikipedia, ''Funkcja φ'', ([https://pl.wikipedia.org/wiki/Funkcja_%CF%86 Wiki-pl]), ([https://en.wikipedia.org/wiki/Euler%27s_totient_function Wiki-en])</ref>
 
−
 
−
</references>
 
  
  
  
 +
<div style="font-size: 75%;">Some rights reserved.
  
 +
(CC) 2009 - 2020 by Henryk Dąbrowski
  
  
 +
Żadna część jak i całość niniejszego opracowania nie może być wykorzystywana w celach komercyjnych, bez uprzedniej pisemnej zgody autora.
  
 +
Dozwolone jest kopiowanie, rozpowszechnianie, przedstawianie i wykonywanie treści jedynie w celach niekomercyjnych pod warunkiem zachowania jej w&nbsp;oryginalnej postaci. Niedozwolone jest jej zmienianie i/lub tworzenie na jej bazie utworów pochodnych.
  
  
 +
Kontakt: brakkarysmierci@gmail.com
  
  
 +
</div>
  
  
−
&nbsp;
+
<span class="plainlinks">[https://henryk-dabrowski.pl/index.php?title=Aborcja_%E2%80%93_orzeczenie_Trybuna%C5%82u_Konstytucyjnego_z_1997_roku <span style="font-size: 50%; line-height: 0.5em; color: transparent;">LINK</span>]</span>

Aktualna wersja na dzień 16:40, 8 kwi 2024

Wolność nie czyni ludzi szczęśliwymi, czyni ich po prostu ludźmi


Powitanie
Brak kary śmierci w kodeksie karnym jest pogardą dla ofiar

Prawa ustanowione są dla sprawiedliwych nie dlatego, by nie popełniali nieprawości, lecz by jej nie doznawali.

Epikur83x100.png  Epikur

Jestem głosem zamordowanych. Jestem głosem tych, których godność i prawo do życia uczyniono mniej znaczącymi od godności i prawa do życia morderców. Jestem głosem tych, którzy nie mogą się już bronić. Jestem głosem niezgody na Twoje milczenie.


Pobierz artykuły dotyczące kary śmierci – plik PDF


Historia
Powstanie Warszawskie

Celem wojny nie jest śmierć za ojczyznę, ale sprawienie, aby tamci skurwiele umierali za swoją.

Patton94x133.png gen. George Patton

Polska
Prawo – artykuł 257 kodeksu karnego
Lewactwo

Nie logika, lecz chęć szczera zrobi z ciebie myśliciela.

Nam bajki trzeba pisać. Powiem więcej: brednie... Niech przy naszych bajkach nawet prawda zblednie.

Ślepi prowadzą ociemniałych ku świetlanej przyszłości.

Czytasz: "Dla nas najważniejszy jest człowiek" i myślisz, że to o Tobie mówią? To błąd. Człowiek to pederasta, lesbijka, zboczeniec, morderca, gwałciciel, złodziej, bandyta, feministka, uchodźca, imigrant, a w ostateczności niepełnosprawny. Jeśli nie zaliczasz się do wymienionych, to nie o Tobie mówią...

Nawet Kościół nie obieca wam takiego raju w niebie, jaki lewactwo obieca wam na ziemi.

Pederaści, lesbijki i homopropaganda
Wiersze
Edukacja


Najnowsze artykuły


Drogi Czytelniku!

Przygotowanie niektórych artykułów wymagało nawet kilkudziesięciu godzin pracy. Większość tekstów to nie są felietony, a opracowania i tłumaczenia, których próżno szukać w mediach głównego nurtu. Jeśli chciałbyś dobrowolnie wesprzeć ten wysiłek i pomóc w rozwoju strony, proszę o dokonanie wpłaty na podane niżej konto bankowe.

Dziękuję za Twoją życzliwą pomoc!
Henryk Dąbrowski



Dane konta bankowego do wykonania wpłaty


Wpłaty



Some rights reserved.

(CC) 2009 - 2020 by Henryk Dąbrowski


Żadna część jak i całość niniejszego opracowania nie może być wykorzystywana w celach komercyjnych, bez uprzedniej pisemnej zgody autora.

Dozwolone jest kopiowanie, rozpowszechnianie, przedstawianie i wykonywanie treści jedynie w celach niekomercyjnych pod warunkiem zachowania jej w oryginalnej postaci. Niedozwolone jest jej zmienianie i/lub tworzenie na jej bazie utworów pochodnych.


Kontakt: brakkarysmierci@gmail.com



LINK

Źródło: „https://henryk-dabrowski.pl/index.php?title=Największy_wspólny_dzielnik,_element_odwrotny_modulo,_funkcja_Eulera&oldid=704”