Mathematicsसंख्या सिद्धांत (Number Theory)University

OCRAPOntarioNSWCBSEGCE O-LevelMoECAPS

यूलर का टोटिएंट फ़ंक्शन (Euler's Totient Function)

n तक की उन धनात्मक पूर्णांकों की संख्या गिनता है जो n के सह-अभाज्य (coprime) हैं।

Understand the formulaSee the free derivationOpen the full walkthrough

ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p})

Open Full Walkthrough Try Calculator

This public page keeps the free explanation visible and leaves premium worked solving, advanced walkthroughs, and saved study tools inside the app.

Core idea

Overview

यूलर का टोटिएंट फ़ंक्शन, जिसे φ(n) द्वारा दर्शाया जाता है, n तक की उन धनात्मक पूर्णांकों की संख्या गिनता है जो n के सापेक्ष अभाज्य (relatively prime) हैं। यह संख्या सिद्धांत में एक मौलिक गुणक फ़ंक्शन (multiplicative function) है जिसका उपयोग मॉड्यूलर अंकगणित और चक्रीय समूहों (cyclic groups) के गुणों का पता लगाने के लिए किया जाता है।

When to use: n मॉड्यूलो पूर्णांकों के गुणक समूह (multiplicative group of integers modulo n) के क्रम (order) की गणना करते समय इस फ़ंक्शन का उपयोग करें। यह मॉड्यूलर घातांक (modular exponentiation) में यूलर के प्रमेय को लागू करने या n क्रम के चक्रीय समूह में जनरेटर (generators) की संख्या निर्धारित करने के लिए प्राथमिक उपकरण है।

Why it matters: यह समीकरण RSA एन्क्रिप्शन एल्गोरिथम का गणितीय आधार है, जो आधुनिक डिजिटल संचार को सुरक्षित करता है। यह दो बड़ी अभाज्य संख्याओं के गुणनफल के टोटिएंट (totient) का निर्धारण करके निजी कुंजियों (private keys) की गणना की अनुमति देता है।

Symbols

Variables

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

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

Derivation/Understanding of Euler's Totient Function

This derivation shows how Euler's totient function, which counts the positive integers up to a given integer n that are relatively prime to n, can be expressed using the prime factorization of n.

Definition and Multiplicative Property:

We begin by defining Euler's totient function and stating its crucial multiplicative property, which allows us to break down the calculation for composite numbers into calculations for their prime power factors.

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

Case for a Prime Power:

For a prime power $p^{k}$ , the only numbers not relatively prime to it are its multiples of $p$ . Subtracting these from the total $p^{k}$ numbers gives the formula for $ϕ (p^{k})$ .

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

General Case using Prime Factorization:

Using the fundamental theorem of arithmetic, any positive integer $n$ can be uniquely expressed as a product of prime powers. The multiplicative property of $ϕ (n)$ allows us to apply the prime power formula to each factor.

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

Substituting and Simplifying:

By substituting the derived formula for $ϕ (p^{k})$ for each prime power factor and rearranging terms, we arrive at the product formula for Euler's totient function, where the product is taken over all distinct prime factors $p$ of $n$ .

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 से n तक की सभी संख्याओं से शुरू करते हैं, और फिर n के प्रत्येक विशिष्ट अभाज्य गुणनखंड के सभी गुणजों को व्यवस्थित रूप से फ़िल्टर करते हैं, केवल उन संख्याओं को छोड़ देते हैं जो n के साथ कोई सामान्य गुणनखंड साझा नहीं करते हैं।

Term

n से कम या उसके बराबर धनात्मक पूर्णांकों की गिनती जो n के साथ सह-अभाज्य हैं।

n तक की संख्याओं के 'सह-अभाज्य घनत्व' या 'सापेक्ष अभाज्यता' का प्रतिनिधित्व करता है। उच्च

ϕ

(n) का मतलब है कि अधिक संख्याएँ n के साथ कोई अभाज्य गुणनखंड साझा नहीं करती हैं।

Term

वह धनात्मक पूर्णांक जिसके लिए टोटिएंट की गणना की जा रही है।

विचार किए जा रहे पूर्णांकों की सीमा की ऊपरी सीमा; 1 से n तक की संख्याओं का 'ब्रह्मांड'।

Term

n का एक विशिष्ट अभाज्य गुणनखंड।

ये n के मौलिक अभाज्य निर्माण खंड हैं, जो साझा किए जाने पर, अन्य संख्याओं को n के साथ सह-अभाज्य होने से रोकते हैं।

Term

n तक की उन संख्याओं का अनुपात जो p से विभाज्य नहीं हैं।

यह कारक उन संख्याओं को 'हटा देता है' जो n के साथ अभाज्य गुणनखंड p साझा करते हैं, प्रभावी रूप से p के आधार पर गैर-सह-अभाज्य संख्याओं को फ़िल्टर करते हैं।

Signs and relationships

(1 - \frac{1}{p}): घटाव '1 - ...' बहिष्करण के सिद्धांत का प्रतिनिधित्व करता है। कुल सेट (1 द्वारा दर्शाया गया) से, अभाज्य गुणनखंड p से विभाज्य संख्याओं का अनुपात (जो 1/p है)

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

एक विश्लेषक को 12 से कम उन पूर्णांकों की संख्या निर्धारित करने की आवश्यकता है जो 1 के अलावा 12 के साथ कोई सामान्य गुणनखंड साझा नहीं करते हैं। इस मान के लिए टोटिएंट फ़ंक्शन के परिणाम की गणना करें।

Hint: 12 के अभाज्य गुणनखंड 2 और 3 हैं।

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), which का उपयोग गणना के लिए किया जाता है the decryption key, Euler's Totient Function का उपयोग गणना के लिए किया जाता है Totient Value from Input Integer. परिणाम महत्वपूर्ण है क्योंकि यह गणना को मॉडल में आकार, दर, संभावना या बाधा से जोड़ने में मदद करता है।

Study smarter

Tips

यदि n अभाज्य है, तो φ(n) = n - 1।
केवल अद्वितीय अभाज्य गुणनखंडों (unique prime factors) की पहचान करें; यदि वे गुणनखंडन में कई बार आते हैं तो गुणनखंडों को दोहराएं नहीं।
एक अभाज्य घात pᵏ के लिए, मान pᵏ - pᵏ⁻¹ है।
फ़ंक्शन गुणक है: φ(m ×n) = φ(m) ×φ(n) यदि m और n सह-अभाज्य हैं।

Avoid these traps

Common Mistakes

गुणनफल सूत्र (product formula) में सभी भाजकों (divisors) को शामिल करना, केवल अद्वितीय अभाज्य गुणनखंडों के बजाय।
phi(n) को भाजकों की संख्या $τ$ (n) के साथ भ्रमित करना।

Common questions

Frequently Asked Questions

This derivation shows how Euler's totient function, which counts the positive integers up to a given integer n that are relatively prime to n, can be expressed using the prime factorization of n.

n मॉड्यूलो पूर्णांकों के गुणक समूह (multiplicative group of integers modulo n) के क्रम (order) की गणना करते समय इस फ़ंक्शन का उपयोग करें। यह मॉड्यूलर घातांक (modular exponentiation) में यूलर के प्रमेय को लागू करने या n क्रम के चक्रीय समूह में जनरेटर (generators) की संख्या निर्धारित करने के लिए प्राथमिक उपकरण है।

यह समीकरण RSA एन्क्रिप्शन एल्गोरिथम का गणितीय आधार है, जो आधुनिक डिजिटल संचार को सुरक्षित करता है। यह दो बड़ी अभाज्य संख्याओं के गुणनफल के टोटिएंट (totient) का निर्धारण करके निजी कुंजियों (private keys) की गणना की अनुमति देता है।

गुणनफल सूत्र (product formula) में सभी भाजकों (divisors) को शामिल करना, केवल अद्वितीय अभाज्य गुणनखंडों के बजाय। phi(n) को भाजकों की संख्या \tau(n) के साथ भ्रमित करना।

यदि n अभाज्य है, तो φ(n) = n - 1। केवल अद्वितीय अभाज्य गुणनखंडों (unique prime factors) की पहचान करें; यदि वे गुणनखंडन में कई बार आते हैं तो गुणनखंडों को दोहराएं नहीं। एक अभाज्य घात pᵏ के लिए, मान pᵏ - pᵏ⁻¹ है। फ़ंक्शन गुणक है: φ(m ×n) = φ(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.

यूलर का टोटिएंट फ़ंक्शन (Euler's Totient Function)

Overview

Variables

Derivation

Definition and Multiplicative Property:

Case for a Prime Power:

General Case using Prime Factorization:

Substituting and Simplifying:

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources