Euler's Theorem Number Theory 12

⭐Support the channel⭐

⭐my other channels⭐

⭐My Links⭐

[JM-usfr]

A few interesting things about Euler’s Totient Function:

1) Obviously it’s a generalization of Fermat’s little Theorem, but it is also generalized by Lagrange’s Theorem for finite groups.

2) It’s used heavily in the classification theorem of those n for which there is a primitive root modulo n.

3) The fact that phi(n) is difficult to compute when n=pq for distinct primes p and q is key in making the RSA crypto-system secure.

4) Just a random fun fact, you can show the ABC conjecture is false for epsilon=0 by considering a=2^(6n)-1, b=1, and c=2^(6n), for any n.

5) Also, phi is bounded above by n-1 (which is attained for n prime) and approximately bounded below by cn/ln (ln(n)) (roughly attained when n is a primorial). The average growth of phi is 3n/pi^2.

[scp]

A key element of RSA cryptography. Thank you for your video.

[knok]

I believe you can shorten proof of gcd(n, a b_i) = 1, by directly applying proposition from gcd lecture: `gcd(a, b) = 1 and gcd(a, c) = 1 -> gcd(a, bc) = 1`

[fluppy]

If I remember correctly, you didn't even define what an inverse is in this course yet. Let alone profing that an inverse exists if gcd(x, n)=1, or am I wrong?

[JM-usfr]

These large exponent examples can also computed without Euler’s Theorem if you instead use modular exponentiation. It’s a fast algorithm for computing exponentiation when over a modulus.