Episode Description
Corey and Jessie go through the next 10 pages of the ZKDL Camp textbook from 21 to 30 getting into prime numbers, fundamental theorem of arithmetic and modular arithmetic all which are important concepts relating to the basics of cryptography.
Watch Episode
Transcript
Click to expand transcript
It’s doing it. >> Welcome to Hashing It Out, a podcast where we talk to the tech innovators behind blockchain infrastructure and decentralized networks. We dive into the weeds to get at why and how people build this technology and the problems they face along the way. Come listen and learn from the best in the business so you can join their ranks. >> That’s an old school one. That’s old. That was um Colin’s music. Colin made that music. >> Oh, I didn’t know that. I was like, “This is corny as fuck.” >> Um, that was the initial intro that we had. >> Interesting. >> I thought that was the video drop that D recently made. We could just >> Whatever. It’s working. All right, everyone who’s watching, no one right now. Maybe somebody later. We are on episode three of our GKDL camp where we will go through the zero knowledge from what is it distributed labs. >> Yep. >> Basically a bunch of lecture notes on learning zero knowledge and we are going through still some math primers. We’re going to start today with prime numbers and get through Chinese remainder theorem I believe. >> Yep. Uh to through um uh you oilers >> get to the Oiler Oilers theorem. >> Yeah. Yeah. Not we’re not going to go over Chinese remainder theorem. That’s after Oilers. I read ahead a little bit. >> No. Oilers is first and then China. Sorry, Chinese and then Oilers. >> Really? >> Yeah. The book. The book is Chinese. >> Oh, yeah. You’re right. You’re right. Okay, never mind. >> Yeah. Last time we went through uh what do we finish off of last time? >> Uh we were at primes. >> No. What do we finish with? Uklitian algorithm. Yeah. Extended uklidian. >> Yeah. Extended extended uklidian. Yeah. I remember a little more math prime. >> We’re getting into a couple things that I guess we’ll be will prove useful later on down the line. Um, when we get into ZK stuff, we’re still doing math primers so that when we learn ZK stuff, it’s not going to be worthless to us all. >> All right, you want to go and start reading? >> Sure. Um, so yeah, 3 point I I did read a little bit, but there’s some notation that I wasn’t unfamiliar with and hopefully we’ll be able to tackle it together and between >> us Google and JBT or whatever we need to use. All right, so here we go. 3.3 prime numbers. Prime numbers are fundamental in mathematics due to their role of the building blocks uh of all natural numbers. In fact, every integer n greater than one can be uniquely factored into the product of primes, a concept known as the fundamental theorem of arithmetic, which we introduce in the next section. This property makes primes central to number theory and cryptography in particular where we will use them in in finite fields extensively. So that’s like super important. Yeah, that’s that’s probably like the main thing of like it’s interesting. You can build any number from a factoriization of primes. >> I think >> there’s a really good varasium video on this. Um >> Oh, there is. >> Yeah, I think so. It’s it’s just it’s nuts. Go ahead. Uh okay, so definition 316. Number p uh exists within the natural set of numbers. n is called prime if and only if it is two um it its only two positive divisor are 1 and n. Definition 3.17 number n uh that exists within the natural set of numbers n is composite if and only if there exists an integer a that exists within the natural set of numbers n which is not one or n for which a is a divisor of n. In other words, it is not prime. Example 3.8. 8. For example, 3, 17, 19, 29,71, 9997, 7,817, and 104,729 are all examples of prime numbers. In contrast, 8, 10,1, 10,000, 100,000 are all examples of composite numbers. One might ask, what to do with the number one? We consider it to be neither prime nor composite. Another logical question is whether the set of prime numbers is finite or infinite. The next theorem settles this question. Theorem 3.18 uklitian theorem. If p is a subset of the natural set of numbers n is a finite set consisting of prime numbers, then there exists a prime number p prime such that p prime um does not exist within the set p. Uh proof idea. So they’re kind of doing a proof if you extended they’re basically trying to prove to you that there’s an infinite amount of uh prime numbers. Um so theorem is a proof of proof idea. We can set p prime and then this is where the notation gets a little bit wonky and unreadable for me. How would you read that colon equals >> uh is set to >> okay is set to and then and then >> defined as is defined as Yeah, we d prime defined as the uh >> the product of >> product of yeah >> the product of and then like >> what is that what is that I don’t know what the big pi it’s it’s it’s it’s the multiplication version of of a sigma which is the summation >> right right >> the product of I guess >> that’s why like it’s it’s it’s a product it’s a it’s a it’s a product of a series and then in that series it’s like p exists within the p is like lowercase p is a number that exists within the set P capital P uh for P + one. So it’s basically saying if you multiply uh the the sequence of products of P + one as you increment P within the set of capital P. Then uh wait what is the colon equals again? um set to defined as >> is defined as okay >> that’s what I usually do I’ll look it up I’m looking it up now with with haiku >> so it says although it is intuitively clear that p prime is not divisible by any prime number in p the formal proof requires a bit more effort so yeah that that equation is a little bit not readable to me I had to use chap gpt earl earlier >> just product notation product >> so instead of summation >> yeah but how would you read that like the subscript like so it’s it’s the product of and then >> P within this exists within capital P of P plus one >> but the colon equals >> if you were to expand that series that the that product of like series like products of series >> how uh how do you get where it says although it is intuitively clear that P prime is not divisible by any prime number in P in capital P. >> How do like that’s not intuitively clear to me? >> P of P exists P P P P P P P P P P P P P P P P P P P P + one. So we’ll just like >> you just be like do P sub one + one P sub 2 + one to PN or to P subn like dot dot dot P subn plus one. >> Yeah, >> where N is >> I guess >> something whatever whatever the definition of the set is right. So whatever P is some set >> a finite set. >> So so how do you how do you how do you get that P prime is not divisible by any prime number in P. So P prime is equal to this formal proof that’s intuitive clear. I mean a So P is a set of prime numbers. Okay. So prime number plus one multiplied together. I guess because all the prime numbers are in addition. They’re plus one. They’re not going to be divisible by themselves. You multiply them together. I think from a previous limit we had last time. Mhm. No, no, I don’t remember because they’re all plus one from each other. >> Uhhuh. >> Then none of them are going to be a divisor of the product of whatever P prime is. But I don’t know why I don’t know why P prime is also prime. >> Like if it was a single if it was a single P plus one like P prime is equal to like it wasn’t a product of the series of P+1 like you know P subn. >> Oh no no no. This this is wrong. This is wrong. So like if we do this, this is this is wrong. >> It’s actually um >> Okay. >> P + one. So it’s all the primes multiplied together. The set of primes multiplied together plus one. >> Oh, >> I think. >> Oh, okay. Not >> the parenthesis. There’s no like going to be. So this is like like this. So P prime is equal to >> that makes sense then because there’s always a plus one constant. You can’t it’s not divisible. >> PN plus. >> Yeah, that makes more sense. That makes more sense. >> But why is the plus one? How do we know it’s a prime? Well, h what I don’t understand is why how do I know P P prime is a prime? I can see that it’s not divisible because you add the plus one, >> right? >> I don’t know why it’s a prime. >> I think they just defined it as a prime in definition 3.16. They just said >> I think you just define things as a prime. No, they like this number P that exists with a natural set of numbers N is called prime if and only if it has two. Maybe they maybe they needed more information for us to make that >> explain this proof idea. Let me take a picture easier for >> did a good job explaining it, but I I I didn’t spend time reading it. see what Haiku has to say. I’ll uh thinking switch my screen. >> I’ll go ahead and read the corollary right after and then once it finishes generating the response then we can read it. >> Yeah. >> Blow it up a little bit. Beautiful proof of Uklid’s theorem in the infinitude of primes. Here’s the idea setup. Suppose capital P is a finite set. Contain all the primes. That’s the assumption we’re testing. >> Okay. Is it just a finite set? Oh, it contains all of the primes. >> Okay. >> The construction define P prime as the product of all primes and P plus one. So I was right about it actually being all the primes plus one. >> Yeah, they should use P prime reveals a problem. When you divide P prime by any prime P in the set of P, you get P prime is the Okay, plus one one mod P. Okay, in plain English, the product of all primes is divisible by P, but adding one leaves a remainder. So P does not divide P prime. Okay, we got that. Yeah, >> this means P prime is not divisible by any prime in P. The conclusion. >> Oh, all primes. Oh, so it’s by definition by definition is a prime is not divisible by any of the primes. >> Yeah, because then it would be composite. >> Yep. Yep. >> Okay. Okay. Okay. Okay. Good job. >> Thank you. >> Okay. >> I love AI. Okay. window >> uh corollary 3.19 there exists an infinite number of primes. Okay. Yep. Lema 3.20 for all n that exists within capital n set of uh natural numbers capital n where n like little n is composite. If there exists a minimal divisor d is greater than one of n then d is a prime number. Consider a scenario where we have a large number and need to determine whether it is prime. How can this be achieved? In other words, what methods exist for primality uh testing? Uh several approaches are available. The most straightforward method is brute force division. Yep. Though it is impractical for large numbers. Yep. Probabilistic tests provide a more feasible alternative, though they introduce a small probability of error. In 2003, a significant breakthrough was made with the discovery of a deterministic primality test which placed the problem within the P complexity class. Uh it is also important to note that various types of prime numbers have applications in different fields. Examples include MERSN uh primes, factorial primes, uklidian primes and Fibonacci primes among others. U as an example consider one of the most well-known categories which you might encounter in the modern zero know zero knowledge protocols mercen primes definition 3.21 21 Men primes. The prime number of the form 2 to the P minus one is called a Men prime. Am I saying that right? Men >> I I guess. Merceni. Mercen. I don’t know. >> It’s It looks French. >> It looks French. Okay. >> Uh where P is a prime number usually notated as following M subp is equal to 2 P minus one. Yeah. Uh example 3.9. For example, 2 7 - 1 is equal to 127 is a mercen prime since 127 is a prime number. However, 2 to the 11th minus 1 is equal to 2047 is not a mercen prime. >> Okay. Since 2047 is equal to 23 * 89. As of 2025, only 52 such numbers were found. The largest of which is two to the really big number minus one. I think that is 136 million 279,000 >> video I think. Let’s put that I’m going look that up not. >> Okay. So the the the exponent for those who actually care is uh 136,279,841. So two to that number minus one. That’s the largest found prime number. Um the mercen prime uh lema 3.22 if the number m subp is prime then so is p. Um mercen primes are important in both number theory and cryptography. They have unique mathematical properties that make them useful for testing primality and generating large prime numbers. Yep. Mercen primes are also crucial in the construction of efficient algorithms for error correction in coding theory and for generating random numbers in cryptographic applications etc. Finally we introduce the dishitz theorem is probably like dish yeah I was about to say it’s probably a le dish theorem which is sometimes used for prime generation in cryptographic systems or constructing special primes uh theorem 3.23 23 to Rishlay’s theorem for any a b that exists within the natural set of numbers n if gcd of a and b is equal to one then infinite primes oh then infinite oh yeah I put a typo here then infinite primes uh prime numbers in the form of a m plus b exists where m exists within the natural set of numbers n so yeah there’s a typo there I need to submit a are. In other words, every infinite arithmetic uh uh progression whose first term and difference are positive integers contains an infinite number of primes. Uh yeah, infinite arithmetic progression whose first term and difference are positive integers contains an infinite number of primes. M what is okay? Uh remember function >> remember the generators like when you have like >> yeah I’m just thinking about it off the top of my head like >> I think if you expand those generator well they’re all based on mercen primes right >> I don’t know why that would be based on mercen primes >> it’s just a prime number >> because it has to be yeah we’ll get there I Explain darish theorem. >> It’s nice progressions is a major result in number theory that generalizes what we know about. >> Share share it. Share it so I can see the math expressions. >> I’m I’m gonna just go ahead and change what I’m sharing over to this and then you we can use your yours for reading. Okay. >> To go back and forth. >> All right. Sure. All right. Uh we got um so it generalizes what we know about primes. The statement if you have an arithmetic progression a a plus d a plus 2d a plus 3d which is what we have here with the um a m plus b. It’s just backwards. >> Yeah. >> Um where a is the first term and d is the common difference. And if uh greatest common denominator of a and d are one meaning that a and d share no common factors then this progression contains infinitely many primes. What this means uh think of any arithmetic progression as regularly spaced sequences 1 4 7 10 13. So oh this is useful for mod like for for prime fields right? I can see this being useful for prime fields. Um because effectively like prime fields are just arithmetic progressions. Dish proved that if the starting point and step sizes are co-prime, you’ll find infinitely many primes hidden in that sequence. Why it’s powerful? It shows primes aren’t just scattered randomly. They’re distributed across all valid arithmetic progressions. You don’t need a special starting point or spacing. They’re everywhere. That’s interesting. Examples primes of the form 4k + 1 is infinitely many fine whatever historical significance this theorem 1837 Jesus was groundbreaking because it introduced analytic methods to number theory using calculus and complex analysis to prove discrete results about integers. It’s a bridge between analysis and arithmetic. Cool. So it gives us tools to do analysis and rearrange things and and I think my intuition says is when we’re looking at circuits again gives us tools to restructure them such that they’re more efficient. H okay let’s look what tools does this give us for a zero knowledge I’m very curious my intuition is right >> why do you use haiku is that >> it’s just faster when I’m doing simple smaller things it’s just >> cheaper It allows me to spend more. That’s a sharp question. Thanks, Claude. Uh, let’s see. Many GK systems need primes with specific algebraic properties. >> Specific Sophie Germaine prime >> guarantees these primes exist in sufficient density. You can find them efficiently for cryptographic setup. Density guarantees reli on sampling from a particular res residue tells you the primes need the security arguments aren’t sparse they’re infinitely dense that’s nice group construction some zk systems use groups built from primes and specific arithmetic progressions >> you know what this is related to like this is related to understanding the security um uh factor that was disclosed for frybased proof systems in the context of um what’s what’s the guy. >> Oh, that one we talked about. >> Benjamin. >> Yeah. >> What’s his name? Uh, Starkwar’s thing. >> Yeah. >> Because I think it was a density guarantees issue because they Yeah. >> Well, look at this. But honestly, I’m not aware of a direct application of Dair’s theorem. Wonder how the book goes into it. >> Apparently, it starts at like chapter 11 or something like that. Like all of this is primer up until like I don’t know like 200 something >> doing a lot of primer. >> Yeah, >> whatever. >> Cool. >> Um >> it’s fun to chat GBT like doing seeing if your intuitions are correct or like seeing if there’s any connection between >> I can just switch tabs. That’s it’s way easier. >> Okay. >> I was gonna have to share my screen. All right. um or add to scene. >> I’ll I’ll read >> 2.4. Okay. Okay. Good for it. >> The fundamental theorem of arith arithmetic states that every integer greater than one can be uniquely factored into primes, which is fascinating. Uh which is crucial for understanding the structure of numbers. It plays a key role in areas like number theory, cryptography, and simplifying calculations involving divisibility. Um so, example 3.10. To see this fact in action, let us deose decompose an integer in 1 2 3 4 5 6 into a product of prime numbers. So 1 2 3 4 5 6 is equal to 2 6 * 3 1 * 643 to 1. You know obviously uh before formulating the fundamental theorem of arithmetic let us consider the auxiliary lema 3.24 24 um uklitian if p is a prime and p is divisible is a divisor of a * b then p is a divisor of a or p a divisor of b okay an exercise uh as an exercise and to show where basu coefficients are used let us prove both this lema and the subsequent theorem proof let be or let P be a divisor of A and B, A times B, but P not a divisor of A. Then the greatest common denominator of A and P is one because there are no common divisor. Okay, that makes sense. In which case, by Beu identity definition 3.14, which we went to last episode, go watch that. There exists such a u and v that exists within the integers that a * u plus p * v is equal to 1. Let’s multiply the left and right sides by b. A U plus P VB, right? But P is a divisor of A and B and P is divisor of P and B. Make sense? Therefore, their sum is also divisor by P being a divisor of A, B, U. Okay, let’s see here. Okay, make sense to you? Uh, not the sum. The sum is also divisible by P is a divisor of a * b * u plus p * b * v. The sum is also divisible by that. Let’s see. Is it one if you just divide them? If you take P P is a divisor of A * B * U plus P * B * V and take the previous expression like it should just be one, right? Yeah, I think so. P is a divisor of P and B. P is a divisor of A and B. There’s some it’s also divisor by oh because of this au plus pv that was equal to one maybe I don’t get it so they multiplied the whole expression by b right so so they they had this previous expression uh on the second sentence um in which case by basu identity definition 3.4 there exists such u and vist with a natural set of or the integer set of numbers z that a u plus pv is equal to 1. So that’s the expression a u plus pv equ= 1. Then they just multiply into that expression this b and they get abu plus pbv is equal to b. And it says but p is a divisor of ab. So p is a divisor of ab. >> You can’t see my screen anymore. I was going to bring up my thing. Write it down. >> Okay. But that’s that’s what they said. Let So P is a divisor of AB and P is a divisor of PB. P is a divisor of PB >> window. >> Where did they get that one? Basu identity 3.14. I think this is one that makes more sense to work out. >> Yeah, I’m I’m pulling up the mirror. >> Yeah. Proof. So the lema 3.14 which is I think was Yeah. Basu identity for any two given integers a b exists with a natural set of numbers n with d is the gcd of a and b. there exists such a UV. Okay, that’s that’s not that’s just the baso identity. That’s something we’ve already accepted. So, let me go back to here. Okay. So, P is a divisor of PB. I’m not seeing that one. P is a divisor of PB. Oh, wait. No, that that that makes sense cuz it’s PB. Therefore, their sum is also divisible by their sum is divisible by P. Okay, that that that jump I need to work that jump out. P is divid plus PB. So p a >> is a divisor of a and b. >> Oh no, I get it. I get it. I get it. It’s because u and v are part of the d are part of the uh basu identity format. Okay. So so the first term abu is is divisible by p because that’s part of the setup. They said let p showing us is a divisor of b. P is a divisor of AB. The jump is P is a divisor. That’s not even a jump. P is a divisor of PB. The jump is the sum of the two is divisible by P. And you can only make that conclusion based on the definition 3.14 that there exists such a UV essentially they’re multipliers such that P is a divisor of AB and BV or sorry AB and PB. >> because of the Basu identity. >> Because of the Basu identity 3.14 >> which are primes >> uh U and V are they primes or they just integers >> within the prime numbers by definition? Uh here they’re just integers. >> U and V. >> Oh yeah Z is integers. I forget. Sorry. >> Yeah. Yeah. Yeah. >> My bad. >> Yeah. U and V are not not guaranteed to be primes. They’re just integers. >> In fact, they’re always positive, right? Because the vaso identity in the context of this type of cryptography, you don’t like it can be positive or it could be negative for both U and V. But it says make the assumption is positive. >> Yeah, >> and it’s a big number. I feel like a lot of these would be more helpful to just code out and then also handwrite like handwrite then code out. and try coding it. I guess theorem can’t see that on the on the upside down the >> mobile street watching this mobiley. We’re sorry. >> Uh go to a computer. >> Theorem 3 3.25 fundamental theorem of arithmetic. Any integer n greater than one can be de decomposed into a unique decomposed in the unique way into a product of prime numbers. So n equals a p sub one to the alpha 1 p sub 2 to the alpha 2 all the way to pt alpha t. Uh so product from j to 1 to t p subj exponentiated by a subj where p sub one to p2 are prime numbers and the alphas the set of alphas exist within the natural numbers. >> Oh interesting. They’re not even guaranteed to be in they don’t have to be integers. They just be natural numbers. Okay. >> That makes sense. Ah really interesting. Yeah, proof we need to >> any integer n exponentiation is integers. >> Yeah. So, so you >> natural numbers is >> so is that a type? No, no, but the last line the last line says uh alpha 1 to alpha. So uh alpha 1 to alpha t exists within the natural set of numbers n. But >> in the beginning this the the second sentence or I guess it’s the first any integer n is greater than one >> natural they’re counting numbers like so they can be negative. >> No but what I’m saying is that it should be swapped out from natural numbers to z because right shouldn’t it be the integer set z. >> No because they can be negative. >> Yeah. But it’s still it doesn’t doesn’t need to be like >> natural to be negative integers integer the set Z I believe is >> integer set is a subset of natural numbers but they they they gave you a statement saying n any integer n is greater than one that means that the set like yes the set can be natural numbers but it would probably be more accurate to say z no >> I’m I’m asking Okay. Um, Z is the integers which is which can be negative. Oh, natural numbers are not negative. Okay. So, they can’t be Z is the integers which can be negative including zero. Double strike in is the natural numbers which starts at zero and goes forward. I guess there’s a convention where sometimes it doesn’t actually start at zero. Interesting. Anyway, so n the natural numbers is a subset of the integers because the integers would be negative. >> Okay. Okay. >> So there you go. >> Oh yeah. Yeah. Yeah. Yeah. Never mind. I’m I’m wrong. Uh for whatever reason I >> the the was it the integer over natural? Yeah. Rational. Okay. Okay. I just need to refer back to the notation notes that I have here. Okay, cool. >> Yeah, that makes sense. Okay. Uh proof. We need to prove both existence and uniqueness. Since the existence is easy to prove, let us make the small exception and show it. For other proofs, I don’t think that’s how you say that. >> Yeah. >> Uh in particular, for the uniqueness case, that for other proofs. Yeah, it’s proofs. Uh, see the literature provided. Okay. Existence. Suppose the theorem statement is false and there exists an in that does not have such a representation. Let n sub0 be the smallest of them. If n sub0 is prime, it can be represented as p1 equal to n sub0 a1= 1, which satisfies the representation. Therefore, n subzero must be composite, which means what is that? For all a, right? >> Yeah. Yeah. um for all a and b that exist within the natural numbers 1 minus a b minus n sub0 such that n is equal to a * b since n sub0 is the smallest nondocomposible number and a b is less than n0 a can be represented as a basically the fundamental theorem of arithmetic there uh there exists sorry you said for all >> exist okay there exist okay there exist Yeah. >> E E for exist. Don’t don’t forget that. >> It’s the I think upside down A is for all. >> Yeah, that’s right. Thank you. Yeah. Therefore, basically you’re you’re expanding A and B via the fundamental theorem of vertic we just showed. >> Uh therefore n sub0 is equal to a * b is equal to um the the product of both of these things. Thus the contradiction as n sub0 is represented the product of primes. >> I didn’t understand that see what the negative is because you’re you’re you’re trying to prove the opposite of the of the existence. So like saying like we’ll just try we’ll try we’ll try and say there’s a negative. We’re trying to say there exists ones that doesn’t satisfy this >> and then expanding them out you show that it’s a it’s a it’s a bad statement. >> Got it. Um suppose the theorem is uh statement is false and there exists n that does not have to be or that does not have such a representation. Let n sub0 be the smallest of them. If n sub0 is prime, it could be represented as p sub 1 is equal to n sub0. Alpha sub one is equal to one which satisfies the representation. Therefore, n sub0 must be composite, which means there exists a exist natural set of numbers n one is less than a b is less than n sub0 such that uh n is equal to a b since n sub0 is the smallest non-decomposible number and a is less than n sub0 then a and b can be represented as a is equal to p sub 1 to alpha one. So it’s the it’s a it’s a product expansion of a and b. Therefore n sub0 is equal to ab is equal to the >> is that because basically that expansion is the same as the actual theorem which then just becomes the exact same representation. >> Maybe let me let me let me look. Thus the contradiction as >> if it’s a composite >> then you get this you get this representation which actually just being the original representation of fundamental theorem of arithmetic which is which is a contradiction right >> it’s still just a product of primes so like >> so they’re they’re always saying it always comes down to being a product of primes >> like yeah so what you’re saying is like by by making a composite and expanding those things as the fundamental charact you end up with the same which is just >> a number. So you’re saying like the representation still holds. >> Yeah, I see. >> There is no way to show that there doesn’t exist a number that can’t be expanded this way because even when you theoretically make one and it still shows to be expanded that way. >> Yeah, I get that. That’s the argument, but it’s just not uh intuitively clicking for me, I suppose. n be the smallest of them prime >> because like this one here if it’s if it is a prime then it already satisfies the representation so it’s cool that that that’s not going to work. So that means like okay let’s look at what it means to be a composite number. A composite number means a and b right. >> And since >> you can define both of these things as >> as a product of primes when you satisfies this is still a product of primes which is the original statement which is the representation. So like >> there is no situation in which you can’t have that representation. >> Yeah. No, I get the argument. It’s just I always I always have issues with proofs of statements because it always like they use the statement to prove the statement and it’s just like wonky for me, you know? It’s like what? It’s like >> it’s got electrolytes. It’s what plants crave. >> Yeah, that’s that’s what it that’s what it, you know, logically sounds like to me. It’s like >> because it’s got electrolytes. Why are there electrolytes? Because that’s what plants crave. >> Yeah, exactly. It it feels circular in in in logic. But are okay >> whatever book >> suppose n is decomposed as and I’m run out of time here definition 3.25 25 then if d is a divisor of n then d is equal to representation um where got it suppose a is that representation and b is that representation then the greatest common denominator can be evaluated as the grain which is the product minimum >> the minimum product of primes >> minimum >> p exponentiated to the minimum minimum of alpha i or b of i. Well, that’s interesting. >> What is what does that evaluate to? Uh the minimum of alpha subi and beta subi. Like what does that evaluate to? >> So you take all of the alphas and alpha of the all the betas >> and you just take the smallest >> and then you exponentiate to that >> smallest of the you can do this basically based on the way exponents work. when you when you multiply two numbers that exponentiate together, you add >> and so this ends up becoming I think that’s how you would prove it. >> Lowest denominator is the max of that’s interesting. Okay, >> so it’s opposite. >> The GCD is min. Yeah, I guess it makes sense. >> It’ll seem as max. >> If B is divisor of A, C is divisor of A, then of B and C is equal to one. I’m missing more extensive proofs on all of these statements. Does that make sense? Like >> you can throw them all in chatbt and have it walk you through each one and be like that doesn’t make sense. More >> I for these things. I mean Haiku seems to be doing a pretty good job here. >> I’ll try that after. >> We could write them all. We could we can ask all your questions then copy and paste the answers and put them in some show notes. >> Yeah, that’d be a good idea. Implications and applications of the fundamental theorem of arithmetic are large and important and the number of obvious ones are listed above. Okay, obvious quote unquote obvious note that the problem of factorization uh in other words finding the decomposition of a number into prime factors is in the NP class of complexity and is the basis of certain crypto systems such as RSA. Yeah, cool. We should They should have had like a primer on complexity theory, you know? >> I love complexity theory. >> It’s like whole books on that >> Yeah. People spend their entire lives on complexity theory, but like Yeah, that’s that’s that’s that’s a that’s a fun place for your brain to explore. >> Yeah. >> All right. You want to do modular? We got We’ll do a little more. >> Sure. >> 3.5 modular arithmetic. Now, we are ready for practical applications of number theory. Starting with modulo congruence. In this section, we will review the idea of congruence, learn how to use it, and explore its key properties. Understanding these properties will help simplify calculations and solve problems more efficiently in fields such as cryptography, algorithms, and number theory. Definition 3.27. Two integers AB exists within the integer set Z are said to be uh congruent modulo n exists within the natural set of numbers n if and only if n is a divisor of uh a minus b. We denote this as a Oh, we denote this by a. How do is congruent to B mod? I guess that means congruent. What is the I think triple bar is congruent. See >> another bar mean. Oh, wait. >> Congruence symbol. Yeah. Okay. So I guess I >> modularic to mean is congruent to so >> so a is congrent to b >> mod. >> Yeah. Okay. All right. Example 3.11. It it easy. Okay. So I’ll just make another. >> Okay. So that meaning here goes the meaning of a is congruent to b mod n is equal to saying a and b leave the same remainder when divided by n. Ah, okay. Should write that out. A and B leave are divided by N. >> A meaning A and B leave the same remainder when divided by n. So congruence. So like let’s say um as an example I get an example here. There we go. They give you an example right here. >> Yeah. So I put a and b divided by n have the same remainder just I just word it another way. >> Yeah if you write it if you write it all out you get the same remainder. So 17 is congruent of mod 5 mod 12 because both 17 and five leave remainder five when divided by 12. Three is can grow to eight mod five because both leave remainder three when divided by five. Does that make sense? >> Interesting. Yep. Yep. >> Okay. >> Example 3.11. It’s easy to see that 26 is congruent to 5 mod 7 since 7 is a divisor of 26 minus 5. As always, we enumerate some key properties of congruence modulo n relation to better understand its nature. First we consider the properties of reflexivity, symmetry and transitivity to confirm that congruence modulo n is what is called an equivalence relation. For general equivalence relation definition see section 9.3 lema 3.28 reflexivity symmetry or symmetry and transitivity. One a is congruent to a mod n. Uh two, if a is congruent to b mod n, then b is congruent to a mod n. Uh if uh three, if a is congruent to b mod n, then b is congruent to c mod n. Then a is congruent to cod n. >> You ever seen the clock visualization for modular arithmetic? >> I feel like I have a long time ago. You want to pull it up >> because >> it goes to 12 and you just mod mod numbers on the clock and it just >> Yeah. So like um here we’ll say mod 12. It’s that’s what’s easier people people to understand. >> Yeah. The clock is is mod 12, right? Inherently. >> Yeah. So if you had like 13 then it’s one >> mod >> it’s mod 12 >> mod 12 >> it’s one >> equal to one because like 13 goes around the clock >> once and then overlaps >> means one over right. >> Yeah. So like whenever you have mod 12, it’s just going around the clock over and over again. >> Yeah. >> Until you and then you, you know, subtract whatever this number is and >> just keep doing it over and over again until So if you was like, you know what? >> So like anything mod anything that’s less than 12, not less than or equal to 12, but less than 12 would just be that number because one >> Yeah, exactly. mod 12 be it would be >> two revolutions of the clock which would be 24 >> right or two yeah >> right so one revolution of clock would be - 12 that would be 14 do it again minus 12 >> okay >> you just do divide by 12 and then the remainder is your modulus >> yeah that’s always been kind of a nice like my intuitive visualization of modular arithmetic >> yeah I don’t tell anybody else that’s watching but it helps with you’re pulling out each time, but like it’s like you end up if you were to like count the clock, right? You end up with two. So you end the clock for 26 modular 12, you end up here. Okay, so your remainder is two. >> Mhm. >> Right. Because you’re going around, you’re going around the circle. You have two left over. One, two. Cool. Your remainder is two. You just keep ticking it like that. >> I don’t know. Useful for me kind of. Yeah, >> I think uh Khan Academy has some other uh ways to visualize nonmod 12 base numbers systems, but >> that’s the same thing. It’s just like just it’s not a clock. It’s just a circle of numbers. >> Yeah. Yeah. Exactly. Exactly. Oh, wait, wait, wait. There’s there’s aren’t there other visualizations other than a clock or no? >> I mean, it’s cicular I can’t say the word circular >> cyclic system. It’s a cyclic system meaning that it goes over like go it’s going around. So I mean even this so like one two three one two 3 one two three is a cyclic system because this is you know modulo 3. It just repeats itself. So you could represent that as one, two, three, and then going around in a circle, right? Doing like that. >> Yeah. >> Just keep doing it. So it’s a different linear representation of mod three versus just putting them in a circle and going around a c going around a clock. >> Yeah. Speometer is usually a good way to put like thing like once it’s once it’s over, it starts over. >> Mhm. >> It’s just whatever the mod is is the the number of times you count before it starts over >> with the speedometer or the accelerometer or >> odometer. >> Odometer. Oh, yeah. Yeah. Because you can just reset it >> once. You just randomly >> Oh, yeah. Yeah. Yeah. Yeah. Yeah. >> I’ve never maxed out an odometer before. >> Oh, I don’t know if anyone has. Like >> that’s a lot of miles and we don’t make cars like that. >> All right. Interesting. >> See what else? How much How much do we got left here? We got quite a bit. >> Yeah. Let me Where did we leave off? >> Let’s leave it at that. Let’s leave at that. We left the 25 rafron number. >> Uh, sounds good. Where did So, we I read the lema 3.28. >> I didn’t read lema 3.29. Let me just read the last two. Let me read through 25. Yeah. So, so after reading the lema 3.28 on reflexivity, symmetry and transitivity, uh, in turn, the following lema states that we can perform addition, subtraction, and multiplication on the congruent numbers modulo n. Similarly to the usual arithmetic lema 3.29, suppose we have a is congruent to b mod n and c is congrent to d mod n. Then 1 a plus or minus c is congrent to b plus or minus d mod n. uh 2 a c is a * c is congruent to b * d mod n. Example 3.12. Let’s see how the lema works in practice. 17 * 26 mod n is congruent to 3 * 5 is congruent to 15 is congruent to 1 mod 7. Um 5 * 26 mod 7 is congruent to 5 + 5 uh is congruent to 10 is congrent to 3 mod 7. um uh -5 * 13 mod 7 is congrent to 7 - 5 uh * 6. So 7 - 5 is in parentheses * 6 is congrent to 2 * 6 is congruent to 12 is congrent to 5 mod 7. I need to work those out and then I’ll be like yeah okay makes sense. >> Yeah, working that out. >> I can’t just look at 26 mod 7 and just like know that. Let’s >> see. or 17 * 26 mod 7. >> How is 3 * 5? So like 17 mod 7 is three. 26 mod 7 is 5, right? So 17 * 26 mod 7 is congruent to the remainders multiplied together. >> Oh, okay. Okay. 15. which is occurred to one mod 7. >> The one mod 7 doesn’t quite >> Yeah. How do you get the one mod 7? >> Where did the one mod 7 coming from? >> Oh, >> you just take 15 itself. It’s essentially mod 7. If you do 15 mod 7, you get one. >> Yeah, I see that. >> So, it’s one mod seven. See a let me read the lema again. Let me reread the lema. Suppose we have a is congruent to b mod n. Wait no that’s not the one. It’s lema 3.292. >> So ac is congrent to bd mod n. So uh because it’s 17 * 26 that matches the form format bd mod n. So 15. So the first part 3 * 5 we got that right and we have to go backwards back into mod. So that that transition backwards in all through mod 7. >> They don’t say that in lima, huh? B B B B B B B B B B B B B B B B B B B B B M N N N N N N N N N N N N N N N N N N N N N n B mod. >> Oh, AC is a AC is three and five. So A >> yeah a >> yeah three and five. So three and five is A and C. >> Yes. So then if it’s if you put it in the format A is congruent to B mod N uh That’s That’s >> What is What is Bod N for 17? Yeah, I’m trying to find. So, let’s see here. I need to write this down. 17 * 26 mod 7. So 17 is let’s do let’s see 17 we have um what is that a is equal to three and So seven goes into 17 twice to two. What is B in this scenario? Is that going to be 17? Yeah. Six. A is equal to five. So we have three which is congruent to 17 odd 7 and five which is congruent to 26 odd seven. And so what is C here? Says we were using the AC grid to BD mod N. >> Yeah. So I have in the format A is congruent to B mod N I have 17 is congruent to 3 mod 7 and then for the format C is congruent to D mod N I have 26 is congruent to five mod N but like I can I like intuitively the like I can just look at the pattern but like I’m trying to make the math math 5 is equal to 15. Where BD in this scenario? Oh, B is 17 is it? Yeah. Okay. So, like you can also so you can put it in three different formats. You can put it in BD mod N is equal to AC and and if you do that then it’s 17 * 26 mod 7 is equal to 15 where A is 3 and C is five and B is 17 D is 26 like you’re saying and then N is 7. We could do it on in the other format. Uh A is congrent to B mod N and 17 is congruent to 3 mod 7 and then C is congrent to D mod N which is 26 is congrent 5 mod 7. Where’s the one? >> I’m trying to simplify. Anyway, >> where’s the one come from? Because I like 15 mod 7 is one. They are congruent to each other. >> Guess they’re just all congruent to each other. >> The whole Yeah. Like uh So, >> so 17 * 26 mod 7 is 1. >> It’s converting from like cyclic arithmetic to linear arithmetic. It allows you to convert. You can take 17 * 26 mod 7. >> Uhhuh. >> And then just do the modular of each of the factors. >> Yeah. >> And then that’s an easier multiplication, >> right? >> 15 and then just convert back >> you get one mod 7. It’s congruent, I guess. So you in the end you have 17* 26. So I guess >> remainder of 1726 mod 7 is one of >> something like that. >> Yes. Yes. Yes. Yes. But like the the lema doesn’t give you the simplification. You’re doing the simplification in the example. >> Yeah. like some playing with >> I think they’re missing they’re like >> because because in the in the first format 17 * 26 mod 7 matches the format BD mod N right which is AC the second the second uh item in 29 >> and then and then and then uh it’s taking that same lema AC equals B BD mod N but you’re putting putting in the format 15 is equal to like 15 is AC is congruent to BD which is now 1. So BD was previously uh 17 * 26 and then you convert it to one. There must be anyway there must be like an addition. Oh, wait. What’s this? >> All right, I gotta go. >> All right, sounds good. I’m gonna do this on outside of the >> If you’re watching, tell us how you feel about that. >> All right. How do we want to end this? That’s it. Just hit end. >> Goodbye. Uh, see you next week. Next week we’ll go over uh >> What’s your sign off? >> More of this. Goodbye. I don’t know. I have a sign off. All right.