Euler's totient, Quadratic residues｜封无义

1. Audio
   Observation

   The narrator says, "That brings us to Euler's totient function $φ(n)$."

2. Formula
   Observation

   The screen displays "Euler's totient function $φ(n)$" and "$φ(n)$: the number of integers from 1 to n that are coprime to n."

$\varphi(n)$

Euler's totient function counts the number of integers coprime to n among those from 1 to n.

n is a positive integer; later in the video, the unique factorization case for $n > 1$ is discussed.

1. Audio
   Observation

   The narrator says, "Let p be a prime number."

2. Formula
   Observation

   The screen displays "Let P be a prime." "Therefore, among the numbers from 1 to P, there are $P - 1$ numbers coprime to P." "Therefore, $φ(P) = P - 1$."

1. The uppercase P on screen and the lowercase p in the audio differ in case, but both represent a prime number mathematically.

p

Primes are used to study the values of Euler's totient function at primes and prime powers.

p is a prime number.

1. Audio
   Observation

   The narrator says, "Among the numbers from 1 to p raised to the k-th power, all except multiples of p are coprime to p raised to the k-th power."

2. Formula
   Observation

   The screen displays "Among the numbers from 1 to $P^k$, there are $P^{k-1}$ numbers not coprime to $P^k$." and "Therefore, $φ(P^k) = P^k - P^{k-1}$."

1. The video does not explicitly specify the range of k; in the context of prime powers, k is conventionally understood to be a positive integer.

k

The exponent of the prime number p, appearing in $p^k$ and $p^{k-1}$.

Not stated in the video; context implies it is a positive integer.

1. Audio
   Observation

   The voiceover says, "If n is a positive integer greater than 1, then n can be uniquely factored into a product of prime numbers."

2. Formula
   Observation

   The screen displays "Fundamental Theorem of Arithmetic: If n is a positive integer greater than 1, then $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}$."

n

The positive integer greater than 1 in the Fundamental Theorem of Arithmetic.

n is an integer greater than 1.

1. Formula
   Observation

   The screen displays the factors $p_1$, $p_2$, $\ldots$, $p_m$ in the factorization.

2. Audio
   Observation

   The voiceover reads term by term: "p1 raised to the power k1, times p2 raised to the power k2, times p3 raised to the power k3, continuing up to $p_m$ raised to the power $k_m$."

$p_i$

The prime factors of n in the Fundamental Theorem of Arithmetic, where $i = 1$, 2, $\ldots$, m.

$p_i$ is a prime number.

1. Formula
   Observation

   The screen displays the exponents $k_1$, $k_2$, $\ldots$, $k_m$.

2. Audio
   Observation

   The voiceover reads each term aloud: "k1th power, k2th power, k3th power, $\ldots$, k_mth power."

1. The video does not explicitly state whether $k_i$ is a positive integer; in the context of the Fundamental Theorem of Arithmetic, it is usually a positive integer.

$k_i$

The exponent of the prime factor $p_i$ in the unique factorization of n.

The video does not specify; according to context, it should be a positive integer.

1. Formula
   Observation

   The image shows the factorization ending with $p_m^{k_m}$.

2. Audio
   Observation

   The voiceover says, "multiply all the way up to $p_m$ raised to the $k_m$-th power."

1. The video does not explicitly state the range of m; according to context, it should be the number of distinct prime factors.

m

The number of distinct prime factors of n.

The video does not specify; according to context, it should be a positive integer.

1. Formula
   Observation

   Expressions such as $φ(n)$, φ(nm), and $φ(p_i^{k_i})$ appear multiple times on screen.

$\varphi$

Euler's totient function, which counts the positive integers less than or equal to a given positive integer that are coprime to it.

positive integer

1. Formula
   Observation

   The screen displays gcd(n,m)=1 and φ(nm)=$φ(n)\cdot φ(m)$.

n, m

two positive integers, required to be coprime in the discussion of multiplicativity.

positive integer

1. Formula
   Observation

   The screen displays gcd(n,m)=1.

gcd

greatest common divisor; gcd(n,m)=1 means n and m are coprime.

pair of integers

1. Formula
   Observation

   The final formula uses $\prod _{i=1}^m (1 - 1/p_i)$.

$\prod_{i=1}^m$

product notation, representing multiplication of factors from $i=1$ to m.

finite product

1. Formula
   Observation

   The screen displays $n = p_1^{k_1} \cdot p_2^{k_2} \cdot p_3^{k_3} \cdot \cdot \cdot p_m^{k_m}$.

$p_i$, $k_i$

$p_i$ is the i-th distinct prime factor, and $k_i$ is its exponent in the prime factorization of n.

$p_i$ is a prime number, and $k_i$ is a positive integer.

1. Audio
   Observation

   The voiceover says, "If the greatest common divisor of this number and 6 is 1, then it is coprime to 6."

2. Diagram
   Observation

   The image lists integers from 1 to 6 and highlights each integer one by one for checking.

The video uses the concrete example "this number and 6" to explain: if the greatest common divisor of an integer and 6 is 1, then it is coprime to 6. This criterion applies when enumerating numbers coprime to a given integer n, from 1 to n.

1. a and n are integers

2. In the video example, $n = 6$

1. Audio
   Observation

   The narrator says, "We define $φ(n)$ as the number of integers coprime to n in the range from 1 to n."

2. Formula
   Observation

   The screen displays "Euler's totient function $φ(n)$" and "$φ(n)$: the number of integers coprime to n in the range from 1 to n."

Euler's totient function phi of n is defined as the number of integers from 1 to n that are coprime to n. The earlier examples 1 to 6 are concrete illustrations of this definition: counting the numbers from 1 to 6 that are coprime to 6.

1. n is a positive integer

2. The counting range is from 1 to n

1. Coprime status is determined by the greatest common divisor.

1. Audio
   Observation

   The narrator says, "Therefore, $φ(p^k) = p^k - p^{k-1}$."

2. Formula
   Observation

   The screen displays "∴ $φ(P^k) = P^k - P^{k-1}$."

1. The video does not explicitly specify the range of k; in the context of prime powers, k is conventionally understood to be a positive integer.

When p is a prime, among the numbers from 1 to $p^k$, exactly those divisible by p are not coprime to $p^k$, and there are $p^{k-1}$ such numbers; therefore, the count of numbers coprime to $p^k$ equals the total $p^k$ minus the count of non-coprime numbers $p^{k-1}$.

1. p is a prime

2. k is a positive integer, as indicated by context

1. Definition of Euler's totient function $φ(n)$
2. Coprime status is determined by the greatest common divisor.

1. Audio
   Observation

   The voiceover states: "Next, Euler's totient function is multiplicative; that is, for two coprime integers n and m, φ(nm) = $φ(n)φ(m)$."

2. Formula
   Observation

   The screen writes: $φ(n)$ is multiplicative, gcd(n, m) = 1, and φ(nm) = $φ(n) \cdot φ(m)$.

The video describes Euler's totient function φ as multiplicative: when two positive integers n and m are coprime, φ(nm) equals the product of $φ(n)$ and $φ(m)$. This property is the key basis for later splitting $φ(n)$ according to its prime factorization.

1. n and m are positive integers.

2. gcd(n, m) = 1, meaning n and m are coprime.

1. Audio
   Observation

   The voiceover says: "Because n equals p1 raised to the power k1, times p2 raised to the power k2, times p3 raised to the power k3, and so on up to $p_m$ raised to the power $k_m$."

2. Formula
   Observation

   The screen writes $n = p_1^{k_1} \cdot p_2^{k_2} \cdot p_3^{k_3} \cdot \cdot \cdot p_m^{k_m}$.

The video expresses a general positive integer n as the product of powers of distinct prime numbers. Here, $p_i$ denotes distinct prime factors, and $k_i$ denotes the exponent corresponding to each prime factor.

1. $p_i$ is a prime number

2. The $p_i$ are pairwise distinct

3. $k_i$ is a positive integer

1. Audio
   Observation

   The narrator says, "Substitute our second prime-number case."

2. Formula
   Observation

   The screen replaces $φ(p_i^{k_i})$ with $p_i^{k_i} - p_i^{k_i - 1}$.

1. The video does not reprove the prime-power formula in this segment; it only cites earlier material.

The video cites the previously derived prime-power case: for a prime p and a positive integer k, $φ(p^k) = p^k - p^{k - 1}$. In this segment, it substitutes this expression for each prime-power factor to obtain the general formula.

1. p is a prime number

2. k is a positive integer

1. Prime factorization form of a positive integer

1. Audio
   Observation

   The narrator says, "Finally, we simplify using the product notation." "Ultimately, we have derived the general form of Euler's totient function."

2. Formula
   Observation

   The screen finally displays $φ(n) = n \prod _{i=1}^m (1 - 1/p_i)$, highlighted in a yellow box.

Derived from prime factorization and multiplicativity: if the distinct prime factors of n are $p_1$, ..., $p_m$, then $φ(n)$ equals n multiplied by the product of the factors ($1 - 1/p_i$) corresponding to each prime factor.

1. n is a positive integer

2. $p_1$, ..., $p_m$ are all the distinct prime factors of n

1. The multiplicativity of Euler's totient function
2. Prime factorization form of a positive integer
3. Euler's totient function formula for prime powers

1. Audio
   Observation

   The voiceover says "Because all numbers from 1 to p except p itself are coprime to p, the numbers from 1 to p that are coprime to p are p minus 1 in total, so phi of p equals p minus 1."

2. Formula
   Observation

   The screen displays "Let P be a prime." "Therefore, among the numbers from 1 to P, there are $P - 1$ numbers coprime to P." "Therefore, $φ(P) = P - 1$."

If p is a prime, then $φ(p) = p-1$.

1. p is a prime

2. $φ(p)$ is defined as the count of integers from 1 to p that are coprime to p

Holds for all primes p.

1. Audio
   Observation

   The voiceover says, "First is the fundamental theorem of arithmetic. If n is a positive integer greater than 1, then n can be uniquely expressed as a product of primes."

2. Formula
   Observation

   The screen displays: "Fundamental theorem of arithmetic: If n is a positive integer greater than 1, then $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}$".

1. The video does not present a proof of the Fundamental Theorem of Arithmetic, nor does it explicitly state the full condition that the $p_i$ are distinct primes and the $k_i$ are positive integers.

If n is a positive integer greater than 1, then n can be uniquely factored as a product of prime powers: $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$.

1. n is a positive integer greater than 1

Holds for all positive integers n satisfying $n > 1$.

1. Audio
   Observation

   The voiceover says, "Moreover, the p's are pairwise coprime."

2. Formula
   Observation

   The terms $p_i^{k_i}$ in context come from powers of distinct primes.

If $p_i$ and $p_j$ are distinct primes, then $p_i^{k_i}$ and $p_j^{k_j}$ are coprime, so Euler's totient function's multiplicativity applies to them.

1. $p_i$ and $p_j$ are distinct primes

2. $k_i$ and $k_j$ are positive integers

Holds for all indices $i \ne j$ corresponding to distinct prime factors.

1. Audio
   Observation

   The voiceover says, 'Clearly, we can enumerate every integer from 1 to 6,' then adds, 'By enumeration, we can easily see that only 1, 5, and 6 are coprime.'

2. Diagram
   Observation

   The screen first displays 'Which numbers from 1 to 6 are coprime to 6?', then lists '1 2 3 4 5 6', and finally shows the large number '2'.

1. Expression

   $$$$
   Explanation

   Pose a counting problem: find the integers coprime to 1 from 6 to 6.

   Justification

   At the beginning of the video, the question is stated directly: 'Which numbers from 1 to 6 are coprime to 6?'

   Shown in the video
2. Expression

   $$\gcd(a,6)=1$$
   Explanation

   For each candidate integer a, use the greatest common divisor to test whether a is coprime to 6.

   Justification

   The voiceover explains, 'If the greatest common divisor of this number and 6 is 1, then it is coprime to 6.'

   Shown in the video
3. Expression

   $$a\in\{1,2,3,4,5,6\}$$
   Explanation

   Enumerate all integers from 1 to 6.

   Justification

   The screen displays "1 2 3 4 5 6", and the voiceover says that each integer can be enumerated.

   Shown in the video
4. Expression

   $$\{1,5\}$$
   Explanation

   The numbers coprime to 6 are 1 and 5.

   Justification

   The voiceover explicitly states "Only 1, 5, and 6 are coprime."

   Shown in the video
5. Expression

   $$2$$
   Explanation

   The numbers coprime to 6 are exactly 2 in number.

   Justification

   The voiceover says "There are two numbers coprime to 6", and the screen finally displays the large number "2".

   Shown in the video

The integers from 1 to 6 that are coprime to 6 are 1 and 5, so the count of coprime numbers in this range is 2.

1. Audio
   Observation

   The narrator says, "Because all numbers from 1 to p except p itself are coprime to p, the numbers from 1 to p that are coprime to p are p minus 1."

2. Formula
   Observation

   The screen writes line by line: "Let P be a prime." "Therefore, among the numbers from 1 to P, there are $P - 1$ numbers coprime to P." "Therefore, $φ(P) = P - 1$."

1. Expression

   $$p\text{is a prime number}$$
   Explanation

   Let the object of study, p, be a prime.

   Justification

   Both the screen and the voiceover begin with "Let p be a prime."

   Shown in the video
2. Expression

   $$\forall a\in\{1,2,\ldots,p-1\},\ \gcd(a,p)=1$$
   Explanation

   The integers from 1 to p, excluding p itself, are all coprime to p.

   Justification

   The narrator says, "Because all numbers from 1 to p, except p itself, are coprime to p."

   Shown in the video
3. Expression

   $$p-1$$
   Explanation

   The number of integers a satisfying $1 \le a \le p$ and gcd(a, p) = 1 is $p - 1$.

   Justification

   There are p numbers from 1 to p; after excluding p itself, $p - 1$ remain.

   Shown in the video
4. Expression

   $$\varphi(p)=p-1$$
   Explanation

   The value of Euler's totient function at a prime is obtained from its definition.

   Justification

   $φ(p)$ is defined as the number of integers from 1 to p that are coprime to p.

   Shown in the video

If p is a prime, then $φ(p) = p - 1$.

1. Audio
   Observation

   The narrator says, "Moreover, since p is prime, among the numbers from 1 to p raised to the k-th power, all except the multiples of p are coprime to p raised to the k-th power," then says, "There are p raised to the ($k - 1$)-th power numbers not coprime to p raised to the k-th power," and finally says, "Subtracting the count of non-coprime numbers from the total gives the count of coprime numbers."

2. Formula
   Observation

   The screen displays: "All numbers from 1 to $P^k$, except multiples of P, are coprime to $P^k$." "From 1 to $P^k$, there are $P^{k-1}$ numbers not coprime to $P^k$." "∴ $φ(P^k) = P^k - P^{k-1}$."

1. The video does not explicitly specify the range of k; in the context of prime powers, k is conventionally understood to be a positive integer.

2. The video does not elaborate on the proof that "among the numbers from 1 to $p^k$, exactly $p^{k-1}$ are multiples of p."

1. Expression

   $$p\text{is a prime number}$$
   Explanation

   Continue using the previous definition of the prime number p.

   Justification

   The screen still displays "Let P be a prime number."

   Shown in the video
2. Expression

   $$\gcd(a,p^k)=1\ \Longleftrightarrow\ p\nmid a$$
   Explanation

   Among the numbers from 1 to $p^k$, all except the multiples of p are coprime to $p^k$.

   Justification

   The voiceover says: "Among the numbers from 1 to p raised to the k-th power, all except the multiples of p are coprime to p raised to the k-th power."

   Shown in the video
3. Expression

   $$p^{k-1}$$
   Explanation

   Among the numbers from 1 to $p^k$, there are $p^{k-1}$ numbers not coprime to $p^k$.

   Justification

   The screen displays "1numbers in P to the power k that are not coprime to P to the power k are P to the power k minus1 of them, and the voiceover explains this simultaneously.

   Shown in the video
4. Expression

   $$p^k-p^{k-1}$$
   Explanation

   The count of coprime numbers equals the total count $p^k$ minus the count of non-coprime numbers $p^{k-1}$.

   Justification

   The voiceover says: "Subtracting the count of non-coprime numbers from the total count gives the count of coprime numbers."

   Shown in the video
5. Expression

   $$\varphi(p^k)=p^k-p^{k-1}$$
   Explanation

   We obtain Euler's totient function formula for prime powers.

   Justification

   This follows from the definition of $φ(n)$ and the counting in the previous step.

   Shown in the video

If p is a prime and k is a positive integer as understood from context, then $φ(p^k) = p^k - p^{k-1}$.

1. Formula
   Observation

   The screen sequentially writes the prime factorization of n, $φ(n) = φ$($p_1^{k_1}$⋯$p_m^{k_m}$), splits it into a product, substitutes the prime power formula, factors out n, and expresses the result as a product notation.

2. Audio
   Observation

   The voiceover explains step by step: "Since Euler's totient function is multiplicative," "it can thus be split into this long product," "then we rearrange and factor out common terms," "and finally simplify using product notation."

1. Expression

   $$n=p_1^{k_1}\cdot p_2^{k_2}\cdot p_3^{k_3}\cdots p_m^{k_m}$$
   Explanation

   First write the positive integer n as a product of powers of distinct primes.

   Justification

   The prime factorization form directly given in the video.

   Shown in the video
2. Expression

   $$\varphi(n)=\varphi(p_1^{k_1}\cdot p_2^{k_2}\cdot p_3^{k_3}\cdots p_m^{k_m})$$
   Explanation

   Substitute the factorization of n into $φ(n)$.

   Justification

   Substitution of equal quantities.

   Shown in the video
3. Expression

   $$\varphi(n)=\varphi(p_1^{k_1})\cdot\varphi(p_2^{k_2})\cdot\varphi(p_3^{k_3})\cdots\varphi(p_m^{k_m})$$
   Explanation

   Split the expression of φ applied to a product into the product of φ-values at each prime power.

   Justification

   Use the multiplicativity of Euler's totient function; powers of distinct primes are pairwise coprime.

   Shown in the video
4. Expression

   $$\varphi(n)=(p_1^{k_1}-p_1^{k_1-1})\cdot(p_2^{k_2}-p_2^{k_2-1})\cdots(p_m^{k_m}-p_m^{k_m-1})$$
   Explanation

   Apply the earlier formula $φ(p^k) = p^k - p^{k-1}$ to each prime power.

   Justification

   The video refers to "the second case involving primes."

   Shown in the video
5. Expression

   $$\varphi(n)=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_m}\right)$$
   Explanation

   Factor $p_i^{k_i}$ out of each term $p_i^{k_i} - p_i^{k_i-1}$, leaving $1 - 1/p_i$.

   Justification

   Algebraic factorization: $p_i^{k_i} - p_i^{k_i - 1} = p_i^{k_i}(1 - 1/p_i)$.

   Shown in the video
6. Expression

   $$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_m}\right)$$
   Explanation

   Recognize the product of the extracted prime powers back as n.

   Justification

   from the first step $n=p_1k$ sub1p sub2k sub2dot dot dot p sub m to the power k sub m.

   Shown in the video
7. Expression

   $$\varphi(n)=n\prod_{i=1}^{m}\left(1-\frac{1}{p_i}\right)$$
   Explanation

   Compress all factors corresponding to prime factors using product notation.

   Justification

   Definition of product notation.

   Shown in the video

Obtain the general formula for Euler's totient function for any positive integer n: $φ(n) = n \prod _{i = 1}^m (1 - 1/p_i)$.

1. Audio
   Observation

   The voiceover asks: "So how many numbers from 1 to 100 are coprime to 100?" Then it says: "Leonhard Euler proposed an algorithm: multiply 100 by 1 over 2, then by 4 over 5, yielding 40."

2. Formula
   Observation

   The screen displays: "How many numbers from 1 to 100 are coprime to 100?" and "$φ(100) = 100 \times 1 / 2 \times 4 / 5 = 40$".

3. Diagram
   Observation

   The screen is filled with a numeric array from 1 to 100, and a portrait of Leonhard Euler appears.

1. The video does not explain in this segment1 and2 and4 and5 come from which prime factors of100 nor does it provide an enumeration verification process.

Find how many integers from 1 to 100 are coprime to 100.

1. The range is from 1 to 100.

2. The target number is 100.

3. The video gives Euler's algorithm: $φ(100) = 100 \times 1 / 2 \times 4 / 5$.

Calculate the number of integers coprime to 100.

1. Expression

   $$\varphi(100)=?$$
   Explanation

   Reformulate the problem as computing Euler's totient function $φ(100)$.

   Justification

   The voiceover defines $φ(n)$ as the count of numbers coprime to n among the integers from 1 to n.

   Derived from the video
2. Expression

   $$\varphi(100)=100\times\frac12\times\frac45$$
   Explanation

   Perform the multiplication calculation using the Euler algorithm provided in the video.

   Justification

   The screen displays the formula directly, and the voiceover simultaneously reads: "Multiply 100 by 1, divide by 2, multiply by 4, divide by 5."

   Shown in the video
3. Expression

   $$=40$$
   Explanation

   The result is 40.

   Justification

   The screen shows the equation ending with 40, and the voiceover says: "yields 40."

   Shown in the video

40

The video states, "When you enumerate them, you are surprised to find that this is actually correct," but this segment does not show actual enumeration-based verification.

1. Diagram
   Observation

   The screen first displays the question: "Which numbers from 1 to 6 are coprime with 6?", then lists: "1 2 3 4 5 6."

2. Animation
   Observation

   The numbers are highlighted or recolored one by one, and finally the screen cuts to a large-sized number: "2."

1. The highlight color of some numbers varies slightly across frames and may not be consistently distinguishable, but its visual function is to mark the enumeration and filtering process.

1. Question text: "Which numbers from 1 to 6 are coprime with 6?"

2. Number sequence 1, 2, 3, 4, 5, 6

3. Result number 2

1. The number sequence appears one by one and is highlighted, indicating checking each integer from 1 to 6.

2. At the end of the animation, a large numeral 2 indicates the count of integers satisfying the condition.

1. The enumeration range is always from 1 to 6.

2. The criterion is given in the voice-over: the greatest common divisor with 6 equals 1.

This animation concretizes the abstract $φ(6)$ counting process as checking each integer from 1 to 6 one by one, and highlights the resulting count as 2.

1. Diagram
   Observation

   The screen displays the question: 'How many integers from 1 to 100 are coprime to 100?', followed by a grid of numbers spanning from 1 to 100.

2. Animation
   Observation

   A portrait of Leonhard Euler appears and moves to the upper-left corner, then the formula $φ(100)=100\times 1/2\times 4/5=40$ appears.

1. Number array from 1 to 100

2. Portrait of Leonhard Euler

3. Formula $φ(100)=100\times 1/2\times 4/5=40$

1. The number array expands from a local view to the full range from 1 to 100, emphasizing that brute-force enumeration is infeasible.

2. After Euler's portrait appears, the screen shifts to the multiplicative formula and gives the result 40.

1. The object of interest is always 100.

2. The counting range is always from 1 to 100.

Visually, a dense array of numbers illustrates the enumeration cost; then Euler's portrait and the multiplication formula introduce a more efficient method for computing $φ(100)$.

1. Formula
   Observation

   Text appears line by line: 'Let P be a prime', '∴ $φ(P) = P - 1$', 'The numbers from 1 to $P^k$ that are not multiples of P are all coprime to $P^k$', '∴ $φ(P^k) = P^k - P^{k-1}$'.

2. Animation
   Observation

   The text appears line by line in order of derivation, with Euler's portrait remaining in the upper-left corner.

1. Euler's portrait

2. Prime assumption text

3. The Euler totient function value of P equals P minus 1

4. Text related to $P^k$

5. The Euler totient function value of P raised to the k-th power equals P raised to the k-th power minus P raised to the (k minus 1)-th power

1. The screen advances from the prime case to the prime-power case.

2. Each row's conclusion builds layer by layer upon the previous row's conclusion.

1. The object of discussion remains the prime p and its powers $p^k$.

2. The definition of Euler's totient function remains unchanged.

This visual process organizes the proof into line-by-line chalkboard writing: first obtaining the formula at primes, then deriving the formula at prime powers by excluding multiples of p.

1. Formula
   Observation

   The screen displays "Fundamental Theorem of Arithmetic: If n is a positive integer greater than 1, then $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}$."

2. Animation
   Observation

   The formula appears character by character, with Euler's portrait still in the upper-left corner.

1. Title: "Fundamental Theorem of Arithmetic"

2. The condition text reads: "If n is a positive integer greater than 1."

3. Factorization expression: $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$

1. The formula unfolds step by step from the title and condition to the full product form.

1. The range condition for n remains that n is a positive integer greater than 1.

2. The expression takes the form of a product of prime powers.

The visual prepares tools for the general integer case: first factor any $n > 1$ into a product of prime powers.

1. Animation
   Observation

   The formula appears line by line and expands downward; earlier lines fade out, leaving only the final formula.

2. Diagram
   Observation

   Approximately 39 seconds later, the part $p_{1}^{k_{1}} \cdots p_m^{k_m}$ is highlighted in red, indicating that it equals n.

1. Prime factorization expression

2. Product expansion of φ

3. Substitution expression for prime powers

4. Expression after factoring out n

5. Final product formula

1. The formula builds row by row, starting from the prime factorization of n.

2. The red highlight marks $p_1^{k_1}$⋯$p_m^{k_m}$.

3. The final formula is emphasized with a yellow box.

4. Intermediate steps fade out afterward, leaving only the conclusion.

1. The portrait in the upper-left corner remains visible throughout.

2. The main derivation thread is always an equivalent transformation of the same $φ(n)$ expression.

The visual layout emphasizes that each step is an equivalent rewriting of $φ(n)$, and highlights the key observation: "the red part equals n", which bridges the expanded form back to $n\prod (1-1/p_i)$.

1. Audio
   Observation

   The voiceover says, "I bet someone in the live chat will say, 'That's easy—just enumerate them one by one!' But that would still be too operationally intensive."

2. Diagram
   Observation

   The screen displays an array of numbers from 1 to 100.

Faced with counting how many numbers between 1 and 100 are coprime to 100, assumes one can enumerate them one by one, just as for the range from 1 to 6.

The video illustrates that enumerating one by one is "too operationally intensive" using a dense array of numbers from 1 to 100, then introduces Euler's totient function and the multiplicative algorithm.

1. Formula
   Observation

   Before stating φ(nm) = $φ(n)\cdot φ(m)$, the screen first writes gcd(n, m) = 1.

One might mistakenly assume φ(nm) = $φ(n)φ(m)$ holds for all n and m.

The video explicitly writes the condition as gcd(n,m)=1, indicating that this multiplicative splitting is used only in the coprime case.

1. Audio
   Observation

   First, "having greatest common divisor 1" explains being coprime to 6; then $φ(n)$ is defined as the count of integers from 1 to n that are coprime to n.

2. Formula
   Observation

   The visual transitions from enumerating numbers from 1 to 6 to displaying "$φ(n)$: the count of integers from 1 to n that are coprime to n."

The counting object of Euler's totient function is determined by "coprimality", and the video defines coprimality via greatest common divisor equal to 1; thus, this criterion is a prerequisite concept for understanding $φ(n)$.

1. Formula
   Observation

   The visual first gives the definition of $φ(n)$, then writes $φ(P) = P - 1$ under the assumption that P is prime.

2. Audio
   Observation

   The narrator first defines $φ(n)$, then says, "Let's begin studying the properties of Euler's totient function with simple prime numbers."

The conclusion $φ(p) = p - 1$ relies on the counting definition of $φ(n)$: first identify which numbers from 1 to p are coprime to p, then count how many there are.

1. Formula
   Observation

   The screen adds a line about $p^k$ to the existing statements "Let p be a prime" and "$φ(p) = p - 1$."

2. Audio
   Observation

   The narrator says, "Also, because p is prime, the numbers from 1 to p raised to the k-th power..."

The prime power formula generalizes the prime case from p to $p^k$, still excluding non-coprime numbers by focusing on multiples of the prime p.

1. Formula
   Observation

   The screen first displays $φ(100) = 100 \times 1 / 2 \times 4 / 5 = 40$, then shows "Euler's totient function $φ(n)$" and its definition.

2. Audio
   Observation

   The narrator first asks how many numbers from 1 to 100 are coprime to 100, then defines $φ(n)$.

The example $φ(100)$ is a concrete application of the definition of Euler's totient function: counting the integers from 1 to 100 that are coprime to 100.

1. Audio
   Observation

   The narrator says, "For the general case, things become somewhat more complicated; I will first introduce two important properties. The first is the fundamental theorem of arithmetic."

2. Formula
   Observation

   The screen then displays $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$.

1. This segment introduces only the fundamental theorem of arithmetic, without showing how it is further used in the general formula for $φ(n)$.

The video presents the fundamental theorem of arithmetic as a prerequisite tool for handling Euler's totient function for general integers n, although this segment does not yet complete the subsequent derivation.

1. Audio
   Observation

   The voiceover says, "Since Euler's totient function is multiplicative... it can be split into this large product."

2. Formula
   Observation

   The on-screen expression changes from $φ(p_1^{k_1}\cdot \cdot \cdot p_m^{k_m})$ to the product of all $φ(p_i^{k_i})$.

Multiplicativity is the justification for splitting $φ(n)$ into multiple prime-power factors according to its prime factorization.

1. Audio
   Observation

   The voiceover says, "Plug in our second case—the prime-power case."

2. Formula
   Observation

   Each $φ(p_i^{k_i})$ on screen is replaced by $p_i^{k_i}-p_i^{k_i-1}$.

Deriving the general formula relies on the prime-power case formula as a substitution module.

1. Formula
   Observation

   The screen first displays the prime factorization of n, then highlights $p_1^{k_1}\cdot \cdot \cdot p_m^{k_m}$ as n.

Prime factorization provides the sources of n and all $p_i$ appearing in the formula.

1. Formula
   Observation

   The screen displays "$φ(n)$: the number of integers between 1 and n that are coprime to n."

2. Audio
   Observation

   The voiceover says, "We define $φ(n)$ as the number of integers between 1 and n that are coprime to n."

1. Definition of Euler's totient function $φ(n)$
2. Coprime status is determined by the greatest common divisor.

1. Audio
   Observation

   The voiceover says, "If the greatest common divisor of this number and 6 is 1, then it is coprime to 6."

1. Coprime status is determined by the greatest common divisor.

1. Formula
   Observation

   The screen displays "∴ $φ(P) = P - 1$."

2. Audio
   Observation

   The voiceover explains that all numbers from 1 to p, except p itself, are coprime to p.

1. Euler's totient function evaluated at a prime
2. Definition of Euler's totient function $φ(n)$

1. Formula
   Observation

   The screen displays "∴ $φ(P^k) = P^k - P^{k-1}$."

2. Audio
   Observation

   The voiceover says, "Subtracting the count of non-coprime numbers from the total count gives the count of coprime numbers."

1. Euler's totient function formula for prime powers
2. $φ(p^k)$ is derived from the count of multiples of p in prime powers.

1. Formula
   Observation

   The screen displays "$φ(100) = 100 \times 1 / 2 \times 4 / 5 = 40$."

2. Audio
   Observation

   The narrator asks how many numbers from 1 to 100 are coprime to 100, and gives the result 40.

1. This segment does not explain the origins of $1/2$ or $4/5$.

1. Compute $φ(100)$ using Euler's multiplication method.
2. Definition of Euler's totient function $φ(n)$

1. Formula
   Observation

   The screen displays "Fundamental Theorem of Arithmetic: If n is a positive integer greater than 1, then $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}$."

1. Fundamental Theorem of Arithmetic

1. Audio
   Observation

   The voiceover explains, "Since Euler's totient function is multiplicative, and since the $p_i$ are pairwise coprime, it can be split into this large product."

1. The multiplicativity of Euler's totient function
2. Powers of distinct primes are pairwise coprime
3. Deriving the general formula for Euler's totient function from the prime factorization.