@@panshuljetwani1726 after a year? interesting. But I believe (mod 53) in this context shows congruence between two numbers. It's like applying "mod 53" to a number, let's say "106 mod(53)" and "0 mod(53)" are both the same number under (mod 53), as when you divide both numbers by 53, you end up with 0. Hope i explained it properly, it is very early where I am.
Wow, thank you!! You've saved me. I now understand Fermat's little theorem for solving a^very large power. Your second example (3^100,000) was excellently explained.
@@Socratica hello, your example was beautifully explained, do you mind explaining how you simplified 81 in your second example? if you do have time to respond i would greatly appreciate it. thank you
Fermat's Little Theorem? More like "Fear not! It's a little theorem," after watching this Socratica video! Thanks for explaining this in such a great way!
Thanks for the video. I was like "this theorem is so easy", but wasn't sure how to apply it. Hopefully this helps with my Applied Cryptography final (well studying for)
mod 53 means if you divide something by 53, you get a remainder that is left over which is the number left over, in this case is 28. A simpler example of this would be 10 ≅ 3 (mod 7)
well, you can test some random number into the theorem a^(p-1)=1(mod p) for your case (458), you can try random a, like 2: is 2^(458-1)%p=1? if it yes, then your case *probably* is a prime, to make sure, you can test for another 'a' value.
@b10noa the two numbers you said are different by n*53 (where n =1 but that's irrelevant) so when divided the remainder is still the same regardless of the value of n as n does not effect the remainder
I prefer the more abstract proof which makes this theorem totally obvious, if you know basic group theory (which you should I think, being a student of mathematics). Although I of course understand why in this introduction the more barehands proof is given. Proof: What one wants is that g^{p-1} = 1, where g and 1 are considered elements of the finite group Z/pZ - {0}, with group operation given by multiplication. It's worth knowing, and not too hard to show, that this is a group (for which you need p is prime). But Z/pZ - {0} has p-1 elements (represented by 1,2,...,p-1), and it's an elementary fact that in any group G with n elements, g^n = identity element for any g in G. In our case, the identity element is 1 and n = p-1. QED So this comes down to basic group theory. The proof that g^n = id in any group of n elements goes something like this: first, k = "order of g" (the smallest n so that g^n = id is true) always divides n, since the elements g,g^2,g^3,...,g^k form a subgroup; subgroups are always of a size dividing n (Lagrange's Theorem. Basically, you need to know that the cosets are always the same size and partition the group). But then g^n = (g^k)^{n/k} = id^{n/k} = id, as required.
This is kind of a late response, but don't listen to ECard821. Modular arithmetic means you take the remainder of the division. 81 mod 53 means find the remainder of dividing 81 by 53 which is 28 (not the difference). Therefore, the only numbers you can have in mod 53 arithmetic is all the integers less than 53.=, [0-52].
Thanks for the video .. but why does Case 2 mean that each congruence class is included in the rearrangement? I mean, why couldn't it only be 1,2,4,7,8...p-1, skipping a few numbers.
When yoy explain it, I feel like I can understand this. But I have no idea how to put it to use. I'm making a program that can tell me if a number is a prime number, then I'm going to use that program in later programing. The easiest way to do this, is suposedly through Fermat's little theorem. I just don't see how I can put this to use. If I wanted to know if 458 is a prime number, how can I use Fermat's little theorem to determine that?
I like this! (Minor edit suggestion: I don't think you mean to say Case 1 and Case 2, since you're not saying that one or the other is the case. What you're saying is that both these things are true.)
Assume a has unique prime factors j,k. To compute phi(a) we first subtract all numbers upp to a that have j as a factor: a * (1 - 1/j). Finally, we subtract the numbers that have k as a factor: phi(a) = a * (1 - 1/j) * (1 - 1/k). For instance, phi(12) = 12 * (1 - 1/2) * (1 - 1/3). Assume a has unique prime factors m,n. By the same principle phi(b) = b * (1 - 1/n) * (1 - 1/m). If a and b are coprime, i.e j and k are different from n and m, then the unique prime factors of a*b are j,k,n,m. Thus phi(a*b) = (a * b) * (1 - 1/n) * (1 - 1/m) * (1 - 1/j) * (1 - 1/k). These can be rearranged to phi(a) * phi(b).
Join our 'axioms' mailing list to learn about new number theory videos: news.axioms.com/join
What does (mod 53) mean?
@@panshuljetwani1726 do you still require an answer to this question my friend?
@@FrancD Yeah I do
@@panshuljetwani1726 after a year? interesting. But I believe (mod 53) in this context shows congruence between two numbers. It's like applying "mod 53" to a number, let's say "106 mod(53)" and "0 mod(53)" are both the same number under (mod 53), as when you divide both numbers by 53, you end up with 0. Hope i explained it properly, it is very early where I am.
The simplest and easiest-to-understand proof I have ever seen. Thank you!!!
Wow, thank you!! You've saved me. I now understand Fermat's little theorem for solving a^very large power. Your second example (3^100,000) was excellently explained.
Best explanation of this theorem I've seen on RUclips, thank you.
I'm not sure if you're not just showing off your keyboard shortcut prowess in this video ._.
If I would have have such nice mentor like you , I would have broken down USMO easily.
That proof was so nice, huge thanks to you :)
l have exam tomorrow and now i am finally fine with this part.. Thank you so much for your help i am so glad 🙏🙏
Great and clear explanation of the proof! Thank you
best available video on Euler theorem
keep it up
You Open My Eyes... Great One!
You explained this so clearly and calmly, thank you!
We're so glad you are watching! Thanks for your nice message. 💜🦉
@@Socratica hello, your example was beautifully explained, do you mind explaining how you simplified 81 in your second example? if you do have time to respond i would greatly appreciate it. thank you
Fermat's Little Theorem? More like "Fear not! It's a little theorem," after watching this Socratica video! Thanks for explaining this in such a great way!
I love this! I’ve seen similar proofs of Fermat’s Little Theorem before, but this explanation really clicked!
best explanation period.
Thanks for having a nice teacher
Thanks for the video. I was like "this theorem is so easy", but wasn't sure how to apply it. Hopefully this helps with my Applied Cryptography final (well studying for)
Great video! Could you expand on Number Theory at all?? Currently trying to grasp the concept of the Euler Totient Function and the RSA Method D:
We're so glad you found our video helpful, Shaquille Mayers! We definitely want to make more Number Theory videos - it's one of our favourite topics!
The presentation is so neat! What program did you use to type the math?
Very nicely done.
So much better than by those who scribble on bits of paper
You are my hero!!! Saved my life .
could anybody explain to me at 4:17 how he did the simplification to get 28 ?? please
It's mod 53..which means the remainder which is left after dividing by 53..so, 81mod53 is remainder of 81/53 which is 28!
+Š П ł P Σ Г 81=53+28 since 53 congruent to 0 (mode 53) then 81 congruent 0+28 (mode 53) so it s 23 mode 53
mod 53 means if you divide something by 53, you get a remainder that is left over which is the number left over, in this case is 28. A simpler example of this would be 10 ≅ 3 (mod 7)
yes you are right
Well... 28, not "28!" haha :)
Beautiful proof presented in a beautiful manner !
How did you simplify 81? Thank you. This video is helpful btw
Since 0 ≡ 53 mod53
3^100,000 ≡ 81 mod53
If we substract 0 ≡ 53 mod53 from 3^100,000 ≡ 81 mod53 ;
we get 3^100,000 ≡ (81-53) mod53
@@yarenkaya7872 was wondering as well. Thank you
@@arthurjacques5721 Np
well, you can test some random number into the theorem
a^(p-1)=1(mod p)
for your case (458), you can try random a, like 2:
is 2^(458-1)%p=1?
if it yes, then your case *probably* is a prime, to make sure, you can test for another 'a' value.
youu explanation is really wonderful
"not elementary enough." - Richard Feynman.
The nicest proof I have ever seen ❤️.
Great video! Wish my professor would stop and use visual aids for his lectures.
I don't think visual Aids is healthy.
@b10noa the two numbers you said are different by n*53 (where n =1 but that's irrelevant) so when divided the remainder is still the same regardless of the value of n as n does not effect the remainder
Thank you for this amazing video .
Holy, this little theorem is powerful as hell
excellent video;Thank you!
How can you prove the "trick" at 5:30? How woud we prove that it always works? Could anyone help me here?
Beautifully explained
One of better explanations! Thanks
Great, you make it look so simple
Wow, excellent explanation of the proof.
I would just say , Thank you.
so easy to understand, thanks
Great explanation. Thanks!
Really great video !!
Helped me to understand the proof!
Thanks for the video!
very nice presentation
Great video, thanks!
on 3:31 what if the quotient = 0 ? what you do?
Excellent stuff
I prefer the more abstract proof which makes this theorem totally obvious, if you know basic group theory (which you should I think, being a student of mathematics). Although I of course understand why in this introduction the more barehands proof is given.
Proof: What one wants is that g^{p-1} = 1, where g and 1 are considered elements of the finite group Z/pZ - {0}, with group operation given by multiplication. It's worth knowing, and not too hard to show, that this is a group (for which you need p is prime). But Z/pZ - {0} has p-1 elements (represented by 1,2,...,p-1), and it's an elementary fact that in any group G with n elements, g^n = identity element for any g in G. In our case, the identity element is 1 and n = p-1. QED
So this comes down to basic group theory. The proof that g^n = id in any group of n elements goes something like this: first, k = "order of g" (the smallest n so that g^n = id is true) always divides n, since the elements g,g^2,g^3,...,g^k form a subgroup; subgroups are always of a size dividing n (Lagrange's Theorem. Basically, you need to know that the cosets are always the same size and partition the group). But then g^n = (g^k)^{n/k} = id^{n/k} = id, as required.
this is awesome. thanks so much!
Thank you!
Very clear, thank you!
Where did the 28 come from?
You are One amazing Dude. thanks man
Woww👌
Thanku so muchh man
what an explanation and presentation !
It's just wowww🔥🔥🔥🔥🔥
At 6:58 why can we say r < p?
If I'm not wrong, I think it's because "r" is any one of the non-zero congruence classes of p
This is kind of a late response, but don't listen to ECard821. Modular arithmetic means you take the remainder of the division. 81 mod 53 means find the remainder of dividing 81 by 53 which is 28 (not the difference). Therefore, the only numbers you can have in mod 53 arithmetic is all the integers less than 53.=, [0-52].
2 problems:
1. how does 81(mod 53) simplify to 28(mod 53)
2. you cannot check if your correct, since calculators cannot calculate such high numbers
Yeah that's why we use these theorems
And 81=53+28 so it's pretty evident
Great video, thanks
how did u get from 81(mod 53) to 28(mod 53)
Great! Thanks
Best explanation!
Thanks so much!
Very helpful.
THANK YOU!
Thanks for the video .. but why does Case 2 mean that each congruence class is included in the rearrangement? I mean, why couldn't it only be 1,2,4,7,8...p-1, skipping a few numbers.
easy explained - thanks a lot.
wow, really excellent video! What program are you using that allows you to input math symbols so quickly?
When yoy explain it, I feel like I can understand this. But I have no idea how to put it to use. I'm making a program that can tell me if a number is a prime number, then I'm going to use that program in later programing. The easiest way to do this, is suposedly through Fermat's little theorem. I just don't see how I can put this to use. If I wanted to know if 458 is a prime number, how can I use Fermat's little theorem to determine that?
I have same problem
what software did you use to write that sir?
Wait is this a different theorem or does the thumbnail actually claim A^P is A(modP)
This is helpful but, can you please explain where you the work.so it makes more sense.
where does 2 and 3 came from?
Could anyone explain to me why r
Because r is representing the congruence class from 1 to (p-1). So r can't be greater or equal to p ... or what do you mean?
What a great explanation 👍👍👍💯
How did 3^10000=81(mod53) convert into
3^10000=28(mod53)
Please answer someone
thank you my professor assumes we know everything
Excellent 😃
Thank you very much for the proof. It is well presented.
it can also be proved by induction with binomial theorem
Hi bro what is the mean of 5(idk what symbol is it)2 .plz someone explain❤
What a great lecture 💯💯
Thanks 😊😊
Thanks ma dude
What does (mod 53) mean?
I like this!
(Minor edit suggestion: I don't think you mean to say Case 1 and Case 2, since you're not saying that one or the other is the case. What you're saying is that both these things are true.)
What if I have 2^17 congruent to mod 23
Where can I go find out what "a divides b" means because that makes no sense.
It just means that a is a factor of b
What program is this? It really helped a lot, thanks!
also, what is congruent in the context
I wish I saw this video back at university sigh
How do you know that r-s not equal to 0?
Thanks alot
FOR THOSE LOST ON HOW HE CONVERTED 81 TO 28, HE SIMPLY SUBTRACTED 53 FROM 81 SINCE IT'S A MODULO
What did you use to simplify 3^(100,000) congruent to 81 (mod 53) to 3^(100,000) congruent to 28 (mod 53).
Since 0 ≡ 53 mod53
3^100,000 ≡ 81 mod53
If we substract 0 ≡ 53 mod53 from 3^100,000 ≡ 81 mod53 ;
we get 3^100,000 ≡ (81-53) mod53
nice way to explain proof
why 3^52 = 1 (mod 53) can imply (3^52)^1923 = 1^1923 (mod 53)?
very nice proof; never seen it before
I really want to know how you simplified 81 to 28????
So, 81=53*1+28
Thank you!
Thanks
thanks a lot
Thank you for your excellent explanation of the proof! My request: a proof that the Euler function is multiplicative: phi(ab)=phi(a)*phi(b).
Assume a has unique prime factors j,k. To compute phi(a) we first subtract all numbers upp to a that have j as a factor: a * (1 - 1/j). Finally, we subtract the numbers that have k as a factor: phi(a) = a * (1 - 1/j) * (1 - 1/k). For instance, phi(12) = 12 * (1 - 1/2) * (1 - 1/3).
Assume a has unique prime factors m,n. By the same principle phi(b) = b * (1 - 1/n) * (1 - 1/m).
If a and b are coprime, i.e j and k are different from n and m, then the unique prime factors of a*b are j,k,n,m. Thus phi(a*b) = (a * b) * (1 - 1/n) * (1 - 1/m) * (1 - 1/j) * (1 - 1/k). These can be rearranged to phi(a) * phi(b).