Euler's Totient Function -- Number Theory 13

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

[goodplacetostop]

34:54 End of example left for the viewer
35:00 Homework
35:25 Good Place To Stop

[charlottedarroch]

φ(n) = 8 iff n is in {15, 16, 20, 24, 30}. The case of φ(n) = 10 is easier. If prime p|n and φ(n) = 10, then (p-1)|10, so p is in {2, 3, 11}. The formula for phi(n) can be expressed n = phi(n)*Product[p/(p-1), primes p]. But φ(n) = 10 is divisible by 5 and n = 2^a 3^b 11^c is not. So we must have that 5|(p-1) for a prime dividing n, so we must have that 11|n. Therefore we need only check the four cases for whether or not a and b are zero. Two of these give solutions and we obtain that φ(n) = 10 iff n is in {11, 22}.

[iabervon]

I don't think you need as much work in cases for the example. If 3^2 or 5^2 divides n, phi(n) is a multiple of 3 or 5, and 8 is not. So b and c are each 0 or 1, and you just have to pick the appropriate power of 2 to finish each case.

[weisanpang]

At 10:00, whoever wonders why the a's term on the LHS is multiple of m, and the b's term on RHS is multiple of n :
a*n congruent b*m (mod m*n)
-> a*n - b*m = (m*n) * k, k = some integer. This is the defn of congruence relation.
-> a*n/(m*n) - b*m/(m*n) = k
-> a/m - b/n = k
-> a needs to be multiple of m and b needs to be multiple of n in order for the LHS to result in integer.

[elias_toivanen]

Impressive stuff! You have an enviable determination to improve your craft.

[AliKhanMaths]

I've never heard of this function before, woah! Videos like yours inspire me to share my own maths content!

[eliapini]

You could as well consider the isomorphism between Zn x Zm and Znm in order to demonstrate the multiplicative property. This tell us that they have the same number of invertible elements and (a, b) is invertible iff a and b are invertible, so Φ(nm)=#{(a, b)|gcd(a, n)=1 and gcd(a, m)=1}=Φ(n)Φ(m).

[rbnn]

Let R be the pairs (x, y) where x is in Z_m and y in Z_n under coordinatewise addition and multiplication. The map f:Z_mn—>R that sends z into (z mod m, z mod n) is injective since m and n are coprime. Hence f is an isomorphism by counting. The units in Z_m (the invertible elements) are the phi(m) numbers coprime to m. Similarly with Z_n. Since the units in R are the pairs (u, v) where u is a unit of Z_m and v of Z_n, the number of units in R is phi(m)phi(n). Because Z_mn and R are isomorphic, they have the same number of units, so phi(m)phi(n)=phi(mn).

[freecky]

Great Video! However, I would like to point out a possible confusion. At around 10:00, you're explain that the m on RHS implies LHS is divisible by m. That is only true because you're doing mod mn. Of course, for people who is familiar with number theory, we would notice this being the needed criterion. However, as this video is targeting people who aren't familiar with this topic, I believe that doing such deduction without saying that it is base on the fact that we're doing mod mn might cause confusion for audience. Aside from that, great video as always!

[aboodahmad]

I have question,
Why when prove S={a(j)n+b(s)m|0<j<phi(m)+1 and 0<s<phi(n)+1} is rrs module mn isn't prove that phi(mn)=phi(m)phi(n)

[naringrass]

so what's the complex numer version of Euler's Totient function?

[weisanpang]

18:20, for gcd(cy, m)=1, you said cy is congruent to a_j (mod m) where a_j is from the reduced residue set of m. For this statement, i cannot find any of your previous video explain that. All you video said was if gcd(a, n)=1, then ax=b(mod n) has exactly one solution. It never said b and n must be coprime as well. Please consider some rigor in your explanation, quite frustrating.

[chrisys]

How come this kind of factoring is allowed at 25:12 with natural numbers? Even if the result is a natural number, wouldn’t 1/p not make sense?

[JM-usfr]

It’s probably easier to prove multiplicativity directly; that is, representing phi as a sum of 1’s for each coprime number. Then just multiply it out, and analyse some facts about divisors, and viola!

[士-xe]

Showing convolution of two multiplicative functions becomes also multiplicative is difficult?
(Convolution f*g(n)=sum of f(d)g(n/d) (d devides n))

[megauser]

The other 2 solutions to phi(n) = 8 are n = 20 and n = 30,
when a=2, b=0, and c=1, or a=b=c=1, respectively.

[yuseifudo]

i really love your videos...you are a living legend :)

[sergpodolnii]

b_{s} is the best name for a variable :)

[briandennehy]

Euler the greatest mathematician of all time??

[MYSBRZ]

Hello Michael, just awesome, just awesome, hey you are unique🙋‍♂️ why are u so good in math learning?