φ(n) fonksiyonun ilk 1000 değeri Totient (kısaca φ, n ) sayılar teorisinde , bir tam sayının o sayıdan daha küçük ve o sayı ile aralarında asal olan sayma sayı sayısını belirten fonksiyondur. Genellikle Euler Totient ya da Euler'in Totienti olarak adlandırılan Totient, İsviçreli matematikçi Leonhard Euler tarafından yaratılmıştır. Totient fonksiyonu, Yunan harflerinden φ {\displaystyle \varphi } ile simgelendiği için Fi fonksiyonu olarak da anılabilir.
Örneğin, φ ( 10 ) = 4 {\displaystyle \varphi (10)=4} ; zira 10 ile dört sayma sayısı, hem 10'dan küçüktür, hem de 10 ile arasında asaldır: 1, 3, 7 ve 9.
Euler fonksiyonu, Euler Fermat teoreminde de kullanılır. Şöyle ki:
a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} , a ile n aralarında asal ise. Dolayısıyla, a φ ( n ) − 1 {\displaystyle a^{\varphi (n)}-1} , n' in bir tam katıdır.
Örneğin, a 4 − 1 {\displaystyle a^{4}-1} , a = 1 , 3 , 7 , 9 {\displaystyle a=1,3,7,9} için sırasıyla 0 , 80 , 2400 , 6560 {\displaystyle 0,80,2400,6560} , 10' un bir tam katıdır.
Totient fonksiyonu ayrıca RSA kriptografi sisteminde de kilit rol oynamaktadır.
Fonksiyonun yukarıda verilen tanımına göre φ ( 1 ) = 1 {\displaystyle \varphi (1)=1} ve eğer p bir asal sayıysa φ ( p k ) = ( p − 1 ) p k − 1 {\displaystyle \varphi (p^{k})=(p-1)p^{k-1}} . Bunun yanında, totient fonksiyonunun çarpım özelliği de vardır: m ve n aralarında asallarsa φ ( m n ) = φ ( m ) φ ( n ) {\displaystyle \varphi (mn)=\varphi (m)\varphi (n)} . (Bu yargının ispatının anahattı: A ,B ve C kümeleri sırasıyla m ,n ve mn ile aralarında asal ve modlarının kalan kümesi olsun. Bu durumda, Çinlilerin kalan teoreminden yararlanılırsa göürülür ki, AxB ve C arasında eşleme olur.) Yani, φ {\displaystyle \varphi } fonksiyonunun değeri aritmetiğin temel teoremi kullanılarak hesaplanabilir. Öyleyse,
n = p 1 k 1 ⋯ p r k r {\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}
için
φ ( n ) = ( p 1 − 1 ) p 1 k 1 − 1 ⋯ ( p r − 1 ) p r k r − 1 . {\displaystyle \varphi (n)=(p_{1}-1)p_{1}^{k_{1}-1}\cdots (p_{r}-1)p_{r}^{k_{r}-1}.} Yukarıdaki formül bir Euler Çarpımı'dır ve genellikle
φ ( n ) = n ⋅ ∏ p | n ( 1 − 1 p ) {\displaystyle \varphi (n)=n\cdot \prod _{p|n}\left(1-{\frac {1}{p}}\right)}
şeklinde yazılır.
φ ( 36 ) = φ ( 3 2 2 2 ) = 36 ( 1 − 1 3 ) ( 1 − 1 2 ) = 36 ⋅ 2 3 ⋅ 1 2 = 12 {\displaystyle \varphi (36)=\varphi \left(3^{2}2^{2}\right)=36\left(1-{\frac {1}{3}}\right)\left(1-{\frac {1}{2}}\right)=36\cdot {\frac {2}{3}}\cdot {\frac {1}{2}}=12}
Yani yazıyla ifade edersek, 36 'nın asal çarpanları 2 ve 3 'tür. 36' nın yarısı olan 18 tane sayı 2 ile bölünür, dolayısıyla 36 ile aralarında asal değildir. Kalan 18 sayının da 3'te biri 3 ile bölünür. Bu durumda 36 sayı içerisinde 36 ile aralarında asal olan sadece 12 sayı kalır.
İlk birkaç değer aşağıdaki tabloda ve grafikte gösterilmiştir:
İlk 100 değerin grafiğe dökümü φ ( n ) {\displaystyle \varphi (n)} +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 0+ 1 1 2 2 4 2 6 4 6 10+ 4 10 4 12 6 8 8 16 6 18 20+ 8 12 10 22 8 20 12 18 12 28 30+ 8 30 16 20 16 24 12 36 18 24 40+ 16 40 12 42 20 24 22 46 16 42 50+ 20 32 24 52 18 40 24 36 28 58 60+ 16 60 30 36 32 48 20 66 32 44 70+ 24 70 24 72 36 40 36 60 24 78 80+ 32 54 40 82 24 64 42 56 40 88 90+ 24 72 44 60 46 72 32 96 42 60
φ ( n ) {\displaystyle \varphi (n)} sayısı aynı zamanda dairesel grup olan C n nin olası generatörlerine eşittir. Bu nedenleC n in her elemanı, bir dairesel altgrup oluşturur. C n nin algrupları C d formundadır, eğer d böler n (d | n şeklinde yazılır). Böylece
∑ d ∣ n φ ( d ) = n {\displaystyle \sum _{d\mid n}\varphi (d)=n} Buradaki toplam n nin tüm d pozitif bölenlerine kadar genişler.
Şimdi Möbius formülünü, bu toplamı değiştirmek ve φ ( n ) {\displaystyle \varphi (n)} için bir formül daha elde etmek için kullanabiliriz:
φ ( n ) = ∑ d ∣ n d ⋅ μ ( n d ) {\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right)} Burada, μ pozitif tam sayılarda tanımlanan Möbius fonksiyonudur.
Euler'in teoremine göre, eğer a ile n aralarında asallarsa, yani ebob (a , n ) = 1,
a φ ( n ) ≡ 1 mod n . {\displaystyle a^{\varphi (n)}\equiv 1\mod n.\,} Bu durum Lagrange'ın teoremini ve a nın Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } nin mod n'e göre tam sayı grubuna ait olmasını takip eder. (Ancak ve ancak a ile n aralarında asallarsa).
Burada gösterilen iki fonksiyon da
∑ d | n φ ( d ) = n . {\displaystyle \sum _{d|n}\varphi (d)=n.} nın sonucudur.
φ {\displaystyle \varphi } (n )yi içeren bir Dirichlet Serisi
∑ n = 1 ∞ φ ( n ) n s = ζ ( s − 1 ) ζ ( s ) {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}} öyle ki ζ(s ) Rienmann Zeta Fonksiyonudur. Bunun ispatı aşağıda gösterildiği gibidir:
ζ ( s ) ∑ f = 1 ∞ φ ( f ) f s = ( ∑ g = 1 ∞ 1 g s ) ( ∑ f = 1 ∞ φ ( f ) f s ) {\displaystyle \zeta (s)\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}=\left(\sum _{g=1}^{\infty }{\frac {1}{g^{s}}}\right)\left(\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}\right)} ( ∑ g = 1 ∞ 1 g s ) ( ∑ f = 1 ∞ φ ( f ) f s ) = ∑ h = 1 ∞ ( ∑ f g = h 1 ⋅ φ ( g ) ) 1 h s {\displaystyle \left(\sum _{g=1}^{\infty }{\frac {1}{g^{s}}}\right)\left(\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}\right)=\sum _{h=1}^{\infty }\left(\sum _{fg=h}1\cdot \varphi (g)\right){\frac {1}{h^{s}}}} ∑ h = 1 ∞ ( ∑ f g = h φ ( g ) ) 1 h s = ∑ h = 1 ∞ ( ∑ d | h φ ( d ) ) 1 h s {\displaystyle \sum _{h=1}^{\infty }\left(\sum _{fg=h}\varphi (g)\right){\frac {1}{h^{s}}}=\sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}} ∑ h = 1 ∞ ( ∑ d | h φ ( d ) ) 1 h s = {\displaystyle \sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}=} ∑ h = 1 ∞ h h s {\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}} ∑ h = 1 ∞ h h s = ζ ( s − 1 ) {\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}=\zeta (s-1)} Lambert serisi fonksiyonu,
∑ n = 1 ∞ φ ( n ) q n 1 − q n = q ( 1 − q ) 2 {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}} öyle ki |q |<1 için ıraksar.
Bu durumun nedeni
∑ n = 1 ∞ φ ( n ) q n 1 − q n = ∑ n = 1 ∞ φ ( n ) ∑ r ≥ 1 q r n {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}=\sum _{n=1}^{\infty }\varphi (n)\sum _{r\geq 1}q^{rn}} yani
∑ k ≥ 1 q k ∑ n | k φ ( n ) = ∑ k ≥ 1 k q k = q ( 1 − q ) 2 . {\displaystyle \sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 1}kq^{k}={\frac {q}{(1-q)^{2}}}.} φ ( n ) {\displaystyle \varphi (n)} nin fonksiyon olarak büyümesi ilginç bir sorudur; çünkü küçükn ler için φ ( n ) {\displaystyle \varphi (n)} in n den küçük olacağı düşüncesi tam olarak doğru değildir. Asimptotik olarak,
n 1 − ε < φ ( n ) < n {\displaystyle \,n^{1-\varepsilon }<\varphi (n)<n} (herhangi bir ε > 0 ve n > N (ε) için)
Aslında
φ ( n ) / n , {\displaystyle \,\varphi (n)/n,} ele alınırsa,
1 − p − 1 {\displaystyle 1-p^{-1}\,} yazılabilir. p|n i sağlayan p asal sayıları için)
Asal sayı teoremi'nden εnin yerine aşağıdakinin yazılabileceği gösterilebilir:
C log log n / log n . {\displaystyle C\,\log \log n/\log n.} φ {\displaystyle \varphi } de ortalama olarak n e yakındır.
1 n 2 ∑ k = 1 n φ ( k ) = 3 π 2 + O ( log n n ) {\displaystyle {\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)} Yani
{ 1 , 2 , … , n } {\displaystyle \{1,2,\ldots ,n\}} ndan rastgele seçilen iki pozitif sayının aralarında asal olma olasılığı n sonsuza yaklaşırken 6 π 2 {\displaystyle {\frac {6}{\pi ^{2}}}} a yaklaşır. Bununla ilgili bir sonuç da,
1 n ∑ k = 1 n φ ( k ) k = 6 π 2 + O ( log n n ) {\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {6}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)} ile gösterilir; çünkü 6 π 2 = 1 ζ ( 2 ) {\displaystyle {\frac {6}{\pi ^{2}}}={\frac {1}{\zeta (2)}}} , formül bu şekilde de ifade edilebilir.
1 n ∑ k = 1 n φ ( k ) k = 1 ζ ( 2 ) + O ( log n n ) {\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {1}{\zeta (2)}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)} Euler Totient Fonksiyonu'nu İçeren Diğer Formüller [ değiştir | kaynağı değiştir ] φ ( n m ) = n m − 1 φ ( n ) for m ≥ 1 {\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n){\text{ for }}m\geq 1} herhangi a , n > 1 , öyle vardır ki l ≥ n öyledir ki l | φ ( a n − 1 ) {\displaystyle {\text{herhangi }}a,n>1{\text{, öyle vardır ki}}l\geq n{\text{ öyledir ki }}l|\varphi (a^{n}-1)} Herhangi a > 1 ve n > 6 öyle vardır ki 4 ⧸ | n öyledir ki l ≥ 2 n öyledir ki l | φ ( a n − 1 ) {\displaystyle {\text{Herhangi }}a>1{\text{ ve }}n>6{\text{ öyle vardır ki }}4\not |n{\text{ öyledir ki }}l\geq 2n{\text{ öyledir ki }}l|\varphi (a^{n}-1)} ∑ d ∣ n μ 2 ( d ) φ ( d ) = n φ ( n ) {\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}} ∑ 1 ≤ k ≤ n ( k , n ) = 1 k = 1 2 n φ ( n ) for n > 1 {\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ for }}n>1} ∑ k = 1 n φ ( k ) = 1 2 ( 1 + ∑ k = 1 n μ ( k ) ⌊ n k ⌋ 2 ) {\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)} ∑ k = 1 n φ ( k ) k = ∑ k = 1 n μ ( k ) k ⌊ n k ⌋ {\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor } ∑ k = 1 n k φ ( k ) = O ( n ) {\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\mathcal {O}}(n)} ∑ k = 1 n 1 φ ( k ) = O ( log ( n ) ) {\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\mathcal {O}}(\log(n))} ∑ 1 ≤ k ≤ n ( k , m ) = 1 1 = n φ ( m ) m + O ( 2 ω ( m ) ) , {\displaystyle \sum _{1\leq k\leq n \atop (k,m)=1}1=n{\frac {\varphi (m)}{m}}+{\mathcal {O}}\left(2^{\omega (m)}\right),} Burada m > 1 bir pozitif tam sayıdır ve ω(m ) m in asal sayı çarpanlarını ifade eder. (Bu formül n den küçük ve m ile aralarında asal olan doğal sayıların sayısını gösterir.)
φ {\displaystyle \varphi } fonksiyonunu içeren bazı eşitsizlikler:
φ ( n ) > n e γ log log n + 3 log log n {\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}} n > 2 için, &gamma Euler sabiti iken, φ ( n ) ≥ n 2 {\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}} n için > 0, ve
φ ( n ) ≥ n for n > 6. {\displaystyle \varphi (n)\geq {\sqrt {n}}{\text{ for }}n>6.} n asal sayısı için, açıkça φ ( n ) = n − 1 {\displaystyle \varphi (n)=n-1} .
n birleşik sayısı için
φ ( n ) ≤ n − n {\displaystyle \varphi (n)\leq n-{\sqrt {n}}} . Rastgele büyüklükteki n için, bu sınırlar halen geliştirilememeiştir ya da daha kesin olmak gerekirse:
lim inf φ ( n ) n = 0 ve lim sup φ ( n ) n = 1. {\displaystyle \liminf {\frac {\varphi (n)}{n}}=0{\mbox{ ve }}\limsup {\frac {\varphi (n)}{n}}=1.} φ {\displaystyle \varphi } fonksiyonu ile σ {\displaystyle \sigma } fonksiyonunu birleştiren birkaç eşitsizlik:
6 n 2 π 2 < φ ( n ) σ ( n ) < n 2 için n > 1. {\displaystyle {\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)<n^{2}{\mbox{ için }}n>1.} Ford, her k ≥ 2 tam sayısı için φ(x ) = m eşitliğinin tam olarak k sağlayanı bulunması durumunu sağlayan bir m sayısının bulunduğunu ispatladı. Ne yazık ki, k = 1 için herhangi bir m bulunamamıştır, Carmichal'ın Totient Fonksiyonu Konjektürü'ne göre, bu durumda böyle bir m in varolmadığına inanılır.