20 Euler’in Phi Fonksiyonu
Teorem 17.1’nda \(U(\mathbb{Z}_n)\) kümesinin bir grup olduğunu görmüştük. Bu grubun eleman sayısı, sayılar teorisinin en önemli fonksiyonlarından birini tanımlar. Bu bölümde o sayıyı hesaplamayı öğreneceğiz; bir sonraki bölümde ise onu Fermat teoremini genelleştirmek için kullanacağız.
20.1 Tanım ve İlk Değerler
Tanım 20.1 (Euler’in \(\phi\) Fonksiyonu) \(1 \leq n \in \mathbb{Z}\) olsun. \(1\) ile \(n\) arasındaki (uç değerler dâhil) tam sayılardan \(n\) ile aralarında asal olanların sayısına \(n\)’nin Euler \(\phi\) değeri denir ve \(\phi(n)\) ile gösterilir:
\[\phi(n) = \#\left\{ a \in \mathbb{Z} \ : \ 1 \leq a \leq n, \ \gcd(a, n) = 1 \right\}\]
Tanım 17.3 gereği \(a + n\mathbb{Z}\) sınıfının birim olması \(\gcd(a,n) = 1\) demekti ve Önerme 17.4 gereği bu özellik temsilci seçiminden bağımsızdı. \(1, 2, \dots, n\) sayıları modülo \(n\) bir tam kalan sistemi oluşturduğundan (her sınıftan tam bir temsilci), \(1 < n\) için
\[\phi(n) = \left| U\left( \mathbb{Z}_n \right) \right|\]
Yani \(\phi(n)\), modülo \(n\) tersi olan sınıfların sayısıdır.
Örnek 20.1 (İlk Değerler) Küçük \(n\) değerleri için doğrudan sayarak:
| \(n\) | \(n\) ile aralarında asal olanlar | \(\phi(n)\) |
|---|---|---|
| \(1\) | \(1\) | \(1\) |
| \(2\) | \(1\) | \(1\) |
| \(3\) | \(1, 2\) | \(2\) |
| \(4\) | \(1, 3\) | \(2\) |
| \(5\) | \(1, 2, 3, 4\) | \(4\) |
| \(6\) | \(1, 5\) | \(2\) |
| \(7\) | \(1, 2, 3, 4, 5, 6\) | \(6\) |
| \(8\) | \(1, 3, 5, 7\) | \(4\) |
| \(9\) | \(1, 2, 4, 5, 7, 8\) | \(6\) |
| \(10\) | \(1, 3, 7, 9\) | \(4\) |
| \(12\) | \(1, 5, 7, 11\) | \(4\) |
\(n = 1\) durumuna dikkat ediniz: \(\gcd(1,1) = 1\) olduğundan \(\phi(1) = 1\)’dir.
Elbette her \(n\) için tek tek saymak istemeyiz. Şimdi \(\phi(n)\) değerini \(n\)’nin asal çarpanlarından okuyacak bir formül kuracağız.
20.2 Asal ve Asal Kuvvetlerde
Önerme 20.1 (Asal Sayılarda) \(p\) bir asal sayı olmak üzere
\[\phi(p) = p - 1\]
Gerçekten de Önerme 9.1 gereği \(1 \leq a \leq p\) aralığındaki bir \(a\) için \(\gcd(a,p) \neq 1\) olması ancak \(p \mid a\) hâlinde olur; bu aralıkta \(p\) ile bölünen tek sayı \(a = p\)’dir. Geriye \(p - 1\) sayı kalır.
Teorem 20.1 (Asal Kuvvetlerde) \(p\) bir asal sayı ve \(1 \leq k\) bir tam sayı olmak üzere
\[\phi\left( p^{k} \right) = p^{k} - p^{k-1} = p^{k}\left( 1 - \frac{1}{p} \right)\]
İspat
Aralarında asal olanları saymak yerine, olmayanları sayıp çıkaracağız.
\(1 \leq a \leq p^{k}\) olsun. Önerme 9.1 gereği \(\gcd\left( a, p^{k} \right) \neq 1\) olması, \(a\) ile \(p^k\) sayılarının ortak bir asal böleninin olması demektir; \(p^k\)’nın tek asal böleni \(p\) olduğundan bu koşul
\[p \mid a\]
koşuluna denktir.
Şimdi \(1 \leq a \leq p^{k}\) aralığında \(p\)’nin katlarını sayalım. Bunlar
\[p, \quad 2p, \quad 3p, \quad \dots, \quad p^{k-1} \cdot p = p^{k}\]
sayılarıdır; yani \(a = mp\) biçiminde ve \(1 \leq m \leq p^{k-1}\) koşuluyla yazılırlar. Demek ki tam \(p^{k-1}\) tane böyle sayı vardır.
Geriye kalanlar \(p^k\) ile aralarında asaldır:
\[\phi\left( p^{k} \right) = p^{k} - p^{k-1}\]
Sağdaki ifadeyi \(p^k\) parantezine alırsak
\[p^{k} - p^{k-1} = p^{k}\left( 1 - \frac{1}{p} \right)\]
\(\blacksquare\)
Örnek 20.2 (Asal Kuvvet Örnekleri) \[\phi(8) = \phi\left( 2^{3} \right) = 2^{3} - 2^{2} = 8 - 4 = 4\]
\[\phi(9) = \phi\left( 3^{2} \right) = 9 - 3 = 6\]
\[\phi(125) = \phi\left( 5^{3} \right) = 125 - 25 = 100\]
\[\phi(49) = \phi\left( 7^{2} \right) = 49 - 7 = 42\]
\(k = 1\) alındığında \(\phi(p) = p - p^{0} = p - 1\) bulunur; Önerme 20.1 bunun özel hâlidir.
20.3 Çarpımsallık
Genel bir \(n\) için formül kurmanın anahtarı, \(\phi\) fonksiyonunun aralarında asal çarpanlar üzerinde “dağılmasıdır”.
Teorem 20.2 (\(\phi\) Çarpımsaldır) \(m, n\) pozitif tam sayıları aralarında asal olsun; yani \(\gcd(m,n) = 1\) olsun. Bu durumda
\[\phi(mn) = \phi(m)\,\phi(n)\]
İspat
\(m = 1\) veya \(n = 1\) ise \(\phi(1) = 1\) olduğundan eşitlik açıktır; \(1 < m, n\) varsayalım.
Fikir şudur: modülo \(mn\) birim olan sınıflar ile, modülo \(m\) birim olan sınıf – modülo \(n\) birim olan sınıf ikilileri arasında birebir eşleme kuracağız. Böyle bir eşleme varsa iki kümenin eleman sayısı eşittir; yani \(\phi(mn) = \phi(m)\phi(n)\) olur.
Eşleme. \(\gcd(a, mn) = 1\) koşulunu sağlayan bir \(a\) tam sayısına, modülo \(m\) ve modülo \(n\) kalanlarından oluşan
\[a \ \longmapsto \ \left( a \bmod m,\ a \bmod n \right)\]
ikilisini karşılık getirelim.
1. Eşleme anlamlıdır. \(\gcd(a, mn) = 1\) olsun. \(m \mid mn\) olduğundan \(a\) ile \(m\)’nin her ortak böleni \(a\) ile \(mn\)’nin de ortak bölenidir; dolayısıyla \(\gcd(a,m) = 1\)’dir. Aynı gerekçeyle \(\gcd(a,n) = 1\)’dir. Demek ki ikilinin her iki bileşeni de gerçekten birim sınıflardır.
2. Eşleme birebirdir. \(a\) ile \(b\) aynı ikiliye gitsin:
\[a \equiv b \pmod m \qquad \text{ve} \qquad a \equiv b \pmod n\]
O hâlde \(m \mid a - b\) ve \(n \mid a - b\)’dir. \(\gcd(m,n) = 1\) olduğundan Teorem 5.2 gereği
\[mn \ \mid \ a - b \qquad \text{yani} \qquad a \equiv b \pmod{mn}\]
Demek ki \(a\) ile \(b\) modülo \(mn\) aynı sınıftadır.
3. Eşleme örtendir. \(\gcd(b, m) = 1\) ve \(\gcd(c, n) = 1\) olan herhangi bir \((b, c)\) ikilisi verilsin. \(\gcd(m,n) = 1\) olduğundan Teorem 16.1 uygulanabilir:
\[x \equiv b \pmod m, \qquad x \equiv c \pmod n\]
sisteminin bir \(a\) çözümü vardır. Önerme 12.1 gereği
\[\gcd(a, m) = \gcd(b, m) = 1 \qquad \text{ve} \qquad \gcd(a, n) = \gcd(c, n) = 1\]
Teorem 5.3 gereği \(\gcd(a, mn) = 1\)’dir; yani \(a\) modülo \(mn\) bir birim sınıftır ve tam olarak \((b,c)\) ikilisine gitmektedir.
Sonuç. Eşleme birebir ve örten olduğundan iki kümenin eleman sayıları eşittir. Sol taraftaki kümenin eleman sayısı \(\phi(mn)\), sağ taraftaki ikililerin sayısı ise \(\phi(m) \cdot \phi(n)\)’dir:
\[\phi(mn) = \phi(m)\,\phi(n)\]
\(\blacksquare\)
\(\gcd(m,n) = 1\) koşulu atılamaz. Örneğin \(m = n = 2\) için
\[\phi(4) = 2 \qquad \text{ama} \qquad \phi(2)\,\phi(2) = 1 \cdot 1 = 1\]
Benzer biçimde \(\phi(6) = 2 = \phi(2)\phi(3)\) doğrudur (\(\gcd(2,3)=1\)), ama \(\phi(12) \neq \phi(2)\phi(6)\)’dır: \(\phi(12) = 4\) iken \(\phi(2)\phi(6) = 1 \cdot 2 = 2\)’dir.
20.4 Genel Formül
Teorem 20.3 (Euler \(\phi\) Fonksiyonunun Çarpım Formülü) \(1 < n\) tam sayısının kanonik gösterimi
\[n = p_1^{k_1} \, p_2^{k_2} \cdots p_r^{k_r}\]
olsun (bkz. Sonuç 10.1). Bu durumda
\[\phi(n) = \prod_{i=1}^{r} \left( p_i^{k_i} - p_i^{k_i - 1} \right) = n \prod_{i=1}^{r} \left( 1 - \frac{1}{p_i} \right)\]
İspat
\(p_1, \dots, p_r\) farklı asallar olduğundan \(p_i^{k_i}\) kuvvetleri ikişer ikişer aralarında asaldır (Sonuç 9.4). Teorem 20.2’ı tekrar tekrar uygulayalım:
\[\phi(n) = \phi\left( p_1^{k_1} \right) \phi\left( p_2^{k_2} \right) \cdots \phi\left( p_r^{k_r} \right)\]
Her çarpana Teorem 20.1’i uygulayalım:
\[\phi(n) = \prod_{i=1}^{r} \left( p_i^{k_i} - p_i^{k_i - 1} \right) = \prod_{i=1}^{r} p_i^{k_i} \left( 1 - \frac{1}{p_i} \right)\]
Çarpımdaki \(p_i^{k_i}\) terimlerini bir araya toplarsak çarpımları \(n\) olur:
\[\phi(n) = n \prod_{i=1}^{r} \left( 1 - \frac{1}{p_i} \right)\]
\(\blacksquare\)
İkinci biçim çok pratiktir: \(n\)’yi yaz, sonra \(n\)’yi bölen her farklı asal için bir \(\left(1 - \frac{1}{p}\right)\) çarpanı ekle. Üsler formülde hiç görünmez; yalnızca hangi asalların böldüğü önemlidir.
Örnek 20.3 (Çarpım Formülüyle Hesaplar) Aşağıdaki değerleri hesaplayınız: \(\phi(360)\), \(\phi(100)\), \(\phi(1001)\).
Çözüm
\(\phi(360)\). Kanonik gösterim \(360 = 2^{3} \cdot 3^{2} \cdot 5\)’tir. Farklı asallar \(2, 3, 5\)’tir:
\[\phi(360) = 360 \left( 1 - \frac{1}{2} \right)\left( 1 - \frac{1}{3} \right)\left( 1 - \frac{1}{5} \right) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96\]
(Çarpanlara ayırma biçimiyle: \(\phi(8)\phi(9)\phi(5) = 4 \cdot 6 \cdot 4 = 96\) ✓)
\(\phi(100)\). \(100 = 2^{2} \cdot 5^{2}\):
\[\phi(100) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40\]
\(\phi(1001)\). \(1001 = 7 \cdot 11 \cdot 13\)’tür (üç farklı asal, hepsinin üssü \(1\)):
\[\phi(1001) = 1001 \cdot \frac{6}{7} \cdot \frac{10}{11} \cdot \frac{12}{13} = 6 \cdot 10 \cdot 12 = 720\]
(Son adımda \(1001 = 7 \cdot 11 \cdot 13\) olduğundan paydalar sadeleşti.)
\(\blacksquare\)
20.5 Temel Özellikler
Teorem 20.4 (\(\phi(n)\) Ne Zaman Çifttir?) \(2 < n\) olan her tam sayı için \(\phi(n)\) çifttir.
İspat
İki durum vardır.
Durum 1: \(n\)’nin tek bir asal böleni var. Yani \(n = 2^{k}\) olsun. \(n > 2\) olduğundan \(k \geq 2\)’dir ve Teorem 20.1 gereği
\[\phi(n) = 2^{k} - 2^{k-1} = 2^{k-1}\]
\(k - 1 \geq 1\) olduğundan bu sayı çifttir.
Durum 2: \(n\)’nin bir tek asal böleni var. \(p\) tek bir asal ve \(p^{k} \, \| \, n\) olsun (yani \(p^k \mid n\) ve \(p^{k+1} \nmid n\)). \(n = p^{k} m\) ve \(\gcd\left( p^{k}, m \right) = 1\) yazalım. Teorem 20.2 gereği
\[\phi(n) = \phi\left( p^{k} \right) \phi(m) = p^{k-1}(p-1)\,\phi(m)\]
\(p\) tek asal olduğundan \(p - 1\) çifttir; dolayısıyla çarpım da çifttir.
Bu iki durum bütün olasılıkları kapsar: \(n > 2\) ise \(n\) ya yalnızca \(2\)’nin kuvvetidir ya da tek bir asal böleni vardır.
\(\blacksquare\)
Teorem 20.4, \(\phi(n) = c\) denklemlerini çözerken hemen kullanılır: \(c\) tek ve \(c > 1\) ise denklemin hiç çözümü yoktur. Örneğin \(\phi(n) = 3\), \(\phi(n) = 5\), \(\phi(n) = 7\) denklemleri çözümsüzdür.
\(\phi(n) = 1\) denkleminin çözümleri ise yalnızca \(n = 1\) ve \(n = 2\)’dir.
Önerme 20.2 (\(\phi(2n) = \phi(n)\) Ne Zaman Olur?) \(1 \leq n\) bir tam sayı olmak üzere
\[\phi(2n) = \phi(n) \iff n \text{ tektir}\]
Ayrıca \(n\) çift ise \(\phi(2n) = 2\,\phi(n)\)’dir.
İspat
(\(\Leftarrow\)) \(n\) tek olsun. Bu durumda \(\gcd(2, n) = 1\)’dir; Teorem 20.2 gereği
\[\phi(2n) = \phi(2)\,\phi(n) = 1 \cdot \phi(n) = \phi(n)\]
(\(\Rightarrow\)) \(n\) çift olsun. \(n = 2^{k} m\) yazalım; burada \(k \geq 1\) ve \(m\) tektir. O hâlde \(2n = 2^{k+1} m\)’dir. İki kez Teorem 20.2 ve Teorem 20.1 uygulayalım:
\[\phi(n) = \phi\left( 2^{k} \right)\phi(m) = 2^{k-1}\phi(m)\]
\[\phi(2n) = \phi\left( 2^{k+1} \right)\phi(m) = 2^{k}\phi(m)\]
Buradan
\[\phi(2n) = 2\,\phi(n) \neq \phi(n)\]
(Son adımda \(\phi(n) \neq 0\) olduğunu kullandık.) Demek ki \(n\) çiftse eşitlik bozulur; karşıt tersi alırsak eşitlik ancak \(n\) tekken sağlanır.
\(\blacksquare\)
Teorem 20.5 (Bölenlerde \(\phi\)) \(d, n\) pozitif tam sayıları ve \(d \mid n\) olsun. Bu durumda
\[\phi(d) \ \mid \ \phi(n)\]
İspat
\(d = 1\) ise \(\phi(1) = 1\) her sayıyı böler; \(1 < d\) varsayalım.
\(d \mid n\) olduğundan Önerme 11.1 gereği \(d\)’nin her asal böleni \(n\)’yi de böler ve Önerme 11.2 gereği üsler korunur. Yani
\[d = p_1^{b_1} \cdots p_s^{b_s}, \qquad n = p_1^{a_1} \cdots p_s^{a_s} \cdot q_1^{c_1} \cdots q_t^{c_t}\]
biçiminde yazılabilir; burada \(1 \leq b_i \leq a_i\)’dir ve \(q_j\) asalları \(d\)’yi bölmeyen (varsa) asallardır.
Teorem 20.3 gereği
\[\phi(d) = \prod_{i=1}^{s} p_i^{b_i - 1}\left( p_i - 1 \right), \qquad \phi(n) = \prod_{i=1}^{s} p_i^{a_i - 1}\left( p_i - 1 \right) \cdot \prod_{j=1}^{t} q_j^{c_j - 1}\left( q_j - 1 \right)\]
Şimdi \(\phi(d)\) çarpımındaki her terimi \(\phi(n)\) çarpımındaki karşılığıyla kıyaslayalım. \(b_i - 1 \leq a_i - 1\) olduğundan
\[p_i^{b_i - 1}\left( p_i - 1 \right) \ \Big| \ p_i^{a_i - 1}\left( p_i - 1 \right)\]
Bölen ilişkisi çarpım altında korunduğundan (Teorem 3.1) bu terimlerin çarpımı da bölünür:
\[\phi(d) = \prod_{i=1}^{s} p_i^{b_i - 1}\left( p_i - 1 \right) \ \Big| \ \prod_{i=1}^{s} p_i^{a_i - 1}\left( p_i - 1 \right)\]
Sağdaki çarpım da \(\phi(n)\)’yi böldüğünden geçişme ile \(\phi(d) \mid \phi(n)\) bulunur.
\(\blacksquare\)
Önerme 20.3 (\(\phi\left( n^{2} \right) = n,\phi(n)\)) Her \(1 \leq n\) tam sayısı için
\[\phi\left( n^{2} \right) = n \, \phi(n)\]
İspat
\(n = 1\) için her iki taraf da \(1\)’dir. \(1 < n\) olsun ve kanonik gösterimi
\[n = p_1^{k_1} \cdots p_r^{k_r}\]
olsun. \(n^{2}\) ile \(n\) aynı asalları içerir; yalnızca üsler ikiye katlanır. Teorem 20.3’ün ikinci biçimini kullanalım:
\[\phi\left( n^{2} \right) = n^{2} \prod_{i=1}^{r}\left( 1 - \frac{1}{p_i} \right)\]
\[\phi(n) = n \prod_{i=1}^{r}\left( 1 - \frac{1}{p_i} \right)\]
Birinci eşitliği \(n^2 = n \cdot n\) biçiminde ayırıp ikinciyi yerine koyalım:
\[\phi\left( n^{2} \right) = n \cdot \left( n \prod_{i=1}^{r}\left( 1 - \frac{1}{p_i} \right) \right) = n \, \phi(n)\]
\(\blacksquare\)
20.6 \(\phi(n) = c\) Denklemleri
Örnek 20.4 (\(\phi(n) = 6\) Denklemi) \(\phi(n) = 6\) eşitliğini sağlayan bütün \(n\) pozitif tam sayılarını bulunuz.
Çözüm
\(n\) bir çözüm olsun ve \(p^{k}\), \(n\)’yi bölen bir asal kuvvet olsun (yani \(p^k \mid n\) ve \(p^{k+1} \nmid n\)). Teorem 20.5 gereği
\[\phi\left( p^{k} \right) = p^{k-1}(p-1) \ \Big| \ \phi(n) = 6\]
1. Hangi asallar \(n\)’yi bölebilir? \(p\) tek asal ise \(p - 1\) sayısı \(6\)’yı bölmelidir:
\[p - 1 \in \{1, 2, 3, 6\} \implies p \in \{2, 3, 4, 7\}\]
Bunlardan asal olanlar \(3\) ve \(7\)’dir. \(p = 2\) de mümkündür. O hâlde \(n\)’nin asal bölenleri yalnızca \(2\), \(3\) ve \(7\) olabilir.
2. Hangi üsler mümkün?
- \(p = 2\): \(\phi\left( 2^{k} \right) = 2^{k-1} \mid 6\) olmalı; \(2^{k-1} \in \{1, 2\}\), yani \(k \leq 2\). Ama \(k = 2\) için \(\phi(4) = 2\)’dir ve geri kalan çarpanın \(3\) olması gerekir — Teorem 20.4 gereği \(1\)’den büyük tek bir \(\phi\) değeri olamaz. O hâlde \(k \leq 1\)’dir.
- \(p = 3\): \(\phi\left( 3^{k} \right) = 2 \cdot 3^{k-1} \mid 6\) olmalı; \(3^{k-1} \mid 3\), yani \(k \leq 2\)’dir.
- \(p = 7\): \(\phi\left( 7^{k} \right) = 6 \cdot 7^{k-1} \mid 6\) olmalı; \(7^{k-1} = 1\), yani \(k = 1\)’dir.
3. Olasılıkları tarayalım. \(n = 2^{a} 3^{b} 7^{c}\) ile \(a \leq 1\), \(b \leq 2\), \(c \leq 1\)’dir ve
\[\phi(n) = \phi\left( 2^{a} \right) \phi\left( 3^{b} \right) \phi\left( 7^{c} \right) = 6\]
\(\phi\left( 2^{a} \right) = 1\) (hem \(a=0\) hem \(a=1\) için) olduğundan koşul
\[\phi\left( 3^{b} \right)\phi\left( 7^{c} \right) = 6\]
hâline gelir. Değerler \(\phi(3^0) = 1\), \(\phi(3) = 2\), \(\phi(9) = 6\) ve \(\phi(7^0) = 1\), \(\phi(7) = 6\)’dır. Çarpımı \(6\) yapan ikililer:
- \(\phi(9) \cdot \phi(7^{0}) = 6 \cdot 1\): \(b = 2\), \(c = 0\)
- \(\phi(3^{0}) \cdot \phi(7) = 1 \cdot 6\): \(b = 0\), \(c = 1\)
(\(\phi(3)\phi(7) = 2 \cdot 6 = 12 \neq 6\)’dır.)
Her ikisinde \(a \in \{0, 1\}\) serbesttir. Dört çözüm bulunur:
\[n \in \{ 9,\ 18,\ 7,\ 14 \}\]
(Sağlama: \(\phi(9) = 6\), \(\phi(18) = \phi(2)\phi(9) = 6\), \(\phi(7) = 6\), \(\phi(14) = \phi(2)\phi(7) = 6\) ✓)
\(\blacksquare\)
Örnek 20.5 (\(\phi(n) = 14\) Denklemi) \(\phi(n) = 14\) eşitliğini sağlayan bir \(n\) tam sayısının bulunmadığını gösteriniz.
Çözüm
\(\phi(n) = 14\) olduğunu varsayalım. \(14 = 2 \cdot 7\) olduğundan \(7 \mid \phi(n)\)’dir.
Teorem 20.3 gereği \(\phi(n)\), \(n\)’yi bölen asal kuvvetlerin \(\phi\) değerlerinin çarpımıdır. \(7\) asal olduğundan Sonuç 9.2 gereği bu çarpanlardan en az birini bölmelidir: bir \(p^{k} \mid n\) asal kuvveti için
\[7 \ \Big| \ \phi\left( p^{k} \right) = p^{k-1}(p-1)\]
\(7\) asal olduğundan Teorem 9.1 gereği iki durum vardır.
Durum 1: \(7 \mid p^{k-1}\). Bu ancak \(p = 7\) ve \(k \geq 2\) ise olur. O hâlde \(49 \mid n\)’dir ve Teorem 20.5 gereği
\[\phi(49) = 42 \ \Big| \ \phi(n) = 14\]
Ama \(42 > 14 > 0\) olduğundan \(42\) sayısı \(14\)’ü bölemez — çelişki.
Durum 2: \(7 \mid p - 1\). Bu durumda \(p \equiv 1 \pmod 7\)’dir. Bu koşulu sağlayan asalların en küçüğü \(29\)’dur (\(8, 15, 22\) asal değildir); yani \(p \geq 29\)’dur. Teorem 20.5 gereği
\[\phi(p) = p - 1 \ \Big| \ \phi(n) = 14\]
Ama \(p - 1 \geq 28 > 14 > 0\) olduğundan bu imkânsızdır — çelişki.
Her iki durum da çelişkiye vardığından \(\phi(n) = 14\) eşitliğini sağlayan bir \(n\) yoktur.
\(\blacksquare\)
20.7 Çalışma Problemleri
Alıştırma 20.1 (\(\phi\) Değerlerini Hesaplama) Aşağıdaki değerleri hesaplayınız.
a) \(\phi(720)\) b) \(\phi(1024)\) c) \(\phi(2431)\) d) \(\phi\left( 5^{4} \cdot 11 \right)\)
İpucu (c): \(2431 = 11 \cdot 13 \cdot 17\)’dir.
Alıştırma 20.2 (\(\phi(n) = c\) Denklemleri) Aşağıdaki denklemlerin bütün çözümlerini bulunuz; çözümü olmayanların nedenini açıklayınız.
a) \(\phi(n) = 4\) b) \(\phi(n) = 8\) c) \(\phi(n) = 10\) d) \(\phi(n) = 12\)
Alıştırma 20.3 (\(\phi\) Fonksiyonunun Özellikleri) Aşağıdakileri ispatlayınız.
a) \(n\) tek ise \(\phi(4n) = 2\,\phi(n)\)’dir.
b) \(\phi(n) = \dfrac{n}{2}\) olması için gerek ve yeter koşul, \(n\)’nin bir \(2\) kuvveti olmasıdır.
c) \(p\) asal ve \(p \mid n\) ise \(\phi(pn) = p\,\phi(n)\)’dir.
d) \(p\) asal ve \(p \nmid n\) ise \(\phi(pn) = (p-1)\,\phi(n)\)’dir.
Alıştırma 20.4 (Bölenler Üzerinden Toplam) \(n\) pozitif bir tam sayı olmak üzere
\[\sum_{d \mid n} \phi(d) = n\]
olduğunu gösteriniz. (Toplam, \(n\)’nin bütün pozitif bölenleri üzerinden alınmaktadır.)
a) Önce \(n = 12\) için doğrudan hesaplayarak doğrulayınız.
b) \(n = p^{k}\) için ispatlayınız.
c) Teorem 20.2’ı kullanarak genel durumu elde ediniz.
İpucu (b): \(p^k\)’nın bölenleri \(1, p, \dots, p^{k}\)’dır ve toplam teleskopiktir.