Fermat's (Euler) Theorem: The Old Math behind modern eCommerce

The bizarre theorem proposed by Fermat in 1640, and proven almost 100 years later by Euler, as a non-applicative gem of pure math, has been dusted off by modern cryptography, and is now exploited in powerful protocols that enable the miracle of cyber commerce. Looking back the proof is so simple, one wonders why it took so long? Is there more math insight there -- that we don't see, but our adversaries do?

[@christianvazquez1910]

Great lecture! This proof helped me understand why it worked and was not hard to grasp.

[@GideonTheTeacher]

thank you Christian, keeps me going!

[@chandanamr]

I'm in 8th grade preparing for invitational mathematics exam. this was a great explanation that clarified one of the more confusing topics

[@GideonTheTeacher]

8th grade! you will go far!

[@user-nm1so7gq7u]

This is the video I was looking for. Feel so lucky that I found this. Thank you for your effort!

[@mehnot4619]

Nice video, very simple and elegant. One thing I'd like to notice is that in the last step, you can cancel out the r.sub(i) on both sides since all of them and n are coprimes, gcd(n,r.sub(i))=1 for all i, and that allows a multiplicative modular inverse to exist. Better be careful with canceling out factors carelessly in modular equations! The fact that this is allowed by the definition of the terms themselves is, in my humble opinion, what makes this proof so elegant.

[@ivanchachkov6619]

Thank you for the great explanation!!! Most videos on youtube do not go that deep.

[@whitewalker608]

That's amazing. Thanks for this. KZbin needs such videos!

[@GideonTheTeacher]

Thanks White, will try to find time to post some more.

[@GideonTheTeacher]

Thank you White Walker for your encouragement!

[@jensbergman6123]

Great video. Really easy to understand on an important theorem. Keep up the good work! :)

[@GideonTheTeacher]

Thanks for commenting, sorry for the late reply. There is beauty there, isn't it?

[@alpozen5347]

amazing sir! thank you for the effort

[@GideonTheTeacher]

appreciate your comment!

[@dannys2817]

Excellent explanation Sir ,

[@GideonTheTeacher]

Thanks, hope you enjoy other videos too

[@prajnaprajna1923]

Sir.Leonhard Euler and Sir Andrew Wiles solve Fermat's last theorem too length . This method is extremely short that is in 7,8 lines Combine two formulas to solve Flt case n=3. first formular Sx=1^2+2^2+3^2+....+x^2=(2x^3+3x^2+x) / 6. so (x^2+y^2-z^2)=(x^2+y^2-z^2)=[3Sx+3S(x-1)+3Sy+3S(y-1)-3Sz-3S(z-1)]^2+(2xy-2zx-2zy+3z^2). And second formular (equality formular) (x^2+y^2-z^2)=(x+y-z)^2+(2xy-2zx-2zy+3z^2) Compare two equations and suppose x^3+y^3=z^3 with x.y.z are integers. So x={6zx+6zy+(6Sx+6Sy-6Sz) - 3.[3Sx+3S(x-1)+3Sy+3S(y-1)-3Sz-3S(z-1)]^2-9z^2} / 6y Paradox.

[@poonamsing1]

very clear, excellent explanation professor. Thanks !

[@GideonTheTeacher]

thanks!

[@momedalhouma14]

we hope that you can add more videos.

[@premktiw4984]

SUPER SUPER SUPER Brilliant video !! By the way when you say at 6:43 . How do you give arguments in support of the fact that a and b being co-prime to n, the remainder of a*b with n has to be co-prime to n ?? I think following should work, what are your opinions ?? Assume a,b to be co-prime with n. Now a*b = r mod n, and r has to be co-prime with n. if this is not true, i.e. r is not co-prime with n, then for some value of K, you can write that a*b = K*n + r, and then suppose the common factor between n and r is c(because r and n are no more co-prime), then you can re-write the expression as. a*b = c*(K*(n/c) + r/c), and now I have c which is a factor of n, and hence the RHS is not co-prime to n, but LHS is, which is not possible, hence :) !!

[@MrEyee2]

prem tiwari I found this proof helpful. Proofs by contradiction are often elegant and this is no different. The video delivery was awesome too. Thanks to you and the author.

[@juanmanuelguerrero9788]

After viewing your video and trying to understand it better, I found that the equation a^(phi(n)+1) = a mod n is always fulfilled for any 'a' inclduing those values which gcd(a,n) is different to 1. Am I right? Thank you for this beautiful explanation.

[@GideonTheTeacher]

+Juan Manuel Guerrero Yes. because then a*r = 0 mod n, r=a^ph(n)-1

[@prajnaprajna1923]

I use the infinity to prove Fermat, mathematicians do not like infinity because it is so broadly and ambiguous to define.Here Fermat give one condition , however , follow my analizing in this case will be transformed into infinite condition and they different. Suppose x^n+y^n=z^n. define n=2a x^a+y^a=z^a+d (x^a+y^a)²=(z^a+d)² x^n+y^n+2x^a.y^a=z^n+d²+2z^a.d because x^n+y^n=z^n so 2x^a.y^a=d²+2z^a.d Named x^a+y^a=S and x^a.y^a=P P=(d²+z^n.d) / 2 Because P is integer so condition is (d²+z^n.d) =2k define n=3b x^b+y^b=z^b+m Named x^n+y^n=S and x^n.y^n=P ( x^b+y^b) ^3=(z^b+m)³ x^n+y^n+3SP=z^n+m³+3(z^b.m)(z^b+m) Because x^n+y^n=z^n so 3SP=m³+3(z^b.m)(z^b+m) Because SP is integer so condition is [m³+3(z^b.m)(z^b+m)] =3K define n=4c x^c+y^c=z^c+v (x^c+y^c)⁴=(z^c+v)⁴ (x^c)⁴+4(x^c)³.(y^c)+6(x^c)².(y^c)²+4(x^c).(y^c)³+(y^c)⁴=z^n+4(z^c)³v+6(z^c)².v²+4(z^c)v³+v⁴ Because x^n+y^n=z^n 4(x^c)³.(.y^c)+6(x^c)².(y^c)²+4(x^c).(y^c)³=4(z^c)³v+6(z^c)².v²+4(z^c)v³+v⁴ 4(x^c)³.(.y^c)+6(x^c)².(y^c)²+4(x^c).(y^c)³ - [6(z^c)².v²+4(z^c)v³+v⁴] =4(z^c)³v { 4(x^c)³.(.y^c)+6(x^c)².(y^c)²+4(x^c).(y^c)³ - [6(z^c)².v²+4(z^c)v³+v⁴] } / [4(z^c)³] = v because v is integer so { 4(x^c)³.(.y^c)+6(x^c)².(y^c)²+4(x^c).(y^c)³ - [6(z^c)².v²+4(z^c)v³+v⁴] } = [4(z^c)³] K Similar , sequence continue infinite: define n=5r, define n=6g, define n=7u, define n=8f ,…….. so appear unlimited conditions that necessary according. Wow! too many conditions. I can’t suffer anymore Let me be king, I must give up

[@hasan0770816268]

Hell yeah dude

[@vidajohn2199]

Thank you!

[@sissi.64]

Nice explanation.

[@GideonTheTeacher]

Thanks... it is truly amazing that it remained hidden for 100 years!

[@jason.mullings]

Euler's Theorem is incomplete...!

[@user-bw4ub4rg4s]

Thank you iam undrstand the theorm