So, like, we're hosting a CTF on Friday. And so, like every spare mental cycle that isn't obligated to something, I'm like, thinking about really crazy things, you know? And so I feel almost like like a bad guy in a movie or something or whatever, where it's like, Okay, you know, you think I'm talking to you, but I'm actually like plotting out all the evil crimes are going to do, or whatever. Like It's just kind of living in a different space mentally. So, like, what I most want to be thinking about write this second is, like, a really obscure plain text eso laying where, like, I like make poetry, but it actually implements a code or whatever, and, how to part around with that in the right way. Can I make real poetry out whatever blo blah. But. So I feel muted. Like, I feel like my volume is half of what it should be. What Is there a song that would like, most get me high energy? Yeah. I like the Black IPs. They're pretty They're so 2008. And you're so 2008. Lyrics didn't age very well, I guess. Okay. So also, this is, like, the least webby kind of, like, subset of side quests that we're doing in this class. And so Friday just, like, was not a lot of people here. You know, maybe they're on the Zoom. I tried to get the recorded lecture up and things or whatever or something. You know. So like, I'm going to need your feedback, but, like, body language feedback and all stuff like that or whatever to be like, Okay, y, I'll put away for phone school. In order to know where we're at or whatever, because this is like Math my intent is the following. My intent is like, I want you to Essentially, see this and say, D. A. So like this line. And so I want you to see that line, be like, obviously, any idiot would know that. And not just because Wikipedia says it, but because, you get what it means, things like that or whatever. And I feel like I said just enough words on Friday that if somebody were completely locked in and paying attention to every last thing and then meditated on it all weekend, they'd be at that point now. They'd be like, Okay, cool. I'm with you. You know, I get it. Like that obviously makes sense to me. I probably didn't say enough words, and I got to say them in like few times or something because like math, That's the other crappy thing about teaching math. I like, made my bread, you know, as a math tutor and stuff or whatever, and a math I've been teaching math classes since I was 19, like at the college level, which is pretty fucking cool, actually, you know, But whatever, Like So it was like Florida State, and, like, Dude brought in, like, you know, red Dixie cups with, like, grain alcohol or whatever to a calculus exam, you know? Like, just, you know, they're party different down here. You guys think of yourself as a party school Florida S, like, Anyway, So but one of the things I know from all the years of teaching math is that, like, my words are almost irrelevant. Right? Like, I can say stuff and you like, kind of get it or whatever. But it's really tricky to then get it to, like, click in you, right? And I don't know. Like when I was learning French, like, I moved to France and I didn't speak the language. And you know, so I was just like kind of translating to English and taking synonyms and kind of spitting back out my English sentences in French or whatever. And after a couple of years, it's like, I could dream in French. And then I was like, Okay, cool, I'm right now. You know, Like once I could dream in French, then I could talk it for itself, or whatever. Still no syntax or grammar or anything else like that. But like, you know, there's this little light switch that's inside of you that like none of my words can get at. And in order to get that light switch, you've got to get curious enough or like, my hope is that I can show you a little bit of the beauty that the beauty like pulls you in, and you're like, Wait, what, or whatever, right? And what I'm hoping for is to say the sort of stuff that makes you say, wait what? And then you're like, thinking about it for a second and I give you just enough space to think about it, that maybe a light switch can go off internally. Maybe. Okay. Now, why does that matter to web app security and all this suf like that? Again, in order to get my goal is that you see this like D, and we can break that down. But because behind this are two of the things that make the Internet secure. One of them is the Diffi Helman Key Exchange where this magical number is P minus one. Internet security leans on this P minus one. In the elliptic curve version, it's sort of the size of the cycles or whatever, you know, fine. Thinking about post quantum crypto, what does that mean or whatever or what happens when Quan computers become efficient, if they've become efficient or whatever. Which of these things falls apart and why? Cool. And for the millions and millions of RSA problems that show up in CTFs and stuff like that or whatever, all of the RSA math comes out of this. I'd be totally fine if what happens today is that I teach you RSA. But I also need to I don't know. I don't just want to, like, say, here's the mechanics of it. I want to get you to feel it. So I don't know. That's maybe possible? That maybe not. I'll try only this week and then I won't try ever again. You know, that's fine. I say that with knowledge that on Friday, I won't be here. Friday, we're hosting Besides Delaware down at FinTech. And so you should all just come on down. Yeah, yeah, Yeah, just come down, Hang out. I want to see 9:00 A.M. So just like instead of going to class, just going down to Fintech, and shoot up to the fifth floor or whatever, and do a hacker con. It's like our little, you know, poor man's def con. What? It'll run all day Friday and then a half a day on Saturday roughly. So but there's just speakers and soft or whatever. I'll be hosting a CTF there, you know. So like, which is the Blue Hen CTF. So you know, that's also kind of crazy. And then the week after I'll be in New York for a conference too. I could maybe arrange a guest speaker or something like that. Maybe what I can do in order to make up for your lost tuition dollars is, like, record a thing on Zoom the night before, and you like, here's a recording and be teaching something interesting. I don't know. So I really value your tuition dollars. All right. So maybe more than you. Um So let's do this thing. And I came in Friday thinking that this is the story I would tell. And this totally wasn't the story. Like, and I think that's one of the things that I find very beautiful. I remember my PH advised, why am I being so long winded. Right. When you can validate something in three different paradigms or whatever, it helps you feel the truthiness of it, maybe. You're like, Okay, people from this field say that. People Mini feels that, Poles fiel say it or whatever. They all get a from completely different like axioms or whatever. It gives it more truthiness. So we came at this on Friday, almost entirely from just staring at these three words, closure, identity, and inverse, and we like, almost got there. Versus the story I thought I'd be telling was these like cycles and stuff. They didn't quite get there. So I'll try to tell the cycle story, but let me just remind you of what we did on Friday maybe, presuming that most of you were not there. Okay. Goes roughly like this. This is like group theory. Group theory is an abstract algebra thing where you study groups, and there's volumes of volumes of support in the library about groups, and there's these simple rules. And if you can find any set and function that combines two things in the set, that satisfy these three words, four words, really. Then it's automatically a group, and you get to immediately know all the things about that group that come from the volumes of stuff written in the library. So it's sort of like saying, we have studied the abstract stuff, and the moment you can actually identify something in the wild as that, you get all of the insight into intuition from the last 100 years of mathematicians. All right? And I said and I believe this Nobel prizes were given for people who identify that electron motions follow group theory patterns or whatever. They're like, cool. Electron motions are now well understood. Thanks, here's your nobel prize. And all I have to do is just like check that these things are true. All right. So here were the properties. You need a set of numbers and a combinator. We were playing with, like, the set of numbers Mod ten, I think was more interesting or the set of numbers Mod seven. So you could say, like, you know, my universe might equal numbers Mod seven. A these? Okay? And maybe my combinator is some function that takes in two of them, and it returns them combined in some way. So I could say like A times B mod seven, something like that. This combinator can take in any two things from that set, and spit out another thing in that set, or does it? Okay. So the question is, given a generic set and a combinator, can I leave the set? So that's the first property was closure. If I can leave the set, I'm not closed. An example of leaving the set is if the universe was like all integers, and the operation was division. So because 3/2 is no longer an integer done. But multiplication leaves me inside the integers. I can take any two integers, multiply them. I still get an integer. Okay. So this first property of closure, satisfied by some traits, but not other traits, things like that. Identity is one magical element that will always return the input. So like, in code or whatever that's basically saying, if I take anything and the identity, I should get that thing. And this is really, you know, for x in un. Right? So if that comes out as all trues, then I found myself in identity. Um, All right. Now, if I change my combinator to, like, plus, that will now be false. But if I switch that to adding zero, then I get back an identity. So like, a different identity, under different operators can exist. You know, It's kind of funky. So under addition, the identity is zero, and multiplication, the identity is one. Those are probably all we need to care about. But you can imagine, you know, the set is all matrices that are like two rows and two columns, and the identity is the identity matrix or something like that, right? And, you know, is that always closed or not or whatever, things like that, maybe, you know, whatever, and how well does that work, et cetera? Okay. Inverse, in order to be a group, and this one is probably the trickiest. In order to be a group, everything needs an opposite, where there's one element that when I combine with that element, my like antimatter. I I'm matter, I need antimatter, and together, we create the identity. So in order to have a group, I need to have two things that can annihilate each other, essentially. So in this case, if my combinator is multiplication. So, here's a dumb way to find my inverse. I don't know why I'm just in the Mood code. I think it's because of the CTF. So I'm going to find an inverse for a given number x. And I'll say, like for y in uni. I comb of x and y equal equal. I guess I have to know the identity here. Return Y. Otherwise, I'll just return false. Because. That's right. That's right. That has to be the identity element, and I didn't write a thing that identifies the identity, but it should be whatever the identity is. So if it's addition, it be zero. So let's try this. Find inverse for every x in the universe. Okay. So here, What wacky thing am I looking at in code here? One. Zero doesn't have an inverse. You think of that but for a second, zero times anything will never be one. And so, like the fact that zero never has an inverse means that this universe that I've got, like it's like too big for life under addition or under multiplication. This is me trying to go fast from Friday based on a presumption that, you know, not everybody was here. Okay. So but even for those who was, it's like, Okay, fine. I don't mind the recap, Maybe. This means that one times one is one. This means that two times four is one. Does that make sense? Well, it's Mod seven. The remainder when I divided by seven gives you one. Here is saying five times three, gets up to 15, but Mod seven, that's 14:01, so I get a one again. Here I'm talking four times two again, here that's five times three again. This one's a butte. Six is its own inverse. 66 is 36, Mod seven is 135, is the multiple of seven just beneath it. What's cool about that is it's the same thing as negative one. Negative one times negative one is always one under multiplication. That means that the 06 under mic is is not a group. That's correct. But the set one through six is a group. All right. And that is probably the interesting thing. So like, and to say Remember my goal. My goal is to look at this crazy thing and say, like, Du, right? So, like, to get to the place where I see Du on that, I've I've got, like, three or four things that got to get right. One. Um. That one's also a du, but in fact, I don't know, I just clicked a thing. I don't know what I clicked. I clicked it on accident. But this is the same sentence, and it's the example we just saw. In fact, they literally do P equal seven. So they're saying, take a look at this. Any number raised to the six is one mod seven. Well, we don't yet know, like, what that means or how that connects or whatever, something like that. Except, what does it mean to raise something to the six? It means that I'm multiplying it by itself six times in a row. B, b, b, b, b, b, b. And all that's really interesting so far is that if I tried really hard to make a group out of the numbers Mod seven, I end up with six elements. So the only interesting thing real so far is that, like, numbers, Mod something under multiplication, form a group whose size is not just the modulus. I had to throw something away to make a group out of it. All right. That's where you go so far. So we've got a fight with this, and this is worthy enough that I'll just duplicate and come back here or whatever. We also have to kind of understand cycles. So I want to talk about cycles. I find cycles really really beautiful. And And Yeah. There's a lot I want to say, and I'm I'm just taking my time. I don't know. I don't know, whatever. Your body language will tell me whether or not I should There's no world in which I should go faster, actually. Like, it's okay. It's just It's just not the same fast paced hard hitting action you've had all semester in web app security. Where it's like, here. Go figure out angular, whatever. Like, you're fine. Because this shit's real. That shit's like surface deep. Go read a documentation, make a hello world. As Catch EPT, whatever. You know, Here CachPT can't make you understand. They can just say the same words I can say. The understanding is just purely contemplative. Anyway, you read Siddhartha. You you ever read Sadartha? Go read Sadartha. All right. I'll tell you my Sadartha story later after you've read it. No spoilers. Okay. So step one, we had to get rid of zero. That makes a group. Okay. Question. If I take all numbers, modulo n for some n, which like x less than or equal to n have an inverse modulo n under multiplication? That contrast isn't very good. And I got lights line. You can read that? Okay. I'm saying, if I take all the numbers mod to n for some n, I take all the numbers less than it. Which ones are going to have an inverse modulo n under multiplication? So let's start with that for a second. Let's try I don't know. Let's try a modulus that has a slightly different structure. Actually, you know what? Maybe we should just try a modulus that is also a prime just to confirm it real quick. So say n equals 13. I'm going to change my My combinator here is fine, but maybe I'll take n also, so I can just kind of, you know, just kind of code this or whatever. So let's go to the find inverse thing, and we say n. And here, I'll take range of n. I think I should say range of n plus one. Oh, right. Da drat. Okay, fine Finfin. It's saying, like, Hey, dude, you wrote find inverse and not take. You're right, you're right. This is kind of what happens when you code anything and react. Why I'm shocked by that. That won't matter. Oh, it's the uni. It's the uni. This needs to be range plus one, I guess. There we go. Okay. So this is saying, take all the numbers 1-0 to 13 modulo 13 and say, find me the inverse of that number mod 13. So it's just like trying to multiply and find anything that when I multiply, gives me one again. We got this pattern. Okay? And what's the pattern? While the inverse of one is one, and by the way, the inverse of negative one is always negative one. So like 12 12 is always going to be one. And everything in between had a partner. They all paired up like little Atlantic puffins or whatever. All right. So which ones are out? Zero, and, you know, of course, 13. So how many numbers are there here? There's exactly 12. What is 12, 13 minus one. Okay. So the number of numbers that had an inverse modulo n where n was a prime happened to be p minus one. Okay. Let's try that where n equals 15. Okay. Not as pleasant. So these are the numbers, Module 15. Are you guys able to read this? I one abstraction layer too far away? These are the numbers, Mod 15. So like zero has no multiplicative inverse mod 15. Zero times nothing nothing times zero is ever going to get me one. One times one is one, negative one times negative one is alwaysive is always positive one. And then they kind of have a weird little maybe unpredictable pattern. One and two are in. Yeah, what's up? Is a multiple decomposition of them? Is false. Yeah. That's a good pattern here. In fact, this is like a classic coding interview. This is sort of fiz buzz in reverse. Anything that is like zero mod three or zero mod five is out. So if we take a look at this, like get one, two, three, four, five, and six, seven, eight, nine, is multiple three, ten is multiple of five, 12, multiple three, 15, multiple of five. Okay. So all the things that Now, Jacob phrased it in a way that is true, but makes a weird little bit of sense it's it's got its own language, which is good. It means you should consider grad school. If you can make your own language for patterns or whatever. The language that I use for that, the coolest little math phrase for it, that captures it like one word is co prime, like the mem version and math. And you guys know this from mem culture, where, you know, you can say like one word and it captures a whole lot of essence. You could say the Mariah Carey mem and you're like, Okay, get your Christmas crap out of here or whatever. A whole lot of weight comes in with that or whatever. What? Loss. Yeah, exactly. Like, I just throw some lines on the screen and you know what loss means or whatever, or not, whatever, if you've got brain rot. So here is the math word for this is co prime. C prime, so like two numbers are co prime. When their GCD is one. It's interesting. It's saying they're prime to each other, right? It's sort of a more relativistic truth about primality. So here's GCD. So I can take GCD of six and 15 is three, it's out. Seven and 15 is one, it's in. So they're saying the greatest common divisor is one. To me, the greatest common divisor is the best algorithm in the whole world. I could talk for hours about how beautiful greatest common divisor is. I'll give you a little TLDR version of that. Fastest thing in the world. Log in algorithms are great. Everything else sucks. And it was made by the Greeks on paper and pencil. You guys have, all your fancy tools and stuff or whatever, and you can't do as good a GCD. And it runs the world, and it's used in all the Internet security, and it makes everything just like And it cracks SA even, right? It's just super cool. So GCD is great. Here's the Matthy version of GCD. If I take GCD of two numbers, actually, let's take six and 15 there. Basically, the cool math version of GCD is the smallest thing you can make by combining your inputs, however you want. So that's the math version of PCD. So let's take six and 15. What do I mean by that? Combine six and 15. You can add them, subtract them as often as you want. So I could take 15 minus six, and I get nine. Okay? Cool, and I could take nine minus six, and I get three. I think no matter what else you'll do, you're either going to get zero or three or a multiple of three. All the things that you can subtract from each other, will just always end up at three and you can't ever get beneath it. It's like a leader board contest or something like that. Like, combine these however you want, add subtract them all day long. I ever you get something smaller than me, that it's now the best guess of the GCD. Whatever the GCD is, it divides whatever it is that you find by combining them always what's cool about that, we take 15 and seven. I could take 15 minus seven. Minus seven again. I get one. All right. I'm done. What's cool about that version of it is that it's also prescriptive. That means that if the GCD is one, I have numbers that I can combine kind of like this that will get me to that one. Okay. Now. Here is what is fascinating about that. These were the numbers Mod 15. Well, if I look at this equation Mod 15, so GCD is like linear combinations, imagine I've got a linear combination like this, and I just look at both sides Mod 15. This part goes away. Mod 150. And so what do I get is a one and then two numbers that multiply together to give me one Mod 15, and one of them was the one I was investigating. I'm going to say that again, there's an important little subtlety, and I don't think I sold it very well because I was trying to TLDR. The GCD of any two numbers is a linear combination of those two numbers. When the GCD is one, I'm going to have some equation, right? Where I get like something times n plus something else times my number is one. I'll get some crap like this. And if I look at that equation, M n, I'm like investigating X, let's say, GCD of n and x, that is to say, the GCD of n and x is one, if and only if There's a linear combination. Of n and x is one. And what does that look like? It looks like this thing. So GCD being one means that you can just do some just subtract and add and subtract an add until you get one eventually. And if you can do that, then you can write down an equation like this somewhere. Maybe you don't know the values or anything else like that or whatever, but you can write it down. And now just take that equation Md n. Mod n, what that means is that one is equal to n plus x n. Why? Because mod n, this is just zero. And so what does this mean? Well, that means that whatever the magical number was, it was the inverse of x mod n. And if that inverse exists, then it's allowed to be in my group. And if it doesn't exist, it's not allowed to be in my group. Put it a different way. If there is no such inverse, then the smallest thing I'll get will be that GCD, whatever it is. If the GCD of these two numbers was three, every combination I make of them is divisible by three, which means I can never find an answer that multiplies together to give me a one. So I'm going to take what Jacob said earlier and say, the only numbers that were left in my group were the ones that are co prime to end. That is their GCD is one. Order to maintain closure multiplication mod number. Every number in that set needs to be co with. Closure is a little bit looser than inverse. So I'm doing inverses. In order to maintain. In order to have an inverse mod N, the only numbers that have an inverse mod N. I'm saying this. A number has an inverse a number has an inverse mod n. If and only if Actually, mathematicians are so cool that we say if and only if like that. IFF is if and only. If and only if GCD of X and N is one. Unique number. A number can be its own inverse, and inverses travel as pairs. So if x is an inverse, then x inverse is the inverse of x, it's Atlantic puff and pairing. They're monogamous. It would be weird for three numbers to have a There's no polyamery in inverses or whatever. X times y times z is one or whatever. Things fall apart qui. No commentary, just saying just doesn't work. So that fact is interesting. And what it's really saying is, um There is a group. There is always a group of numbers, modulo n under multiplication. I want to move this because every time I'm typing, under multiplication. The size of that group is the number of things less than n with GCD one. Now, that number like counting up the number of things that are smaller than a thing that are co prime to it. We have a symbol for that. And you know what that symbol is? F of n. That's the symbol. F of n oiler socian function just counts the number of things less than n that have no common factors with it. Okay. So step one of this weird little story is that Mod N and using multiplication, one is the identity, and there is a group. There's always a group there, and the group is only made by the things that have no common factors with M. And that's how many of them there are. Five n. Now, we could explore five n. Again, I can spend many, many hours talking about all this. I'm trying to find the right way to give you as much of the interest as I can while still being as close to shotgunny in the class as I can, not make it a math class. But e. Pi of a prime is p minus one. That is, take all the numbers less than seven. The number of those numbers that have no common factors with seven are all of them but zero. So one, two, three, 456. That's it. And so given, you know, 23, there'll be 22 numbers one through 22. They have no common factors of 23. They all therefore have an inverse of some kind. I don't know exactly what it is, but I'll use GC to find it. Oiler. All right. Now, five of like 15 is not 14. Like, we can kind of see that. 515, we had to get rid of all the multiples of three. We had to get rid of all the multiples of five. So it's going to be kind of like 15 minus all the multiples of three. And minus all the multiples of five. But then I have to kind of not include 15 in that. Or actually, I think I can add one back because of double counting. So I think if I do that right, that is 15 minus five minus three. Basically, get rid of all the multiples of three. There's five of them, three, six, nine, 12, 15. Get rid of all the multiples of five, five, ten, 15. I got rid of 15 twice. So I add 15 back in, which is still gone, but I add it back in. And I get 1078. Okay. Let's go back and count the number of things we had here. One, two, three, four, five, six, 78. O. Okay. Cool. All right. Now, I'm shortcutting that or whatever. Again, you could spend some time flipping on light switches in that space too. It's not quite the light switch. I'm aiming at in this exact moment, but it's beautiful. I will now phrase this this way for RSA. A prime times another prime. Pi of that product is that? Which I could actually do the math on that. That is P times Q minus Q minus p plus one, which is exactly what I did there, when I was just counting. A? Any other prime? A product of two primes. They both need to be prime. Okay. This thing is it's a really fascinating little function counting up all the GCDs and suf it gets very combinatorial. Go spend a year of your life doing combinatorics. Like, it's worth it, right? Like, combinatorics help you in Vegas. They help you in, like, poting, they help you and just thinking, like, combinatorics are awesome. And a lot of times when parents are like, Hey, I think my kid might be kind of autistic like you or whatever, you know, they just really love like geeky problems and stuff. Like, what do I do for them? I'm like, teach him combinatorics. Like, you can learn it at any age, and it's just always useful. Calculus, useless, whatever, fine. Like, it's okay. But combinatorics. Bain every time I play a game of cards, you know. All right. So, cool. Now, what have we established? We've established, kind of the group of numbers Mod N has this many elements, and they're the ones that have an inverse, and they're kind of scattered in some wacky way, like predictable, but not exactly superstructured. The opposite of the izbuzz problem, something like that. Okay. Now, I have to sell you another thing. So that is me kind of looking at, like, that was basically this sentence. I kind of started at the bottom. It's clear that the group of numbers Mod N has five n numbers. Is that sentence okay with everybody now? Sort of it's just the ones that have no common factors with it. And so when does a number have an inverse when they have no common factors? And so, like that so basically, we handled this thing. Now to get to this part. This is like my Noda story. Like, I want to get to this bullet point here, which this like L tech is making my mouse not able to highlight the end of the things kind of bothering me, but fine. In order to get here, this is not true yet. This is not yet clear at all. Because now we just kind of have to explore, like, what does it mean to just take a number and start multiplying. All right. Have you I've gone through like Alan Watts phases in my life or just, like, just just listened to all the Alan Watts it possibly can. And those are a little bit weird chapters of life, you know? It's fine. I think it's a little bit more hedonistic than I think you ought to be, maybe. Like Alan Watts would not make a reliable dad, maybe, you know, died of alcoholism or whatever, right, you know, but, like, he just attached to enough that it's like, Okay, cool, There's wisdom there or something like that, but, like, slight grain of salt in Alan Wats. Um But Alan Watts taught me the phrase to persist in one's folly. So basically saying, when you have a debate, you know, hey, it's the day before the election, right? You have a debate with somebody who thinks the opposite of you. It's frigging animalistic, you know, tribal, like, I hate you and you hate me and kind of things or whatever and blah, blah, blah. Because, like, conflict about, world views and stuff like that, it's just not easily handled in like a quick little conversation, right? But what you can do is just agree and agree so much that they realize there's a contradiction. They're like, Okay, cool. You know what? I just love what you're saying. Let's just run it to infinity. And then it falls apart. So what you can do if you're going to have that, like, world view level debate with somebody who really hates your way of thinking is just just super agree with them. And that's called persisting in your folly. So like, you know, Oh, you think the world is flat. Just keep heading west then. You'll eventually fall off. Let's go see those dragons, baby. Let's go. Oh, crap. You Anda right back where you started. You know, okay. You know, I guess it's not. And maybe they'll make up some other rationalization or something like that, but like, they're not going to hate you along the way. So we're going to do that with number theory here. We're going to say, like, let's take the numbers Md 15. Alright. Let's take the numbers Md 15. N equals 15. And we're just going to pick one of them that's in that group. So pick a number that has no common factors with 15, and it's interesting. Seven sounds good. I'm just going to multiply by seven over and over and over and over. We're going to persist in the fall. And this is to answer the question. What is the action of seven on something? Well let's just see what the action of seven is on one. So I'll say one, one time seven, one time seven times seven Mod 15. And let's keep going seven to the third, Mod 15. And at this point, I now can kind of code this as seven to the fourth, Mod 15. Oh. Wait. Seven to the fourth, Mod 15 was one. That was a little unexpected. What about seven to fifth? Oh, right. I guess the world is not flat. Okay. All right. Well, just a, applied reasoning. What is seven to 8015? Go quick. Yeah. Okay. Why? Because I hit four. I was back at one. So like, every possible four is just going to get me back to one, you know? Okay. You kind of did this when you were learning about the square root of negative one. Squaro negative one is i, i squared is negative one. I cubed negative i, fourth, one, I fifth is I again. Therefore, you know, I to 2025 is I. Okay, cool. Just cycles. So Yeah. I don't even know what this is. I'm just like looking at what seven does Mod 15. There are sentences where that will apply, but I haven't yet made any hypotheses or anything like that. I'm just feeling it out first. So I mean, we could take a number that has a common factor with 15, ten, maybe? Let's just see 100 is one, ten to one is ten, ten square is ten, ten cub is ten. Okay. That got weird really fast. Okay, fine. All right. Let's talk about this generically. Take any number to any number 15. Okay. How many possible outputs are there? T. You're saying seven, six, 14? Oh, 14. Sure. Yeah. Like like Well, 14 or 15? One thing is true is that I'm never going to magically get a 16 out of it, right? 16 15 is one. So one thing is true is that there's at most 15 possibilities no matter what I imagine up. Probably less, you know, but no more than 15. Okay. But, like, how big is this number I? Well, we just did 8,000, you know. So if I were to make this sequence of all things, just keep multiplying over and over and over again, will it repeat? Yeah, totally. It has to at some point. There must be two values. No matter what x you pick, there must be two values like I where these two things are the same. It's the pigeonhole principle. Yes. Kids keep pigeons in their roofs these days, right? Well, I'll just think about how you keep your pigeons at home, and, you know, when you're going to care for Mopsy and Flopsy, and whatever you call your pigeons, you've only got so many holes to keep your pigeons in. And so if you have more pigeons, then you have holes, you have to have one hole with more than one pigeon at night. That's the pigeonhole. I don't know. I don't know who the hell is keeping pigeons. Probably New Yorkers. 'cause, like, that was true in like Homolne two and whatever? There's a New York pigeon keeping tradition that I didn't experience not growing up in the Big Apple. All right. So, just to say that eventually, if I just take a number and multiply itself over and over and over again, I will eventually repeat that just must be true. Okay. Now, let's look for some of those repetitions. So let's just do PO of x to the d 15 for i in range. I'm going to go all the way up to 30 just to kind of, like, see the cycle. And I kind of need to do this X doesn't exist. So like for in range one to 15, I guess. Now, Python three kind of got a little bit lame. I'm gonna like, maybe print the string of this or something. Okay. The I think if I reduce it to 30, I can make the font bigger. The people in the back are not even looking up. Can you read that? Is that like too small? It's a little bit of an eye exam. You can't read it? No. It's okay. Okay. All right. So, I'm taking one to one times one times one times one times one, never goes anywhere. This is obviously two. So you can kind of look at the second value to see which one's getting multiplied here. So this is like two, two times two, two times two times two. And then I get to 16, Mod 15 is one. So, I start to repeat. Okay. Now I get to three. Three kind of did a wonky thing, 39126. And then it goes again, 39126. Okay. So it does have a cycle, but it's a cycle of length three. And I'll say all the ones that have a common factor with 15 are going to break our intuition a little bit. You know? They're going to be a little bit poorly behaved, but they still must cycle. And by the way, the set of numbers in any one of these rows is called the orbit of that number. I've always loved that in number theory. Where like, What is the orbit of seven Mod 15? Like, Oh, it's 7413 and one. That's the orbit. I don't know who invented that, but you know, then I picture 15, and they're all kind of like floating around 15, like it's their son or whatever. Um, SUN. All right. Four, does this guy? 14. 14. 14. Now, four is two times two, is it not? So like one thing you can observe is that this cycle, I'm multiplying by fours is like multiplying by twos, two at a time. It's like jumping up two steps at a time on the stairs. And so I can see that this cycle is every other step of this cycle. You know what I'm saying? So, and we might even be able to find, like a wacky one. Here's this one. Okay, so what are some of the questions I've got? I got a lot of questions. If I don't have any common factors, like six. Oh, my gosh. Look how weird six is, you know? But six has a common factor. Those are weird. Ten was weird. Seven is cool, you know. But how long is the cycle length? So one of the things I want to know is, how long is your cycle length? If I just take the orbit of that number, how many possible things can I hit? So far, I've seen a cycle of length one, which is boring, a cycle of length four. Okay. A cycle of length two. These ones don't count. Cycle of length four. Cycle of length four. That one doesn't count, doesn't count. Cycle of length two. Cycle of length doesn't count. Cycle of length four and cycle of length two. Okay. So like multiplication by yourself over and over and over again, only ever got either two numbers or four numbers. Interesting. Interesting. Okay. That's wacky. U Why? What? So in order to look at those cycle lengths, one of the observations. What was 515, remember 515? It's eight. So like 515 was eight. The cycle lengths that we saw divide eight. Okay. Here's a weird fact. I think I want to have you feel it. The size of any cycle has to divide the size of the larger group. All right. That's a sentence that is true, but, like, you don't know why it's true, but maybe we can observe that it's true. Okay. So I think we can maybe, like, wave our hands a little bit at it. Oh, I've got 1 minute left. Gosh, darn it. All right. So talk faster. Okay. So the size of the cycle. So let's take one of these cycles. Let's take the twos. I have one, two, four, eight. If I multiply each of those by three, I get one of the other cycles we saw. Oh, wait, not three. I don't want to do three. Let's do another number that's in the group. Seven. There you go. Okay. If I multiply each of those by 14, I get something. If I multiply each of those by four, I'll get the original set. If I multiply each of those by eight, I get the original set. If I multiply each of those by 13, I get this set. Here's a weird little fact. If I take your cycle, 22, and I multiply them all by just one single three, Either, I'm just going to have the cycle again. Like, either three was in the cycle, W case, I'm just kind of like jumping forward some number of stairs, so I'm either going to get the same cycle or I will get none of the same elements. And this is what we call a co set. So I say I've got this cycle, and I can move the entire cycle. And what I get is something with no intersection. That divides the entire group up into, like, clicks. There's the cool chicks and the emo girls or whatever, you know, and that's just how the locker room divided. So if you take a cool chick and she talks to another cool chick, then they just hang out their cool chick. But you have a cool chick. Note talks Nemo chick. She's corrupted.Ni emo chick, whatever. I don't know. I don't think that analogy works at all. But I've I've got no intersection. There's no floaters. That's probably less and less true in the Internet age or whatever. But I've got either one set of four or the other set of four. What that means is that every cycle is going to create these partitions of the entire group. Because I can take any other element in the group and multiply by my cycle, and it's going to shift all of them or none of them. If it shifts all of them and I get a complete thing with no intersection, and what that means is that every cycle has to create shadow cycles, called cosets that are the exact same size as the original, and every element in the group goes into one of those cosets, and those cosets themselves have to divide up the size of the group, which means the only possible cycle length divides the size of the group. Which means that anything must cycle in a loop that exactly divides the size of the group. Now, let's see if we did it. Now look at this thing and say, Oh, well da. This is saying the group of numbers mod n has five of n elements. Any number can be multiplied by itself over and over and over again, and it'll cycle. The length of the cycle is going to divide the size of the group. And the length of the cycle will always end at a one. I'm just going to do my thing and end back at one and do my thing and end back at one and do my thing and end back at one. So if I take any number and multiply itself over and over and over again up to the size of the group, I will end up back at one as long as that number had no common factors with n. And so here, they'll say, this thing is true. If n and A are co prime, then this is can grow into one mode. Now you can look at that thing and say, Du, obviously, any Idiot would know that. But that's the thing behind the math of all the United Security, RSA, things like that, I didn't talk RS at all. But now we're ready. RSA is now just like a trivial consequence of knowing this statement in some wacky way. I'll do RSA, I say. Okay, hopefully I got to some of the beauty, maybe. You know, there's hours and hours of beautiful coffee talk conversations behind this that I encourage you to go have, you know. But see it.
Euler's Theorem
From Andrew Novocin November 04, 2024
2 plays
2
0 comments
0
You unliked the media.
Zoom Recording ID: 4159319948
UUID: lZI1k7BzTqiE3fsCL2q+fg==
Meeting Time: 2024-11-04 02:12:56pmGMT
- Tags
- Department Name
- ECE
- Department Division
- Date Established
- November 04, 2024
- Appears In
Link to Media Page
Loading