Euler Totient Fonksiyonu

Core idea

Overview

Euler Totient Fonksiyonu, φ(n) ile gösterilir, n'ye kadar olan pozitif tam sayıların n ile aralarında asal olan sayısını sayar. Modüler aritmetik ve döngüsel grupların özelliklerini incelemek için kullanılan sayı teorisindeki temel bir çarpımsal fonksiyondur.

When to use: Bu fonksiyonu, n modülündeki çarpımsal grubun mertebesini hesaplarken kullanın. Euler Teoremi'ni modüler üs almada veya n mertebeli bir döngüsel gruptaki üreteç sayısını belirlerken uygulamak için birincil araçtır.

Why it matters: Bu denklem, modern dijital iletişimi güvence altına alan RSA şifreleme algoritmasının matematiksel temelini oluşturur. İki büyük asalın çarpımının totient'ini belirleyerek özel anahtarların hesaplanmasına olanak tanır.

Symbols

Variables

$ϕ$ (n) = Totient Value, n = Input Integer

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

Euler Totient Fonksiyonunun Türetilmesi/Anlaşılması

Bu türetme, verilen bir n tam sayısına kadar n ile aralarında asal olan pozitif tam sayıları sayan Euler'in totient fonksiyonunun, n'nin asal çarpanlara ayrılması kullanılarak nasıl ifade edilebileceğini gösterir.

n, a positive integer.

1

Tanım ve Çarpımsal Özellik:

Euler'in totient fonksiyonunu tanımlayarak ve bileşik sayılar için hesaplamayı asal kuvvet çarpanlarına yönelik hesaplamalara ayırmamızı sağlayan kritik çarpımsal özelliğini belirterek başlarız.

Euler’s totient function ϕ (n) counts the positive integers up to n that are relatively prime to n . It is a multiplicative function, meaning if g cd (m, n) = 1, then ϕ (mn) = ϕ (m) ϕ (n) .

2

Bir Asal Kuvvet için Durum:

Bir asal kuvvet $p^{k}$ için, onunla aralarında asal olmayan tek sayılar $p$ 'nin katlarıdır. Bunları toplam $p^{k}$ sayıdan çıkarmak $ϕ (p^{k})$ formülünü verir.

Consider n = p^{k} for a prime p and integer k \geq 1. The integers not relatively prime to p^{k} are multiples of p : p, 2 p, \dots, p^{k - 1} p . There are p^{k - 1} such multiples up to p^{k} . ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p}) .

3

Asal Çarpanlara Ayırmayı Kullanan Genel Durum:

Aritmetiğin temel teoremi kullanılarak, herhangi bir pozitif tam sayı $n$ asal kuvvetlerin çarpımı olarak benzersiz biçimde ifade edilebilir. $ϕ (n)$ fonksiyonunun çarpımsal özelliği, asal kuvvet formülünü her çarpana uygulamamıza olanak tanır.

Let the prime factorization of n be n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}} . Due to the multiplicative property, we can write: ϕ (n) = ϕ (p_{1}^{k_{1}}) ϕ (p_{2}^{k_{2}}) \dots ϕ (p_{r}^{k_{r}}) .

4

Yerine Koyma ve Sadeleştirme:

Her asal kuvvet çarpanı için $ϕ (p^{k})$ adına türetilen formülü yerine koyup terimleri yeniden düzenleyerek, Euler'in totient fonksiyonu için çarpım formülüne ulaşırız; burada çarpım, $n$ 'nin tüm farklı asal çarpanları $p$ üzerinden alınır.

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Result

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Source: Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Why it behaves this way

Intuition

1'den n'ye kadar tüm sayıların olduğu bir elek hayal edin ve ardından n'nin her bir farklı asal çarpanının tüm katlarını sistematik olarak filtreleyerek, n ile hiçbir ortak çarpanı paylaşmayan sayıları geride bırakın.

Term

n'den küçük veya eşit ve n ile aralarında asal olan pozitif tamsayıların sayısı.

n'ye kadar olan sayıların 'aralarında asal yoğunluğunu' veya 'bağıl asal olma durumunu' temsil eder. Daha yüksek bir

ϕ

(n), daha fazla sayının n ile ortak asal çarpan paylaşmadığı anlamına gelir.

Term

Totient'in hesaplandığı pozitif tamsayı.

Göz önünde bulundurulan tamsayı aralığının üst sınırı; 1'den n'ye kadar olan sayıların 'evreni'.

Term

n'nin farklı bir asal çarpanı.

Bunlar, n'nin temel asal yapı taşlarıdır; eğer paylaşılırlarsa, diğer sayıların n ile aralarında asal olmasını engellerler.

Term

n'ye kadar olan ve p ile bölünmeyen sayıların oranı.

Bu çarpan, p asal çarpanıyla n'yi paylaşan sayıları 'çıkarır', etkili bir şekilde aralarında asal olmayan sayıları p'ye göre filtreler.

Signs and relationships

(1 - \frac{1}{p}): Çıkarma '1 -...' dışlama ilkesini temsil eder. Toplam kümeden (1 ile temsil edilen), bir asal çarpan p'ye (bu 1/p'dir) bölünebilen sayıların oranı

Free study cues

Insight

Canonical usage

Euler's Totient Function operates on and returns integer counts, which are inherently dimensionless quantities in a physical sense.

Dimension note

The function calculates a count of integers, making both its input and output inherently dimensionless quantities. It does not involve physical units or dimensions.

One free problem

Practice Problem

Bir analist, 1 ile 12'den başka ortak çarpanı olmayan 12'den küçük tam sayıların sayısını belirlemek istiyor. Bu değer için totient fonksiyonunun sonucunu hesaplayın.

Hint: 12'nin asal çarpanları 2 ve 3'tür.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1) bağlamında, which ölçümleri yorumlanabilir bir değere dönüştürmek için kullanılır. Sonuç önemlidir çünkü hesaplamayı modeldeki şekle, hıza, olasılığa veya kısıtlamaya bağlamaya yardımcı olur.

Study smarter

Tips

Eğer n asal ise, φ(n) = n - 1.
Çarpım formülünde sadece benzersiz asal çarpanları belirleyin; çarpanlar çarpanlarına ayırmada birden fazla kez görünse bile tekrarlamayın.
pᵏ asal kuvveti için değer pᵏ - pᵏ⁻¹ olur.
Fonksiyon çarpımsaldır: Eğer m ve n aralarında asal ise φ(m ×n) = φ(m) ×φ(n).

Avoid these traps

Common Mistakes

Çarpım formülünde tüm bölenleri dahil etmek yerine sadece benzersiz asal çarpanları dahil etmek.
phi(n) ile bölen sayısı $τ$ (n)'yi karıştırmak.

Keep going

Related Formulas

Common questions

Frequently Asked Questions

Bu türetme, verilen bir n tam sayısına kadar n ile aralarında asal olan pozitif tam sayıları sayan Euler'in totient fonksiyonunun, n'nin asal çarpanlara ayrılması kullanılarak nasıl ifade edilebileceğini gösterir.

Bu fonksiyonu, n modülündeki çarpımsal grubun mertebesini hesaplarken kullanın. Euler Teoremi'ni modüler üs almada veya n mertebeli bir döngüsel gruptaki üreteç sayısını belirlerken uygulamak için birincil araçtır.

Bu denklem, modern dijital iletişimi güvence altına alan RSA şifreleme algoritmasının matematiksel temelini oluşturur. İki büyük asalın çarpımının totient'ini belirleyerek özel anahtarların hesaplanmasına olanak tanır.

Çarpım formülünde tüm bölenleri dahil etmek yerine sadece benzersiz asal çarpanları dahil etmek. phi(n) ile bölen sayısı \tau(n)'yi karıştırmak.

RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1) bağlamında, which ölçümleri yorumlanabilir bir değere dönüştürmek için kullanılır. Sonuç önemlidir çünkü hesaplamayı modeldeki şekle, hıza, olasılığa veya kısıtlamaya bağlamaya yardımcı olur.

Eğer n asal ise, φ(n) = n - 1. Çarpım formülünde sadece benzersiz asal çarpanları belirleyin; çarpanlar çarpanlarına ayırmada birden fazla kez görünse bile tekrarlamayın. pᵏ asal kuvveti için değer pᵏ - pᵏ⁻¹ olur. Fonksiyon çarpımsaldır: Eğer m ve n aralarında asal ise φ(m ×n) = φ(m) ×φ(n).

References

Sources

Wikipedia: Euler's totient function
Rosen, Kenneth H. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2011.
A Friendly Introduction to Number Theory by Joseph H. Silverman
Elementary Number Theory and Its Applications by Kenneth H. Rosen
Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Overview

Variables

Derivation

Tanım ve Çarpımsal Özellik:

Bir Asal Kuvvet için Durum:

Asal Çarpanlara Ayırmayı Kullanan Genel Durum:

Yerine Koyma ve Sadeleştirme:

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources