MathematicsNumber TheoryUniversity

OCRAPOntarioNSWCBSEGCE O-LevelMoECAPS

Euler's Totient Function

Counts the number of positive integers up to n that are coprime to n.

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

Euler's Totient Function, denoted as φ(n), counts the number of positive integers up to n that are relatively prime to n. It is a fundamental multiplicative function in number theory used to explore the properties of modular arithmetic and cyclic groups.

When to use: Use this function when calculating the order of the multiplicative group of integers modulo n. It is the primary tool for applying Euler's Theorem in modular exponentiation or when determining the number of generators in a cyclic group of order n.

Why it matters: This equation is the mathematical cornerstone of the RSA encryption algorithm, which secures modern digital communications. It allows for the calculation of private keys by determining the totient of the product of two large primes.

Symbols

Variables

\phi(n) = Totient Value, n = Input Integer

ϕ (n)

Totient Value

V a r iab l e

n

Input Integer

V a r iab l e

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.

n is a positive integer.
p denotes a prime number.

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.

Free formulas

Rearrangements

Solve for $ϕ (n)$

Euler's Totient Function Formula

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

This formula defines Euler's Totient Function, $ϕ$ (n), which counts the positive integers up to a given integer n that are relatively prime to n. The formula expresses $ϕ$ (n) in terms of n and its distinct prime factors p.

Difficulty: 2/5

The static page shows the finished rearrangements. The app keeps the full worked algebra walkthrough.

Visual intuition

Graph

Graph unavailable for this formula.

The plot of Euler's Totient function appears as a chaotic scatter of points that forms an upper boundary near the line y = x-1, punctuated by sharp downward spikes at prime numbers. The global trend is linearly increasing on average, yet the function exhibits extreme local volatility because the output depends heavily on the prime factorization of each integer. The recurring 'dips' correspond to numbers with many small prime factors, illustrating the function's sensitivity to the density of divisors.

Graph type: step

Why it behaves this way

Intuition

Imagine a sieve where you start with all numbers from 1 to n, and then systematically filter out all multiples of each distinct prime factor of n, leaving only those numbers that share no common factors with n.

ϕ (n)

The count of positive integers less than or equal to n that are coprime to n.

Represents the 'coprime density' or 'relative primality' of numbers up to n. A higher

ϕ

(n) means more numbers share no common prime factors with n.

The positive integer for which the totient is being calculated.

The upper bound of the range of integers being considered; the 'universe' of numbers from 1 to n.

A distinct prime factor of n.

These are the fundamental prime building blocks of n, which, if shared, prevent other numbers from being coprime to n.

(1 - \frac{1}{p})

The proportion of numbers up to n that are not divisible by p.

This factor 'removes' the numbers that share a prime factor p with n, effectively filtering out non-coprime numbers based on p.

Signs and relationships

(1 - \frac{1}{p}): The subtraction '1 - ...' represents the principle of exclusion. From the total set (represented by 1), the proportion of numbers divisible by a prime factor p (which is 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.

Common confusion

Students sometimes try to assign physical units to the input or output of number theoretic functions. However, Euler's Totient Function deals purely with integer counts, which are dimensionless and do not have associated

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.

Unit systems

$n$ integer · Represents a positive integer input to the function.

$p$ integer · Represents a prime factor of n.

$ϕ (n)$ integer · Represents the count of positive integers up to n that are coprime to n.

One free problem

Practice Problem

An analyst needs to determine the number of integers less than 12 that share no common factors with 12 other than 1. Calculate the result of the totient function for this value.

Input Integer12

Solve for: $r es u l t$

Hint: The prime factors of 12 are 2 and 3.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

In RSA cryptography, the totient of the product of two large primes p and q is phi(n) = (p-1)(q-1), which is used to calculate the decryption key.

Study smarter

Tips

If n is prime, then φ(n) = n - 1.
Identify only unique prime factors; do not repeat factors if they appear multiple times in the factorization.
For a prime power pᵏ, the value is pᵏ - pᵏ⁻¹.
The function is multiplicative: φ(m × n) = φ(m) × φ(n) if m and n are coprime.

Avoid these traps

Common Mistakes

Incorrectly including all divisors instead of only unique prime factors in the product formula.
Confusing phi(n) with the number of divisors au(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.

Use this function when calculating the order of the multiplicative group of integers modulo n. It is the primary tool for applying Euler's Theorem in modular exponentiation or when determining the number of generators in a cyclic group of order n.

This equation is the mathematical cornerstone of the RSA encryption algorithm, which secures modern digital communications. It allows for the calculation of private keys by determining the totient of the product of two large primes.

Incorrectly including all divisors instead of only unique prime factors in the product formula. Confusing phi(n) with the number of divisors au(n).