Ferma, Eyler və Vilson Teoremləri

İsbat. İsbatın ideyası çox gözəldir və heç bir mürəkkəb texnika tələb etmir. Aşağıdakı $p-1$ sayda ədədə baxaq:

$$a,\quad 2a,\quad 3a,\quad \dots,\quad (p-1)a .$$

İddia edirik ki, bu ədədlərin $p$ moduluna görə qalıqları — sırası dəyişmiş şəkildə — məhz $1, 2, \dots, p-1$ ədədləridir.Bunu iki addımda görək.Birinci addım: heç biri sıfır qalıq vermir. Əgər hansısa $1 \le i \le p-1$ üçün $p \mid ia$ olsaydı, $p$ sadə olduğuna görə Evklid lemmasına (Dərs 4) əsasən $p \mid i$ və ya $p \mid a$ alınardı. Birincisi mümkün deyil, çünki $1 \le i \le p-1$; ikincisi isə şərtə ziddir. Deməli, hər bir $ia$ ədədinin qalığı $1, 2, \dots, p-1$ arasındadır.İkinci addım: qalıqlar cüt-cüt fərqlidir. Tutaq ki, $1 \le i < j \le p-1$ üçün

$$ia \equiv ja \pmod p .$$

Onda $p \mid (j-i)a$ olur. Yenə Evklid lemmasına görə $p \mid a$ və ya $p \mid (j-i)$. Birincisi şərtə ziddir, ikincisi isə $0 < j - i < p$ olduğuna görə mümkün deyil. Ziddiyyət. Deməli, bütün qalıqlar fərqlidir.İndi hesabı aparaq: $p-1$ sayda ədədimiz var, hər birinin qalığı $\{1, 2, \dots, p-1\}$ çoxluğundandır və hamısı fərqlidir. Sonlu çoxluqda bu, o deməkdir ki, qalıqlar həmin çoxluğu tam örtür — yalnız sıra dəyişir. Ona görə də bu ədədlərin hasili ilə $1 \cdot 2 \cdots (p-1)$ hasili $p$ moduluna görə eyni qalığı verir:

$$a \cdot 2a \cdot 3a \cdots (p-1)a \;\equiv\; 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod p .$$

Sol tərəfdə $a$-nı mötərizədən çıxaraq:

$$a^{\,p-1} \cdot (p-1)! \;\equiv\; (p-1)! \pmod p .$$

Son addım: $(p-1)!$ ədədi $1$-dən $p-1$-ə qədər olan vuruqların hasilidir və bunların heç biri $p$-yə bölünmür; $p$ sadə olduğundan $\big((p-1)!,\, p\big) = 1$. Deməli, Dərs 5-dəki ixtisar qaydasına görə hər iki tərəfi $(p-1)!$ ədədinə ixtisar edə bilərik:

$$a^{\,p-1} \equiv 1 \pmod p .$$

■

İsbat. İki halı ayıraq.Əgər $p \mid a$ olarsa, sol tərəf də, sağ tərəf də $p$-yə bölünür ($a^p$ ədədi $a$-ya, o da $p$-yə bölünür), yəni hər ikisi $0$ qalığını verir və bərabərlik doğrudur.Əgər $p \nmid a$ olarsa, teoremə görə $a^{p-1} \equiv 1 \pmod p$; hər iki tərəfi $a$-ya vursaq, $a^{p} \equiv a \pmod p$ alırıq. ■

İsbat. Birinci hissə Fermanın kiçik teoreminin ikinci formasıdır. İkinci hissə üçün $k - 1 = (p-1)t$ yazaq. Əgər $p \mid n$ olarsa, $n^{k} - n$ ədədinin hər iki toplananı $p$-yə bölünür. Əks halda $(n,p)=1$ və

$$n^{k-1} = \left(n^{\,p-1}\right)^{t} \equiv 1 \pmod p ,$$

buradan hər iki tərəfi $n$-ə vurmaqla $n^{k} \equiv n \pmod p$, yəni $p \mid n^k - n$. ■

Həll. $p = 11$ sadədir, $(7,11)=1$, deməli $7^{10} \equiv 1 \pmod{11}$. Üstü $10$-a görə azaldaq: $2026 = 10 \cdot 202 + 6$, yəni $7^{2026} \equiv 7^{6} \pmod{11}$.İndi $7^6$-nı addım-addım hesablayaq: $7^2 = 49 \equiv 5$, $7^3 \equiv 5 \cdot 7 = 35 \equiv 2$, $7^6 = \left(7^3\right)^2 \equiv 2^2 = 4 \pmod{11}$. Cavab: $4$□

Həll. Axtardığımız ədəd elə sadə $p$-lərin hasilidir ki, $p - 1 \mid 20$ şərti ödənsin (yuxarıdakı teoremə görə məhz bu şərtdə $p \mid n^{21}-n$ hər $n$ üçün doğrudur).$20$-nin bölənləri: $1, 2, 4, 5, 10, 20$. Hər birinə bir vahid əlavə edib sadə olanları seçək: $2$ (sadə), $3$ (sadə), $5$ (sadə), $6$ (sadə deyil), $11$ (sadə), $21$ (sadə deyil).Deməli axtarılan ədəd $2 \cdot 3 \cdot 5 \cdot 11 = 330$.Bu ədədin ən böyük olduğunu görmək üçün $n = 2$ götürmək kifayətdir: $2^{21} - 2 = 2097150 = 330 \cdot 6355$ və bu ədədin $330$-dan başqa universal bölən verə biləcəyini iddia etsək, məsələn $p^2$ tipli bir vuruq üçün $n=p$ halı dərhal ziddiyyət verir. Cavab: $330$□

Həll. Cəmdəki hər bir əsas $1$-dən $p-1$-ə qədərdir, deməli heç biri $p$-yə bölünmür. Fermanın kiçik teoreminə görə hər bir toplanan $1$ qalığını verir:

$$k^{\,p-1} \equiv 1 \pmod p, \qquad k = 1, 2, \dots, p-1 .$$

Toplananların sayı $p-1$ olduğundan cəm

$$\underbrace{1 + 1 + \dots + 1}_{p-1 \text{ dəfə}} = p - 1 \equiv -1 \pmod p .$$

Cavab: Cəm $-1$, yəni $p-1$ qalığını verir.□

Həll. Fərz edək ki, belə $n > 1$ var. Əvvəlcə qeyd edək ki, $2^n - 1$ tək ədəddir, deməli onun böləni olan $n$ də təkdir; xüsusən $n \ge 3$.$n$ ədədinin ən kiçik sadə bölənini $p$ ilə işarə edək. $p$ tək sadə ədəddir və $p \mid 2^{n} - 1$, yəni

$$2^{n} \equiv 1 \pmod p .$$

Digər tərəfdən, $(2,p)=1$ olduğuna görə Fermanın kiçik teoreminə əsasən

$$2^{\,p-1} \equiv 1 \pmod p .$$

Dərs 6-da gördüyümüz kimi, $2$-nin $p$ moduluna görə mərtəbəsi — ən kiçik müsbət $d$ üçün $2^d \equiv 1$ — belə bütün üstləri bölür. Deməli $d \mid n$ və $d \mid p-1$, yəni $d \mid (n,\, p-1)$.İndi əsas müşahidə: $p$ ədədi $n$-in ən kiçik sadə bölənidir, ona görə $n$-in $1$-dən böyük heç bir böləni $p$-dən kiçik ola bilməz. $p - 1 < p$ olduğundan $(n,\, p-1)$ ədədi $p$-dən kiçikdir, deməli o, $1$-ə bərabər olmalıdır. Buradan $d = 1$, yəni $2^{1} \equiv 1 \pmod p$, yəni $p \mid 1$ — mümkün deyil.Ziddiyyət göstərir ki, belə $n > 1$ mövcud deyil. Cavab: Yalnız $n = 1$ ödəyir.□

İsbat. $1$-dən $p^k$-ya qədər olan ədədlərdən hansıları $p^k$ ilə qarşılıqlı sadə deyil? $p^k$ ədədinin yeganə sadə böləni $p$-dir, deməli $(m, p^k) > 1$ olması yalnız $p \mid m$ deməkdir.$1$-dən $p^k$-ya qədər $p$-yə bölünən ədədlər $p, 2p, 3p, \dots, p^{k-1} \cdot p$ ədədləridir; onların sayı $p^{k-1}$-dir. Qalanları isə $p$ ilə, deməli $p^k$ ilə də qarşılıqlı sadədir. Beləliklə $\varphi(p^k) = p^k - p^{k-1}$. ■

İsbat. $1$-dən $mn$-ə qədər olan ədədləri $m$ sütunlu bir cədvələ düzək:

$$\begin{array}{cccc} 1 & 2 & \cdots & m \\ m+1 & m+2 & \cdots & 2m \\ \vdots & \vdots & & \vdots \\ (n-1)m+1 & (n-1)m+2 & \cdots & nm \end{array}$$

Bir sütundakı bütün ədədlər $m$ moduluna görə eyni qalığı verir. Deməli $m$ ilə qarşılıqlı sadə olanlar tam olaraq $\varphi(m)$ sayda sütunda yerləşir; qalan sütunlarda bir dənə də uyğun ədəd yoxdur.İndi belə bir sütuna baxaq — deyək ki, qalığı $r$ olan sütun, yəni

$$r,\quad r+m,\quad r+2m,\quad \dots,\quad r+(n-1)m .$$

Bu $n$ ədədin $n$ moduluna görə qalıqları nədir? $(m,n)=1$ olduğuna görə Dərs 5-dəki ixtisar qaydasına əsasən $r + im \equiv r + jm \pmod n$ münasibətindən $i \equiv j \pmod n$ alınır; $0 \le i, j \le n-1$ olduğundan $i = j$. Deməli bu $n$ ədədin qalıqları cüt-cüt fərqlidir və beləliklə $0, 1, \dots, n-1$ qalıqlarının hamısını bir dəfə verir. Onlardan $n$ ilə qarşılıqlı sadə olanların sayı $\varphi(n)$-dir.Yekunda: uyğun sütunların sayı $\varphi(m)$, hər sütunda uyğun ədədlərin sayı $\varphi(n)$, deməli ümumi say $\varphi(m)\varphi(n)$-dir. ■

İsbat. Kanonik ayrılışdakı vuruqlar cüt-cüt qarşılıqlı sadədir, ona görə multiplikativliyi ardıcıl tətbiq edərək

$$\varphi(n) = \varphi\!\left(p_1^{a_1}\right) \cdots \varphi\!\left(p_k^{a_k}\right) = p_1^{a_1}\!\left(1 - \tfrac{1}{p_1}\right) \cdots p_k^{a_k}\!\left(1 - \tfrac{1}{p_k}\right),$$

və $p_1^{a_1} \cdots p_k^{a_k} = n$ olduğundan istənilən düstur alınır. ■

Həll. Əvvəlcə $n$-in mümkün sadə bölənlərini müəyyən edək. Əgər $p \mid n$ olarsa, düsturda $p-1$ vuruğu iştirak edir və o, $\varphi(n) = 8$ ədədini bölür. Deməli $p - 1 \mid 8$, yəni $p \in \{2, 3, 5\}$ (çünki $p-1 \in \{1,2,4,8\}$ üçün $p \in \{2,3,5,9\}$ və $9$ sadə deyil).Həmçinin $p^2 \mid n$ olarsa, düsturda $p$ vuruğu qalır, yəni $p \mid 8$; bu isə yalnız $p = 2$ üçün mümkündür. Deməli $n = 2^a \cdot 3^b \cdot 5^c$, burada $b, c \in \{0, 1\}$.İndi bütün halları yoxlayaq:

$$\varphi\!\left(2^a\right) \cdot \varphi\!\left(3^b\right) \cdot \varphi\!\left(5^c\right) = 8 .$$

$b = c = 0$: $\varphi(2^a) = 8 \Rightarrow 2^{a-1} = 8 \Rightarrow a = 4$, yəni $n = 16$.$b = 1, c = 0$: $\varphi(2^a) \cdot 2 = 8 \Rightarrow \varphi(2^a) = 4 \Rightarrow a = 3$, yəni $n = 24$.$b = 0, c = 1$: $\varphi(2^a) \cdot 4 = 8 \Rightarrow \varphi(2^a) = 2 \Rightarrow a = 2$, yəni $n = 20$. (Burada $\varphi(2^0) = \varphi(2^1) = 1 \ne 2$ olduğuna görə $a = 0$ və $a = 1$ halları düşür.)$b = 1, c = 1$: $\varphi(2^a) \cdot 2 \cdot 4 = 8 \Rightarrow \varphi(2^a) = 1 \Rightarrow a \in \{0, 1\}$, yəni $n = 15$ və $n = 30$.Beləliklə həllər: $15, 16, 20, 24, 30$. Cavab: $n \in \{15,\,16,\,20,\,24,\,30\}$; cəmi beş həll.□

Həll. Düstura görə

$$\frac{\varphi(n)}{n} = \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = \frac12 .$$

Əgər $n$-in tək sadə böləni $q$ olsaydı, hasilə $1 - \tfrac1q = \tfrac{q-1}{q}$ vuruğu daxil olardı və məxrəcdə $q$ (tək sadə ədəd) qalardı; halbuki sağ tərəfin məxrəci $2$-dir. Daha dəqiq: $\tfrac12$ kəsrini yalnız $p = 2$ vuruğu verir, əlavə hər hansı $\tfrac{q-1}{q}$ vuruğu ($q \ge 3$) hasili kiçildərək $\tfrac12$-dən aşağı salır.Deməli $n$-in yeganə sadə böləni $2$-dir, yəni $n = 2^{k}$, $k \ge 1$. Yoxlayaq: $\varphi(2^k) = 2^{k-1} = \tfrac{2^k}{2}$ — ödənir. Cavab: $n = 2^{k}$, $k \ge 1$, yəni $2, 4, 8, 16, \dots$□

Həll. $n$-in kanonik ayrılışını $n = 2^{a} m$ şəklində yazaq, burada $m$ təkdir.Əgər $m$-in iki müxtəlif tək sadə böləni olsaydı, $\varphi(n)$ ədədi $4$-ün qatı olardı və $\varphi(n)$-də görünən $\tfrac{n}{\varphi(n)}$ nisbətinin məxrəci tək vuruqlar saxlayardı. Daha aydın yol: nisbətə baxaq.

$$\frac{n}{\varphi(n)} = \prod_{p \mid n} \frac{p}{p-1}.$$

Bu nisbətin tam ədəd olması tələb olunur. Vuruqları sadə-sadə yoxlayaq:Yalnız $p = 2$: nisbət $2$ — tamdır, $n = 2^a$.Yalnız $p = 3$: nisbət $\tfrac32$ — tam deyil.$p = 2$ və $p = 3$: nisbət $2 \cdot \tfrac32 = 3$ — tamdır, $n = 2^a 3^b$ ($a, b \ge 1$).$p = 2$ və $p \ge 5$: nisbət $2 \cdot \tfrac{p}{p-1}$; $\tfrac{p}{p-1}$ ən sadə şəkildə yazılmış kəsrdir və məxrəci $p - 1 \ge 4$-dür, $2$ ilə vurmaq bunu tam etmir.Üç və daha çox sadə vuruq halında məxrəcdə ən azı bir $p-1 \ge 4$ qalır və eyni səbəbdən tamlıq pozulur.Cavab: $n = 2^{a}$ ($a \ge 1$) və $n = 2^{a} 3^{b}$ ($a, b \ge 1$).□

İsbat. Hər hasil $n$ ilə qarşılıqlı sadədir. Əgər $(a,n)=1$ və $(r_i, n) = 1$ olarsa, onda $(a r_i, n) = 1$ — çünki $n$-in hər hansı sadə böləni $a r_i$ hasilini bölsəydi, Evklid lemmasına görə ya $a$-nı, ya da $r_i$-ni bölərdi, ikisi də mümkün deyil. Deməli hər $a r_i$ ədədinin qalığı $R_n$-dədir.Qalıqlar fərqlidir. Əgər $a r_i \equiv a r_j \pmod n$ olarsa, $(a,n)=1$ olduğuna görə Dərs 5-dəki ixtisar qaydası ilə $r_i \equiv r_j \pmod n$; hər ikisi $1$ ilə $n$ arasında olduğundan $r_i = r_j$, yəni $i = j$.$\varphi(n)$ sayda fərqli element $\varphi(n)$ elementli çoxluğa düşürsə, çoxluq tam örtülür. ■

İsbat. Lemmaya görə $\{a r_1, \dots, a r_{\varphi(n)}\}$ çoxluğunun qalıqları $\{r_1, \dots, r_{\varphi(n)}\}$ çoxluğu ilə üst-üstə düşür. Deməli hasilləri də $n$ moduluna görə bərabərdir:

$$(a r_1)(a r_2) \cdots (a r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n .$$

Sol tərəfdə $a$ vuruğunu ayıraq:

$$a^{\,\varphi(n)} \cdot r_1 r_2 \cdots r_{\varphi(n)} \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n .$$

Hər bir $r_i$ ədədi $n$ ilə qarşılıqlı sadədir, deməli hasilləri də $n$ ilə qarşılıqlı sadədir və ixtisar qaydasına görə hər iki tərəfi ona ixtisar edə bilərik:

$$a^{\,\varphi(n)} \equiv 1 \pmod n .$$

■