Tekst źródłowy strony Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera

<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.12.2023</div>

__FORCETOC__



== Największy wspólny dzielnik ==

<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 [[Ciągi liczbowe#C74|C74]]) 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}}



<span id="H4" style="font-size: 110%; font-weight: bold;">Twierdzenie H4</span><br/>
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>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z lematu Bézouta (zobacz [[Ciągi liczbowe#C74|C74]]) 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

::<math>(d k) x + (d m) y = d</math>

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/>
&#9633;
{{\Spoiler}}



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



<span id="H6" style="font-size: 110%; font-weight: bold;">Twierdzenie H6</span><br/>
Niech <math>a, b, m \in \mathbb{Z}</math>. Prawdziwa jest następująca równoważność

::<math>\gcd (a, m) = 1 \quad  \text{i} \quad \gcd (b, m) = 1 \quad \qquad \Longleftrightarrow \quad \qquad \gcd (a b, m) = 1</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

<math>\Large{\Longrightarrow}</math>

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 [[Ciągi liczbowe#C75|C75]]). 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>.

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



<span id="H7" style="font-size: 110%; font-weight: bold;">Twierdzenie H7</span><br/>
Dla <math>a, b, m \in \mathbb{Z}</math> jest

::<math>\gcd (a b, m) \mid \gcd (a, m) \cdot \gcd (b, 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>

::<math>t = \gcd (b, m)</math>

Z lematu Bézouta (zobacz [[Ciągi liczbowe#C74|C74]]) 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}}



<span id="H8" style="font-size: 110%; font-weight: bold;">Twierdzenie H8</span><br/>
Jeżeli liczby <math>a, b</math> są względnie pierwsze, to

::<math>\gcd (a b, m) = \gcd (a, m) \cdot \gcd (b, 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>

::<math>t = \gcd (b, m)</math>

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 [[Ciągi liczbowe#C76|C76]])

::<math>s \mid a \qquad \,\, \text{i} \qquad t \mid b \qquad \qquad \;\, \Longrightarrow \qquad \qquad s t \mid a b</math>

::<math>s \mid m \qquad \text{i} \qquad t \mid m \qquad \qquad \Longrightarrow \qquad \qquad s t \mid m</math>

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/>
&#9633;
{{\Spoiler}}



<span id="H9" style="font-size: 110%; font-weight: bold;">Twierdzenie H9</span><br/>
Jeżeli liczby <math>b, m</math> są względnie pierwsze, to

::<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}}



<span id="H10" style="font-size: 110%; font-weight: bold;">Twierdzenie H10</span><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;">
::<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="margin-top: 1.5em; margin-bottom: 1em;">
::<math>
\begin{array}{llll}
  d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d = a x + b y & \text{(lemat Bézouta C74)} \\
  &  &  & \\
  & \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}}



<span id="H11" style="font-size: 110%; font-weight: bold;">Zadanie H11</span><br/>
Pokazać, że jeżeli liczby <math>a, b</math> nie są jednocześnie równe zero, to

::<math>\gcd \left( {\small\frac{a}{\gcd (a, b)}}, {\small\frac{b}{\gcd (a, b)}} \right) = 1</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z twierdzenia [[#H10|H10]] otrzymujemy

::<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>

::::<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}}



<span id="H12" style="font-size: 110%; font-weight: bold;">Zadanie H12</span><br/>
Pokazać, że <math>a \mid b</math> wtedy i&nbsp;tylko wtedy, gdy <math>a \mid \gcd (a, 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>

Zakładając, że <math>a \mid b</math>, dostajemy 

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



<span id="H14" style="font-size: 110%; font-weight: bold;">Twierdzenie H14</span><br/>
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>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>d_1 = \gcd (d, a) \;</math> i <math>\; d_2 = \gcd (d, b)</math>. Z&nbsp;twierdzenia [[#H8|H8]] mamy

::<math>d_1 d_2 = \gcd (d, a) \cdot \gcd (d, b) = \gcd (d, a b) = d</math>

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

::<math>\gcd (d_1, d_2) = e \qquad \Longrightarrow \qquad e \mid d_1 \quad \text{i} \quad e \mid d_2</math>

::::::::<math>\, \Longrightarrow \qquad e \mid \gcd (d, a) \quad \text{i} \quad e \mid \gcd (d, b)</math>

::::::::<math>\, \Longrightarrow \qquad e \mid a \quad \text{i} \quad e \mid b</math>

::::::::<math>\, \Longrightarrow \qquad e \mid \gcd (a, b)</math>

::::::::<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 [[Ciągi liczbowe#C74|C74]]) 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}}



<span id="H16" style="font-size: 110%; font-weight: bold;">Uwaga H16</span><br/>
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

::<math>a^{- 1000} \equiv 1^{- 10} \equiv 1 \!\! \pmod{d}</math>

Omówimy ten problem w&nbsp;następnej sekcji. Zauważmy, wyprzedzając materiał, że z&nbsp;kongruencji

::<math>a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d}</math>

wynika, że <math>\gcd (a, d) = 1</math> i&nbsp;liczba <math>a</math> ma element odwrotny modulo <math>d</math>.





== Element odwrotny modulo <math>m</math> == 

<span id="H17" style="font-size: 110%; font-weight: bold;">Twierdzenie H17</span><br/>
Niech <math>m \in \mathbb{Z}_+</math>. Dla liczby <math>a \in \mathbb{Z}</math> istnieje taka liczba <math>x</math>, że

::<math>a x \equiv 1 \!\! \pmod{m}</math>

wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (a, m) = 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

<math>\Large{\Longrightarrow}</math>

Z założenia istnieje taka liczba <math>x</math>, że

::<math>a x \equiv 1 \!\! \pmod{m}</math>

Zatem dla pewnego <math>k \in \mathbb{Z}</math> jest

::<math>a x = 1 + k m</math>

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

<math>\Large{\Longleftarrow}</math>

Z założenia <math>\gcd (a, m) = 1</math>. Z&nbsp;lematu Bézouta (zobacz [[Ciągi liczbowe#C74|C74]]) wynika, że istnieją takie liczby całkowite <math>x, y</math>, że

::<math>a x + m y = 1</math>

Zatem modulo <math>m</math> dostajemy

::<math>a x \equiv 1 \!\! \pmod{m}</math>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span id="H18" style="font-size: 110%; font-weight: bold;">Definicja H18</span><br/>
Niech <math>m \in \mathbb{Z}_+</math>. Liczbę <math>x</math> taką, że

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



<span id="H19" style="font-size: 110%; font-weight: bold;">Uwaga H19</span><br/>
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

::<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 <span style="font-size: 90%; color:black;"><code>Mod(a, m)^(-1)</code></span>.



<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>{\small\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>{\small\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 [[Ciągi liczbowe#C75|C75]]), 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 [[Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n#B31|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>

Czyli

::<math>\log n < {\small\frac{1}{3}} n^{1 / 3}</math>

Wiemy (zobacz [[Twierdzenie Czebyszewa o funkcji π(n)#A38|A38]]), że dla dowolnego <math>a \in \mathbb{Z}_+</math> istnieje takie <math>n_0</math>, że dla każdego <math>n > n_0</math> jest <math>\log n < n^{1 / a}</math>. Zatem dla odpowiednio dużych <math>n</math> z&nbsp;pewnością będzie <math>\log n < {\small\frac{1}{3}} n^{1 / 3}</math>. Zamieszczony niżej obrazek przedstawia wykres funkcji <math>f(n) = {\small\frac{1}{3}} n^{1 / 3} - \log n</math>

::[[File: Euler1.png|1000px|none]]

Widoczne na wykresie miejsce zerowe funkcji <math>f(n)</math> znajdujemy, wpisując w&nbsp;PARI/GP polecenie

 <span style="font-size: 90%; color:black;">'''solve'''(n = 20000, 40000, 1/3 * n^(1/3) - '''log'''(n))</span>

Otrzymujemy

::<math>n = 29409.96 \ldots</math>

Zatem <math>{\small\frac{n}{3 \log n}} > n^{2 / 3} \;</math> dla <math>\; n > 29500</math>

Poleceniem

 <span style="font-size: 90%; color:black;">'''for'''(n = 1, 29500, '''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>

Czyli

::<math>\log n < {\small\frac{1}{3}} n^{1 / 4}</math>

Wpisując w&nbsp;PARI/GP polecenie

 <span style="font-size: 90%; color:black;">'''solve'''(n = 10^3, 10^7, 1/3 * n^(1/4) - '''log'''(n))

otrzymujemy

::<math>n = 4447862.68 \ldots</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 [[Twierdzenie Czebyszewa o funkcji π(n)#A41|A41]] 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 [[Ciągi liczbowe#C49|C49]]), czyli <math>p</math> musi być liczbą pierwszą Fermata. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="H49" style="font-size: 110%; font-weight: bold;">Zadanie H49</span><br/>
Pokazać, że funkcja Eulera spełnia warunek <math>\varphi (n) = {\small\frac{n}{2}}</math> wtedy i&nbsp;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) = {\small\frac{2^k m}{2}} \cdot {\small\frac{\varphi (m)}{m}} = {\small\frac{n}{2}} \cdot {\small\frac{\varphi (m)}{m}}</math>

ale <math>{\small\frac{\varphi (m)}{m}} = 1</math> wtedy i&nbsp;tylko wtedy, gdy <math>m = 1</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="H50" style="font-size: 110%; font-weight: bold;">Zadanie H50</span><br/>
Pokazać, że funkcja Eulera spełnia warunek <math>\varphi (n) = {\small\frac{n}{2}} - 1</math> wtedy i&nbsp;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) = {\small\frac{n}{2}} - 1</math> w&nbsp;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|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|H43]] wynika natychmiast, że <math>m</math> musi być liczbą pierwszą. Ponieważ najmniejszymi liczbami, dla których warunek <math>\varphi (n) = {\small\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>













&nbsp;