Euler's Theorem -- Number Theory 12

[@StarsManny]

I imagine the doctor applied the bandage all the way up to the fingertips and Michael said "that's a good place to stop"

[@trueriver1950]

It's even better to stop just before the finger tips: that's so you can check the colour and indirectly check blood flow is OK past the bandage.

[@thatkindcoder7510]

@@trueriver1950 So it was the doctor who said "That's a good place to stop..."

[@trueriver1950]

@@thatkindcoder7510 ;)

[@ey3796]

😂😂

[@wavyblade6810]

I think there's a similar, but sort of easier and quicker way to prove that ab_i and ab_j are incongruent mod n. After supposing the opposite, we in fact have n|a(b_i - b_j). But gcd (n,a)=1, so n does not divide a (I guess n=1 doesn't make sense). So n must divide b_i - b_j. And because 1

[@gustavoexel5569]

7:39 I think there's a way more straightforward way of proving this. Since gcd(a,n)=1, then ab_i≡ab_j (mod n) implies that b_i≡b_j (mod n). But because the original reduced residue system was incongruent, then b_i≡b_j (mod n) implies that i = j, and therefore ab_i≡ab_j (mod n) is only true when i = j.

[@eamon_concannon]

13:12 I think you need to prove that there is a bijection (of congruence) from the set {ab_1, ab_2,.....ab_ϕ(n)} to the set {b_1, b_2,.....b_ϕ(n)} where 1≤b_j≤n-1. For any 1≤i≤ϕ(n), we have ab_i=lmodn where 0≤l≤n-1. We need to show l=b_j for some j. gcd(ab_i,n) = 1 implies ab_ix+ny=1 for some integers x and y. ab_i - l =nq for some integer q, so ab_ix - lx= nqx ---> 1-ny - lx = nqx, --> n(qx+y)+lx=1, so gcd(l,n)=1 which means that l=b_j for some j. We have ab_i=b_jmodn. To show the mapping is a bijection, suppose BWOC that i≠k and ab_k=b_jmodn, then by transitive property of congruence, ab_i=ab_kmodn which is false. So mapping is 1-1 between sets of equal size, hence mapping is bijective.

[@jasonroberts2010]

The second step of proving the lemma took me a while to digest. From there though, the final proof jumped out at me and I gave a laugh of delight, shock, and wonder. Now that I understand this thing, I want to go back and watch your other videos using it and get that deeper understanding I need to start trying these questions before you answer them.

[@tonyhaddad1394]

All math lover think the same way , i always want to undertand math more deeply , when i miss a lemma or a step ... a feel the same way !!

[@Juniper-111]

I like how this also appears in elementary group theory. It falls out of Lagrange's theorem: x in U(n) has x^|U(n)| = 1 (mod n) since |x| divides |U(n)| = totient(n) where U(n) is the multiplicative group of integers mod n i.e. the group of integers less than and co-prime to n (the reduced residue system mod n).

[@SanketAlekar]

Exactly, love how group theory ties in nicely with it. The residues co prime to n form a multiplicative group modulo n.

[@KimHengTeo]

Using Euler theorem and CRT for finding 7^950 mod 100 is overkill. The simplest way is to observe that 7^4 = 1 mod 100. From there, we have 7^950=7^(4*237+2) = 7^2 = 49 mod 100

[@goodplacetostop2973]

23:11 Homework 23:50 Good Place To Stop

[@wojteksocha2002]

Why this comment was added 2 weeks ago??

[@goodplacetostop2973]

@@wojteksocha2002 I have a better question: why not? 😂

[@kemalkayraergin5655]

@@wojteksocha2002 we could predict that guy is paid by michael

[@resilientcerebrum]

@@kemalkayraergin5655 playlists are the key to success

[@2070user]

@@resilientcerebrum shut up is the key to secret

[@Heshmbdelgwd]

In the proof of the second part of the first lemma, you could just use the fact that ab is congruent to ac modulo n, if and only if b is congruent to c modulo n/g, where g is gcd(a, n), which would be 1 in this case.

[@thetheoreticalnerd7662]

the second part of proving the lemma is actually much easier: BWOC suppose ab_i = ab_j (mod n). Note that by assumption a is coprime to n, so a has an inverse mod n. Therefore, this would imply that b_i = b_j (mod n), a contradiction since it is a reduced residue system.

[@JM-us3fr]

Using an inverse is effectively the same as Bezout’s identity, the difference being the Bezout’s identity reminds the viewer of the mechanism for computing the inverse.

[@giampierogiancipoli7780]

The point at 13:19 is not clear. Why does it tell us that the product of all the members of a reduced residue system is the same modulo n for all the RRSs?

[@GhostyOcean]

The lemma states that for each 1≤i≤phi(n), ab_i = b_j for some unique 1≤j≤phi(n). So you have a *bijection* from the set of coprime residues to the same set. (Basically, the ab_i's make a rearrangement of the same set residues.) Therefore the product of ab_i's is congruent to the product of b_i's.

[@Vincent1971Tlse]

@@GhostyOceanThanks for your answer. I had the same question.

[@lemons107]

Sir, thank you very much for this course. Using it to pretty much teach myself number theory for university. I really appreciate it, it's a lot of fun and easy to follow!

[@RexxSchneider]

For warm-up, I suppose you want answers in the comments? (If not I can delete this) WU1: φ(15) = 15 . (3-1)/3 . (5-1)/5 = 8, so we have 8 members of the residue system: {1, 2, 4, 7, 8, 11, 13, 14} and similar such as {-7, -4, -2, -1, 1, 2, 4, 7}. WU2: 3^999,999,999 mod 7 - use FLT to get 3^6 ≡ 1 mod 7, so 3^999,999,999 = (3^6)^166,666,666 . 3^3 ≡ 3^3 mod 7 = 27 mod 7 ≡ 6 mod 7. Note that Euler's theorem gives 3^φ(7) ≡ 1 mod 7 and because 7 is prime φ(7) = 7-1 = 6 producing the FLT result. WU3: Last digit of 3^1000 is 3^1000 mod 10. Using ET, 3^φ(10) ≡ 1 mod 10 and φ(10) = φ(2).φ(5) = (1).(4) = 4. So 3^4 ≡ 1 mod 10 and hence 3^1000 = (3^4)^250 ≡ 1 mod 10. The last digit is 1. I do think it would have been helpful to have done some work on calculating φ(n) _before_ working on these sort of problems. Just knowing that φ(100) = φ(4).φ(25) would have been helpful to many, or that φ(n) = n times the product of (p-1)/p for each distinct prime p that is a factor of p (for more general use).

[@randomlife7935]

As Michael emphasized, the theorem you used to determine φ(n) has not been covered by the course yet, so you cannot use it at this time.

[@RexxSchneider]

@@randomlife7935 And as I said, it better to cover some of the concepts that are needed _before_ you move on to topics that make use of them. I certainly would never have taught Euler's theorem before taking a good look at his totient function first. Nevertheless, in this particular case, nobody has to use the properties of φ(n) to make use of it, as it can be found by counting the coprimes smaller than n. But that is tedious for large n and not a good use of student's time, IMHO. My intention with my comment was not to do the work for any students following the course, but to provide an affirmation of the results that they get, and to point them to further investigation of the totient function. I've always found that keen students who are given insights into extension work will want to expand their knowledge, and there's little doubt in my mind that time spent in becoming familiar with the totient function will pay off in these sort of problems. YMMV.

[@tomatrix7525]

Yeah, you can definitely see from Michael’s perspective how many of this stuff is so ‘standard’ that u forget students never saw totient function beforr maybe. I think he uploaded a proof of the multiplicativity of the function before.

[@RexxSchneider]

@@tomatrix7525 Indeed, although to be fair to Michael Penn, he does say the video is intended as support for a course he is teaching, so he probably has a particular group of students in mind and is aware of their existing experience. The problem lies, of course, with all of the other several thousand viewers who watch these videos, many of whom won't have the same background as Michael Penn's originally intended audience. I expect that he has to make compromises with the limited time available to teach a course and it's quite likely that skimping on the background of the totient function is a good choice in order to fit in all of the material required for the rest of the course. For armchair teachers like myself who happily retired several years ago, it's easy to recommend spending more time on this aspect or that topic -- and maybe you have to when you have a very wide range of abilities and backgrounds among your audience -- but I very much appreciate the time and effort put into these videos. Long may they continue.

[@jasonroberts2010]

8 elements in residue of 15, 6, and the residue of 100 is 40(need to practice Chinese remainder theorem, to spit it between 4 and 25)

[@AntonBourbon]

*None* of the examples requires Euler's theorem or Fermat's Little theorem, let alone Chinese Remainder Theorem. Moreover, they are solved easier and faster using basic modular arithmetic. (A). 7^950 mod 100: if you either quickly multiply in your head _or_ read Feynman's "Lucky Numbers" (with a simple method to square numbers around 50), it takes seconds to see 7^4 = 49^2 = (50 - 1)^2 = 50^2 - 2*50*1 + 1 = 2500 - 100 + 1 = 2401. *01* , that is 7^4 ≡ 1 (mod 100) ⇒ 7^950 = 7^2 * 7^948 = 49 * (7^4)^262 ≡ 49 * 1^262 (mod 100) ≡ 49 (mod 100) (B) 3^999,999,999 mod 7: check 3^2, then 3^3 and voila: 3^3 = 27 = 28 - 1 ≡ -1 (mod 7). 3^999,999,999 = (3^3)^333,333,333 ≡ (-1)^333,333,333 (mod 7) ≡ -1 (mod 7) ≡ 6 (mod 7) (C) 3^1000 mod 10: you need to have skipped arithmetic not to know 3^4 = 9*9 = 81 ≡ 1 (mod 10) ⇒ 3^1000 = (3^4)^250 ≡ 1^250 (mod 10) ≡ 1 (mod 10) *P. S. I appreciate your video and thank you for it.*

[@ruanramon1]

Fermazzle Little Theorem

[@trueriver1950]

The set {-3, -1, 1, 3} is shown as a red~res of 8; interestingly it turns out to also be a red~res of 10 even tho you don't show that in the list. I found it curious that the same set can occur in both lists

[@thatkindcoder7510]

The same is true for red res systems of 4 and 6, both having {1, -1}...

[@mohamedmontaser4930]

hay prof i got the term u were talking about and it is 7^950 = 69684792878758135164424871860897410590654029436821573172354149831239895084045435356747022585410114513158686123548273686057843529168478388315754541202389274259104138101417819286940012691578308940758351769021650833766921400089881165818275781263371308759110824141999395968242625752777926802158980657524935939218910624388277082340940534850927649416165229760129385334906873517447496156244136314828775657448249334977760343184372937563306422884836385748813454202187008468176672859911499192167453397465910941094844036780502804971111854977600080478576619808526702337896600911234707181682725672164713643765755224001972031123226811087983583123454818494531240176266319174964871432027726075834331639131441265184798457023608527572910480300722310253467244242826187050513853125210419487516639373381808435197863071711249 in integers

[@DR-tx3ix]

I thought it was interesting that the last two digits of 7^950 is 49 which is 7^2. So I got 7^948 and sure enough the last two digits are 01.

[@benjiusofficial]

Why you gotta use the picture of Euler when he was old for the thumbnail? You coulda used that one when he's still young and has the craziness in his eyes and that awesome hat. Dude was a mathematician's mathematician.