Mathematical modeling / English

Number Theory | Euler's Totient Function: Definition and Basic Example

Michael Penn · YouTube · 5:16

YouTube · Michael PennOriginal video

IN THIS VIDEO

01Euler's Totient Function Definition
02Connection to Group of Units
03Example: Calculating phi(5)

FROM THE LEARNING NOTES

\varphi(n) = \# \{ 1 \le m \le n \mid \gcd(m,n)=1 \}

Euler's Totient Function Definition

SELECTED MOMENT

Example: phi(15)

SUGGESTED PREPARATION

Natural numbers
Greatest Common Divisor (GCD)
Relatively prime (coprime) integers
Basic set notation
Natural numbers and positive integers
Prime numbers
Greatest common divisor
Set cardinality notation

READ & KEEP

The explanation, unpacked.

Saves 0

Reviewed learning material · Video analysis · English

Read the full overview

This video introduces Euler's totient function, defined as the count of positive integers up to n that are relatively prime to n. The presenter explains the formal definition using set notation and the greatest common divisor, noting its equivalence to the size of the group of units modulo n. Three examples are worked out on the blackboard: calculating $\varphi(5)$ , $\varphi(8)$ , and $\varphi(15)$ , demonstrating how to identify coprime integers for prime, power-of-two, and composite inputs. This introductory number-theory whiteboard segment first displays the definition of Euler's totient function, $\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$ , together with examples including $\varphi(5)=4$ , $\varphi(8)=4$ , and $\varphi(15)=8$ . The lecturer finishes explaining the $\varphi(15)$ example by noting that certain multiples are skipped and the remaining coprime integers are counted. He then erases the examples and states a proposition for primes: if $p$ is prime, then $\varphi(p)=p-1$ . After briefly giving the intuitive reason, he writes a careful proof using the facts that the only divisors of $p$ are 1 and $p$ , that any $m$ with $1\le m<p$ cannot be divisible by $p$ , and therefore $\gcd(p,m)=1$ for every such $m$ . The segment ends by concluding that all integers from 1 to $p-1$ are counted by $\varphi(p)$ , and by previewing a future formula for $\varphi$ of a prime power.

Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.

Chapters

0:00Introduction 0:21Definition of Euler's Totient Function 0:41Relation to Group of Units 1:01Example: phi(5)1:35Example: phi(8)2:05Example: phi(15)2:40Definition and examples on the board 2:59Transition from examples to a theorem 3:10Proposition for a prime p 3:46Careful proof that

\varphi(p)=p-1

5:07Conclusion and preview of prime powers

Learning script

Generated from the video's visuals and explanation; not verbatim speech.

The video begins with an introduction to Euler's totient function, also known as Euler's phi function. The presenter outlines the goal: to define the function, provide examples, and eventually derive formulas for its values.

The formal definition is presented on the blackboard. The function $\varphi: \mathbb{N} \rightarrow \mathbb{N}$ maps a natural number $n$ to the count of integers $m$ in the range $1 \le m \le n$ such that $\gcd(m,n)=1$ . In simpler terms, it counts how many numbers up to $n$ share no common factors with $n$ other than 1.

The presenter connects this definition to abstract algebra, noting that the set of integers relatively prime to $n$ forms the group of units modulo $n$ , denoted $U_n$ . Therefore, $\varphi(n)$ is equal to the order (size) of this group, written as $|U_n|$ .

The first example calculates $\varphi(5)$ . Since 5 is a prime number, all positive integers less than $5 (1, 2, 3, 4)$ are relatively prime to it. Thus, the set is $\{1, 2, 3, 4\}$ and the count is 4.

The second example calculates $\varphi(8)$ . Here, we must exclude numbers that share a factor with 8. Since 8 is even, all even numbers (2, 4, 6) have a greatest common divisor greater than 1 with 8. The remaining numbers are the odd integers $\{1, 3, 5, 7\}$ . Counting these gives $\varphi(8) = 4$ .

The third example calculates $\varphi(15)$ . The number 15 factors into $3 \times 5$ . We must exclude multiples of $3 (3, 6, 9, 12)$ and multiples of $5 (5, 10)$ . The remaining integers relatively prime to 15 are listed as $\{1, 2, 4, 7, 8, 11, 13, 14\}$ . Although the final count isn't explicitly written before the clip ends, there are 8 elements in this set.

The clip opens with the left half of the chalkboard already showing the definition of Euler's totient function, $\varphi:\mathbb{N}\to\mathbb{N}$ and $\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$ . On the right half, three worked examples are visible: $\varphi(5)=\#\{1,2,3,4\}=4$ , $\varphi(8)=\#\{1,3,5,7\}=4$ , and $\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$ . The lecturer is finishing the last example aloud, saying that one had to skip 12, skip 9, and so on, and that counting the remaining entries gives 8. Mathematically, this is a direct application of the definition: among the integers below 15, only those with greatest common divisor 1 with 15 are retained, and the cardinality of that retained set is 8.

After completing the example, the lecturer announces that he will clean up the board and then prove a formula for the value of $\varphi$ of a prime. Visually, the right-side examples are erased while the left-side definition remains. This transition signals a move from concrete computation to a general statement. The unchanged definition on the left serves as the formal basis for the theorem that follows.

On the cleared right side, the lecturer writes a proposition: 'For a prime p we have $\varphi(p)=p-1$ .' This is the central claim of the segment. The hypothesis is that $p$ is prime, and the conclusion is an exact formula for the totient at that input. The statement specializes the earlier definition by taking $n=p$ , so the task becomes counting how many integers $m$ with $1\le m<p$ satisfy $\gcd(p,m)=1$ .

Before writing the proof, the lecturer gives the intuitive reason the result should hold: the only integers that fail to be relatively prime to a prime are its multiples, and every positive integer smaller than $p$ is not a multiple of $p$ . He then explicitly says that, despite this seeming obvious, he will give a more careful proof for practice. This distinction matters pedagogically: the intuitive explanation identifies the key idea, while the forthcoming proof will justify it using the definition of prime divisors and the gcd condition from the definition of $\varphi$ .

The proof begins under the heading 'Proof:'. First, the lecturer writes that the only divisors of $p$ are 1 and $p$ . This step uses the definition of a prime number and establishes the complete divisor structure of $p$ . Next, he introduces an arbitrary integer $m$ satisfying $1\le m<p$ , matching the range specified in the definition of $\varphi(p)$ . From $m<p$ , he infers that $p$ cannot divide $m$ , because a positive multiple of $p$ would be at least $p$ itself.

The argument then converts the divisibility observation into a coprimality statement. Since the only divisors of $p$ are 1 and $p$ , and since $p\nmid m$ , the only possible common divisor of $p$ and $m$ is 1. This is written as $\gcd(p,m)=1$ . At this point the proof has shown that every integer $m$ in the allowed range $1\le m<p$ is relatively prime to $p$ . Applying the definition of the totient function, the counted set is therefore all of $\{1,2,\dots,p-1\}$ , whose size is $p-1$ . Hence $\varphi(p)=p-1$ , exactly as claimed.

The lecturer remarks that he will not write down every remaining detail because the verbal explanation has already covered them. He then closes the segment by stating that the next video will consider a formula for $\varphi$ of a power of a prime. Thus this clip completes the basic prime case and positions it as the first simple result in a sequence of formulas for the totient function.

Knowledge cards

Euler's Totient Function Definition

Euler's totient function, denoted $\varphi(n)$ , counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . Two numbers are relatively prime if their greatest common divisor (gcd) is 1.

\varphi(n) = \# \{ 1 \le m \le n \mid \gcd(m,n)=1 \}

Connection to Group of Units

The value of the totient function corresponds to the size of the multiplicative group of integers modulo n, often denoted as $U_n$ or (This formula needs review. Please report it using the page feedback control.{Z))^ $\times$ . This group consists of all residue classes modulo n that have a multiplicative inverse.

\varphi(n) = |U_n|

Example: Calculating phi(5)

For a prime number like 5, every positive integer less than 5 is relatively prime to it. The set is $\{1, 2, 3, 4\}$ , so the count is 4.

\varphi(5) = 4

Example: Calculating phi(8)

For $n=8$ , we exclude even numbers because they share a factor of 2 with 8. The valid integers are the odd numbers $\{1, 3, 5, 7\}$ . There are 4 such numbers.

\varphi(8) = 4

Example: Calculating phi(15)

For $n=15$ ( $3 \times 5$ ), we exclude multiples of 3 and 5. The remaining coprime integers are $\{1, 2, 4, 7, 8, 11, 13, 14\}$ . Counting these gives 8.

\varphi(15) = 8

Euler's totient function definition

The video defines $\varphi$ as a function from natural numbers to natural numbers. For each $n$ , $\varphi(n)$ is the number of integers $m$ such that $1\le m<n$ and $\gcd(m,n)=1$ . In plain terms, it counts the positive integers below $n$ that are relatively prime to $n$ .

\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}

Example: computing $\varphi(15)$

Using the definition with $n=15$ , the board lists the integers below 15 that are coprime to 15: $1,2,4,7,8,11,13,14$ . The lecturer explains that multiples such as 9 and 12 are skipped, and the remaining count is 8. Therefore $\varphi(15)=8$ .

\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8

Other visible examples

Two additional examples remain visible before the board is erased: $\varphi(5)=\#\{1,2,3,4\}=4$ and $\varphi(8)=\#\{1,3,5,7\}=4$ . These illustrate the same counting procedure on smaller inputs.

\varphi(5)=4,\quad \varphi(8)=4

Proposition for a prime input

The main theorem of the segment states that if $p$ is prime, then the totient of $p$ is exactly one less than $p$ . This is written as a proposition before the proof begins.

\varphi(p)=p-1\quad\text{for prime }p

Key idea behind the prime case

The lecturer first gives the intuition: the only integers that are not relatively prime to a prime are its multiples, and no positive integer smaller than $p$ is a multiple of $p$ . He then stresses that a more careful proof is still worth writing out.

Proof step 1: divisors of a prime

The proof starts from the defining property of a prime number: the only positive divisors of $p$ are 1 and $p$ itself. This fact is the foundation for the later gcd conclusion.

Proof step 2: choose $m$ below $p$

To evaluate $\varphi(p)$ , the proof considers an arbitrary integer $m$ with $1\le m<p$ , exactly the range appearing in the definition of the totient function.

1\le m<p

Proof step 3: $p$ cannot divide $m$

Because $m$ is strictly smaller than $p$ , it cannot be a positive multiple of $p$ . This is recorded on the board as $p\nmid m$ .

p\nmid m

Proof step 4: conclude $\gcd(p,m)=1$

Since the only divisors of $p$ are 1 and $p$ , and $p$ does not divide $m$ , the only common divisor shared by $p$ and $m$ is 1. Therefore $\gcd(p,m)=1$ for every $m$ in the range $1\le m<p$ .

p\nmid m\Rightarrow \gcd(p,m)=1

Final conclusion of the proof

Once every integer from 1 through $p-1$ has been shown to be relatively prime to $p$ , the definition of $\varphi$ implies that all $p-1$ of them are counted. Hence $\varphi(p)=p-1$ . The lecturer then previews the next topic, a formula for $\varphi$ of a power of a prime.

Detailed learning notes

Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.

Symbols · 12

$\varphi$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The board shows the function symbol $\varphi$ in the definition line $\varphi$ : $\mathbb{N} \rightarrow \mathbb{N}$ .
Audio
Observation
The speaker names it "Euler's phi function or Euler's totient function".

Symbol

$\varphi$

Meaning

Euler's totient function, which counts positive integers less than or equal to n that are relatively prime to n.

Domain

$n \in \mathbb{N}$

n

Clear evidence

Shown in the video

Evidence

Formula
Observation
The variable n appears in $\varphi(n)$ and in the set condition $1 \le m \le n$ .
Audio
Observation
The speaker refers to "natural numbers" when explaining the domain and codomain.

Symbol

Meaning

A natural number input to the totient function.

Domain

$n \in \mathbb{N}$

m

Clear evidence

Shown in the video

Evidence

Formula
Observation
The variable m is the dummy element in the set \{ $1 \le m \le n \mid \gcd(m,n)=1$ \}.

Symbol

Meaning

An integer ranging from 1 to n used to test whether it is relatively prime to n.

Domain

$1 \le m \le n$

$\gcd$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The expression $\gcd(m,n)=1$ appears on the board as the condition for membership in the set.
Audio
Observation
The speaker says "relatively prime to n" and later explicitly calculates "gcd of 2 with 8 is 2".

Symbol

$\gcd$

Meaning

Greatest common divisor function; $\gcd(m,n)=1$ means m and n share no common factors other than 1.

Domain

m, $n \in \mathbb{N}$

$U_n$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The speaker writes = | $U_n$ | below the definition.
Audio
Observation
The speaker mentions "the group of units modulo n".

Symbol

$U_n$

Meaning

The group of units modulo n, consisting of integers relatively prime to n under multiplication modulo n.

Domain

$n \in \mathbb{N}$

$\varphi$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Left board shows $\varphi:\mathbb{N}\to\mathbb{N}$ and $\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$ ; right board later shows $\varphi(p)=p-1$ .

Symbol

$\varphi$

Meaning

Euler's totient function, defined as the number of positive integers less than $n$ that are relatively prime to $n$ .

Domain

Input is a natural number $n$ ; output is a nonnegative integer count.

$n$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The definition line uses $\varphi(n)$ with condition $1\le m<n$ .

Symbol

$n$

Meaning

A natural-number argument of the totient function in the general definition.

Domain

$n\in\mathbb{N}$ .

$m$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The set-builder definition uses $m$ in $\{1\le m<n\mid \gcd(m,n)=1\}$ ; the proof writes $1\le m<p$ and $\gcd(p,m)=1$ .

Symbol

$m$

Meaning

An integer being tested for relative primality with the argument of $\varphi$ .

Domain

In the definition, $1\le m<n$ ; in the proof, $1\le m<p$ .

$\gcd(\cdot,\cdot)$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The definition contains $\gcd(m,n)=1$ , and the proof concludes $\gcd(p,m)=1$ .

Symbol

$\gcd(\cdot,\cdot)$

Meaning

Greatest common divisor function; equality to 1 expresses that two integers are relatively prime.

Domain

Applied to positive integers such as $(m,n)$ or $(p,m)$ .

$\#$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The left board writes $\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$ .

Symbol

$\#$

Meaning

Cardinality operator counting the number of elements in the displayed set.

Domain

Applied to finite sets of integers.

$p$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Right board states 'For a prime p' and then $\varphi(p)=p-1$ ; the proof uses divisors of $p$ and $1\le m<p$ .

Symbol

$p$

Meaning

A prime number used as the special input to the totient function in the proposition and proof.

Domain

$p$ is prime.

$|U_n|$

Approximate timing

Shown in the video

Evidence

Formula
Observation
Below the totient definition on the left board there is a separate line resembling $=|U_n|$ .

Uncertainties

The symbol is only partially legible in the sampled frames.
Its role is not explained in this clip.

Symbol

$|U_n|$

Meaning

An additional expression visible below the definition; likely a cardinality notation, but its exact meaning is not established in this segment.

Domain

Unclear from this clip.

Knowledge points · 4

Definition of Euler's Totient Function

Clear evidence

Shown in the video

Evidence

Formula
Observation
The board displays Def^n: Euler's totient function, $\varphi$ : $\mathbb{N} \rightarrow \mathbb{N}$ , and $\varphi(n)$ = \# \{ $1 \le m \le n \mid \gcd(m,n)=1$ \}.
Audio
Observation
The speaker states: "we define it as a function from N to N... and phi of n is equal to the number of elements in this set... all natural numbers between 1 and n that are relatively prime to n."

Definition

Explanation

Euler's totient function $\varphi(n)$ counts the number of positive integers m up to n that are relatively prime to n (i.e., their greatest common divisor is 1).

Formula

\varphi(n) = \# \{ 1 \le m \le n \mid \gcd(m,n)=1 \}

Conditions

n is a natural number

Prerequisites

$\varphi$
n
m
$\gcd$

Totient Function and Group of Units

Clear evidence

Shown in the video

Evidence

Formula
Observation
The speaker writes = | $U_n$ | directly below the set definition.
Audio
Observation
The speaker explains that the group of units modulo n has exactly these elements, so the count is the same as the number of elements in the group of units modulo n.

Method

Explanation

The value of $\varphi(n)$ is equivalent to the order (size) of the multiplicative group of integers modulo n, denoted $U_n$ .

Formula

\varphi(n) = |U_n|

Conditions

n is a natural number

Prerequisites

Definition of Euler's Totient Function
$U_n$

Definition of Euler's totient function

Clear evidence

Shown in the video

Evidence

Formula
Observation
Left board displays $\varphi:\mathbb{N}\to\mathbb{N}$ and $\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$ .
Audio
Observation
The lecturer refers to having 'defined Euler's totient function' before proving the next result.

Definition

Explanation

The video presents Euler's totient function as a map from natural numbers to natural numbers. For each $n$ , $\varphi(n)$ counts how many integers $m$ satisfy $1\le m<n$ and $\gcd(m,n)=1$ . In words, it counts the positive integers smaller than $n$ that are relatively prime to $n$ .

Formula

\varphi:\mathbb{N}\to\mathbb{N},\quad \varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}

Conditions

$n$ is a natural number.
The counted integers $m$ satisfy $1\le m<n$ .
Relative primality is expressed by $\gcd(m,n)=1$ .

Worked example $\varphi(15)=8$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Right board shows $\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$ .
Audio
Observation
The lecturer says they had to skip 12, skip 9, and so on, and that counting gives 8.

Method

Explanation

The example applies the definition directly to $n=15$ . The listed set contains the integers below 15 that are coprime to 15, and the final count is 8. The spoken explanation emphasizes excluding multiples of 3 and 5, which matches the visible list omitting numbers such as 3, 6, 9, 12, and 15.

Formula

\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8

Conditions

Use the definition with $n=15$ .
Only integers $m$ with $1\le m<15$ are considered.
Keep exactly those $m$ with $\gcd(m,15)=1$ .

Prerequisites

Definition of Euler's totient function

Claims and conditions · 1

Totient of a prime equals $p-1$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Right board states 'Proposition: For a prime p we have $\varphi(p)=p-1$ .'
Audio
Observation
The lecturer says they will prove a formula for the value of $\varphi$ of a prime.

Theorem

Statement

For every prime number $p$ , $\varphi(p)=p-1$ .

Hypotheses

$p$ is prime.

Quantifiers

Universal over primes $p$ .

Derivations and proofs · 1

Proof that $\varphi(p)=p-1$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Proof written on the right board includes 'Notice the only divisors of p are 1 and p', 'Let $1\le m<p$ ', and ' $p\nmid m \Rightarrow \gcd(p,m)=1$ '.
Audio
Observation
The lecturer explains that the only divisors of $p$ are 1 and $p$ , that any $m<p$ cannot be divisible by $p$ , and therefore $\gcd(p,m)=1$ , so all numbers from 1 to $p-1$ are counted.

Proof

Steps

Expression
Explanation
Start from the fact that if $p$ is prime, its only positive divisors are 1 and $p$ itself.
Justification
Definition of a prime number.
Shown in the video
Expression
$1\le m<p$
Explanation
Take an arbitrary integer $m$ in the range used by the totient definition for input $p$ .
Justification
The definition of $\varphi(p)$ counts $m$ with $1\le m<p$ .
Shown in the video
Expression
$p\nmid m$
Explanation
Because $m$ is strictly smaller than $p$ , $m$ cannot be a multiple of $p$ .
Justification
A positive multiple of $p$ is at least $p$ itself.
Shown in the video
Expression
$\gcd(p,m)=1$
Explanation
Since the only divisors of $p$ are 1 and $p$ , and $p$ does not divide $m$ , the only common divisor of $p$ and $m$ is 1.
Justification
Common divisors of $p$ and $m$ must be divisors of $p$ ; excluding $p$ leaves only 1.
Shown in the video
Expression
$\varphi(p)=p-1$
Explanation
Therefore every integer $m$ with $1\le m<p$ is relatively prime to $p$ , so the counted set has exactly $p-1$ elements.
Justification
Apply the definition of $\varphi$ after establishing $\gcd(p,m)=1$ for all $1\le m<p$ .
Shown in the video

Conclusion

All integers from 1 through $p-1$ are relatively prime to a prime $p$ , hence $\varphi(p)=p-1$ .

Worked examples · 5

Example: $\varphi(5)$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The board shows $\varphi(5)$ = \# \{ 1, 2, 3, 4 \} = 4.
Audio
Observation
The speaker lists the positive integers smaller than 5 that are relatively prime to 5: 1, 2, 3, and 4, concluding $\varphi(5)$ is 4.

Problem

Calculate $\varphi(5)$ .

Given

$n = 5$

Goal

Find the number of integers m with $1 \le m \le 5$ such that $\gcd(m,5)=1$ .

Steps

Expression
$\{ 1, 2, 3, 4 \}$
Explanation
List integers from 1 to 5 that are coprime to 5.
Justification
Since 5 is prime, all positive integers less than 5 are coprime to it.
Shown in the video
Expression
$4$
Explanation
Count the elements in the set.
Justification
There are 4 elements listed.
Shown in the video

Answer

$\varphi(5) = 4$

Verification

Direct counting matches the definition.

Example: $\varphi(8)$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The board shows $\varphi(8)$ = \# \{ 1, 3, 5, 7 \} = 4.
Audio
Observation
The speaker skips even numbers because their gcd with 8 is not 1 (e.g., gcd(2,8)=2, gcd(4,8)=4, gcd(6,8)=2), leaving 1, 3, 5, 7.

Problem

Calculate $\varphi(8)$ .

Given

$n = 8$

Goal

Find the number of integers m with $1 \le m \le 8$ such that $\gcd(m,8)=1$ .

Steps

Expression
$\{ 1, 3, 5, 7 \}$
Explanation
List odd integers from 1 to 8.
Justification
Even numbers share a factor of 2 with 8, so they are not coprime to 8.
Shown in the video
Expression
$4$
Explanation
Count the elements in the set.
Justification
There are 4 elements listed.
Shown in the video

Answer

$\varphi(8) = 4$

Verification

Direct counting and checking gcd values confirms the result.

Example: $\varphi(15)$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The board shows $\varphi(15)$ = \# \{ 1, 2, 4, 7, 8, 11, 13, 14 \}.
Audio
Observation
The speaker lists numbers relatively prime to 15, explicitly skipping multiples of 3 and $5 (3, 5, 6, 9, 10, 12, 15)$ .

Uncertainties

The final count for $\varphi(15)$ is not written on the board before the video ends, though the set contains 8 elements.

Problem

Calculate $\varphi(15)$ .

Given

$n = 15$

Goal

Find the number of integers m with $1 \le m \le 15$ such that $\gcd(m,15)=1$ .

Steps

Expression
$\{ 1, 2, 4, 7, 8, 11, 13, 14 \}$
Explanation
List integers from 1 to 15 that do not share factors with 15 (i.e., not divisible by 3 or 5).
Justification
$15 = 3 \times 5$ , so any multiple of 3 or 5 will have a gcd > 1 with 15.
Shown in the video

Answer

The set has 8 elements, so $\varphi(15) = 8$ (implied but not explicitly stated as a final number on the board).

Verification

Counting the listed elements yields 8.

Computing $\varphi(15)$ by listing coprime integers

Clear evidence

Shown in the video

Evidence

Formula
Observation
Right board lists $\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$ .
Audio
Observation
The lecturer says to skip 12, skip 9, and so on, then count up to get 8.

Problem

Compute $\varphi(15)$ using the definition of Euler's totient function.

Given

$n=15$ .
$\varphi(n)$ counts integers $m$ with $1\le m<n$ and $\gcd(m,n)=1$ .

Goal

Find the number of positive integers less than 15 that are relatively prime to 15.

Steps

Expression
$1\le m<15$
Explanation
Consider the candidate integers below 15.
Justification
Directly from the definition of $\varphi(15)$ .
Shown in the video
Expression
$\{1,2,4,7,8,11,13,14\}$
Explanation
Keep exactly those candidates whose greatest common divisor with 15 is 1; the board displays this surviving set.
Justification
Application of $\gcd(m,15)=1$ .
Shown in the video
Expression
$8$
Explanation
Count the elements of the displayed set.
Justification
Cardinality of the listed finite set.
Shown in the video

Answer

$\varphi(15)=8$ .

Verification

The spoken explanation mentions skipping multiples such as 9 and 12, consistent with excluding numbers sharing a factor with 15.

Additional visible examples $\varphi(5)$ and $\varphi(8)$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Right board also shows $\varphi(5)=\#\{1,2,3,4\}=4$ and $\varphi(8)=\#\{1,3,5,7\}=4$ .

Uncertainties

These examples are visible but not verbally worked out in detail during this clip.

Problem

Read the other totient examples already written on the board.

Given

$\varphi(5)=\#\{1,2,3,4\}=4$ .
$\varphi(8)=\#\{1,3,5,7\}=4$ .

Goal

Record the displayed example values without extra derivation.

Steps

Expression
$\varphi(5)=4$
Explanation
The board lists the four positive integers below 5 and gives their count.
Justification
Visible worked example on the board.
Shown in the video
Expression
$\varphi(8)=4$
Explanation
The board lists the odd integers below 8 and gives their count.
Justification
Visible worked example on the board.
Shown in the video

Answer

$\varphi(5)=4$ and $\varphi(8)=4$ .

Verification

Both lines match the same set-counting definition shown on the left board.

Visual events · 4

Blackboard Layout

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A blackboard is split by a yellow vertical line. The left side contains the pre-written definition of Euler's totient function.

Objects

Blackboard
Yellow dividing line
Pre-written text on the left

Invariants

The left side remains static during the examples.

Interpretation

The layout separates the formal definition from the worked examples.

Writing Examples

Clear evidence

Shown in the video

Evidence

Animation
Observation
The speaker writes 'examples' on the right side and sequentially calculates $\varphi(5)$ , $\varphi(8)$ , and $\varphi(15)$ .

Objects

Chalk
Right side of blackboard

Changes

Text appears sequentially as the speaker calculates each example.

Invariants

The definition on the left remains visible.

Interpretation

Visual progression of applying the definition to specific numbers.

Board cleared from examples to theorem statement

Clear evidence

Shown in the video

Evidence

Animation
Observation
The right side of the chalkboard containing the examples is erased, leaving the left-side definition visible.
Audio
Observation
The lecturer says he will clean up the board and then prove a formula for the value of $\varphi$ of a prime.

Objects

Chalkboard left panel with the definition of $\varphi$ .
Chalkboard right panel with examples $\varphi(5)$ , $\varphi(8)$ , and $\varphi(15)$ .

Changes

The example computations on the right are erased.
The left definition remains visible.
A new heading 'Proposition' is then written on the right.

Invariants

The definition of $\varphi$ on the left stays on screen.
The lecture topic remains Euler's totient function.

Interpretation

The visual transition marks a shift from concrete examples to a general statement about primes.

Stepwise writing of the prime-totient proof

Clear evidence

Shown in the video

Evidence

Animation
Observation
Under 'Proof:' the lecturer writes the divisor fact, the assumption $1\le m<p$ , and the implication $p\nmid m\Rightarrow\gcd(p,m)=1$ .

Objects

Text 'Proof:'.
Sentence about the only divisors of $p$ .
Inequality $1\le m<p$ .
Implication involving $p\nmid m$ and $\gcd(p,m)=1$ .

Changes

Each proof line is added sequentially on the right board.
The argument moves from properties of divisors to a gcd conclusion.

Invariants

The left-side definition of $\varphi$ remains visible throughout.
The proposition $\varphi(p)=p-1$ stays above the proof.

Interpretation

The writing order mirrors the logical structure: prime divisor fact, arbitrary $m<p$ , exclusion of divisibility by $p$ , then coprimality.

Misconceptions · 2

Skipping Non-Coprime Numbers

Clear evidence

Shown in the video

Evidence

Audio
Observation
When calculating $\varphi(8)$ , the speaker notes that even numbers must be skipped because their gcd with 8 is not 1.

Misconception

Assuming all numbers up to n are included in the count.

Clarification

Only numbers m where $\gcd(m,n)=1$ are counted; for composite n like 8, many numbers (like evens) are excluded.

Intuitive plausibility is not the same as a formal proof

Clear evidence

Shown in the video

Evidence

Audio
Observation
The lecturer says the result may seem obvious because only multiples of a prime fail to be relatively prime to it, but adds that they will give a more careful proof for practice.

Misconception

One might think $\varphi(p)=p-1$ needs no proof because it looks obvious from the behavior of multiples of $p$ .

Clarification

The video explicitly separates the intuitive reason from a more careful proof, showing that the conclusion should still be justified from the definition of prime divisors and gcd.

Concept relations · 4

Definition of Euler's Totient Function → Totient Function and Group of Units

Clear evidence

Shown in the video

Evidence

Audio
Observation
Speaker links the set definition to the group of units modulo n.
Formula
Observation
Writes = | $U_n$ |.

Equivalent

Explanation

The cardinality of the set of coprimes is exactly the order of the group of units modulo n.

Definition of Euler's totient function → Totient of a prime equals $p-1$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The proof repeatedly uses the definition $\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$ with $n=p$ .

Proof dependency

Explanation

The proposition $\varphi(p)=p-1$ is proved by applying the general definition of $\varphi$ to the special case $n=p$ and analyzing $\gcd(p,m)$ .

Definition of Euler's totient function → Worked example $\varphi(15)=8$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The examples $\varphi(5)$ , $\varphi(8)$ , and $\varphi(15)$ are written as cardinalities of sets matching the definition on the left.

Application

Explanation

The worked examples instantiate the abstract definition by listing the relevant coprime integers and counting them.

Totient of a prime equals $p-1$ → Proof that $\varphi(p)=p-1$

Clear evidence

Shown in the video

Evidence

Formula
Observation
The proof links 'the only divisors of p are 1 and p' with the conclusion $\gcd(p,m)=1$ once $p\nmid m$ is known.

Contains

Explanation

The key ingredient inside the proof is the divisor structure of a prime number, which is then converted into a gcd statement.

Find an answer · 7

What is the formal definition of Euler's totient function?

Clear evidence

Shown in the video

Evidence

Formula
Observation
Board shows definition.

Knowledge points

Definition of Euler's Totient Function

How do you calculate phi(8)?

Clear evidence

Shown in the video

Evidence

Formula
Observation
Board shows calculation for 8.

Knowledge points

Example: $\varphi(8)$

What is the definition of Euler's totient function shown on the board?

Clear evidence

Derived from the video

Evidence

Formula
Observation
The left board displays the full definition of $\varphi(n)$ .

Knowledge points

Definition of Euler's totient function

Why does $\varphi(p)=p-1$ when $p$ is prime?

Clear evidence

Derived from the video

Evidence

Formula
Observation
The right board states and proves $\varphi(p)=p-1$ for a prime $p$ .

Knowledge points

Totient of a prime equals $p-1$
Proof that $\varphi(p)=p-1$

How is $\varphi(15)$ computed in the example?

Clear evidence

Derived from the video

Evidence

Formula
Observation
The board lists $\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$ .
Audio
Observation
The lecturer mentions skipping 12 and 9 before counting to 8.

Knowledge points

Worked example $\varphi(15)=8$
Computing $\varphi(15)$ by listing coprime integers

What role does $\gcd(m,n)=1$ play in the definition and proof?

Clear evidence

Derived from the video

Evidence

Formula
Observation
Both the definition and the proof use $\gcd(\cdot,\cdot)=1$ to express relative primality.

Knowledge points

Definition of Euler's totient function
Proof that $\varphi(p)=p-1$

What other totient examples are visible besides $\varphi(15)$ ?

Approximate timing

Derived from the video

Evidence

Formula
Observation
The board also shows $\varphi(5)=4$ and $\varphi(8)=4$ .

Uncertainties

These examples are visible but not discussed in detail in the audio during this clip.

Knowledge points

Additional visible examples $\varphi(5)$ and $\varphi(8)$

Coverage and review notes

Covered · Introduction and context setting.

Covered · Definition and relation to group of units.

Covered · Worked examples.

Covered · Opening board state shows the definition and three examples; the audio finishes the count for $\varphi(15)=8$ .

Covered · The lecturer transitions from examples toward the next theorem while the example board remains visible.

Covered · The right-side examples are erased and the lecturer announces a proof about $\varphi$ of a prime.

Covered · The proposition 'For a prime p we have $\varphi(p)=p-1$ ' is written on the board.

Covered · The lecturer gives the intuitive reason and says a more careful proof will follow.

Covered · The full proof is written and explained step by step from divisors of $p$ to $\gcd(p,m)=1$ and then to $\varphi(p)=p-1$ .

Covered · The lecturer closes the segment and previews the next topic, a formula for $\varphi$ of a power of a prime.

Explore the knowledge in this video

Open video knowledge graph →

Euler's totient ExplanationAt 0:22
Why this connection?
Reviewed English material v1: card "Euler's Totient Function Definition" at 0:22 — Euler's totient function, denoted $\varphi(n)$ , counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . Two numbers are relatively prime if their greatest common divisor (gcd) is 1.

Number Theory | Euler's Totient Function: Definition and Basic Example

The explanation, unpacked.

Chapters

Learning script

Knowledge cards

Euler's Totient Function Definition

Connection to Group of Units

Example: Calculating phi(5)

Example: Calculating phi(8)

Example: Calculating phi(15)

Euler's totient function definition

Example: computing φ(15)\varphi(15)φ(15)

Other visible examples

Proposition for a prime input

Key idea behind the prime case

Proof step 1: divisors of a prime

Proof step 2: choose mmm below ppp

Proof step 3: ppp cannot divide mmm

Proof step 4: conclude gcd⁡(p,m)=1\gcd(p,m)=1gcd(p,m)=1

Final conclusion of the proof

Detailed learning notes

φ\varphiφ

n

m

gcd⁡\gcdgcd

UnU_nUn​

φ\varphiφ

nnn

mmm

gcd⁡(⋅,⋅)\gcd(\cdot,\cdot)gcd(⋅,⋅)

#\##

ppp

∣Un∣|U_n|∣Un​∣

Definition of Euler's Totient Function

Totient Function and Group of Units

Definition of Euler's totient function

Worked example φ(15)=8\varphi(15)=8φ(15)=8

Totient of a prime equals p−1p-1p−1

Proof that φ(p)=p−1\varphi(p)=p-1φ(p)=p−1

Example: φ(5)\varphi(5)φ(5)

Example: φ(8)\varphi(8)φ(8)

Example: φ(15)\varphi(15)φ(15)

Computing φ(15)\varphi(15)φ(15) by listing coprime integers

Additional visible examples φ(5)\varphi(5)φ(5) and φ(8)\varphi(8)φ(8)

Blackboard Layout

Writing Examples

Board cleared from examples to theorem statement

Stepwise writing of the prime-totient proof

Skipping Non-Coprime Numbers

Intuitive plausibility is not the same as a formal proof

Definition of Euler's Totient Function → Totient Function and Group of Units

Definition of Euler's totient function → Totient of a prime equals p−1p-1p−1

Definition of Euler's totient function → Worked example φ(15)=8\varphi(15)=8φ(15)=8

Totient of a prime equals p−1p-1p−1 → Proof that φ(p)=p−1\varphi(p)=p-1φ(p)=p−1

What is the formal definition of Euler's totient function?

How do you calculate phi(8)?

What is the definition of Euler's totient function shown on the board?

Why does φ(p)=p−1\varphi(p)=p-1φ(p)=p−1 when ppp is prime?

How is φ(15)\varphi(15)φ(15) computed in the example?

What role does gcd⁡(m,n)=1\gcd(m,n)=1gcd(m,n)=1 play in the definition and proof?

What other totient examples are visible besides φ(15)\varphi(15)φ(15)?

Explore the knowledge in this video

More in this subject

Example: computing $\varphi(15)$

Proof step 2: choose $m$ below $p$

Proof step 3: $p$ cannot divide $m$

Proof step 4: conclude $\gcd(p,m)=1$

$\varphi$

$\gcd$

$U_n$

$\varphi$

$n$

$m$

$\gcd(\cdot,\cdot)$

$\#$

$p$

$|U_n|$

Worked example $\varphi(15)=8$

Totient of a prime equals $p-1$

Proof that $\varphi(p)=p-1$

Example: $\varphi(5)$

Example: $\varphi(8)$

Example: $\varphi(15)$

Computing $\varphi(15)$ by listing coprime integers

Additional visible examples $\varphi(5)$ and $\varphi(8)$

Definition of Euler's totient function → Totient of a prime equals $p-1$

Definition of Euler's totient function → Worked example $\varphi(15)=8$

Totient of a prime equals $p-1$ → Proof that $\varphi(p)=p-1$

Why does $\varphi(p)=p-1$ when $p$ is prime?

How is $\varphi(15)$ computed in the example?

What role does $\gcd(m,n)=1$ play in the definition and proof?

What other totient examples are visible besides $\varphi(15)$ ?