PSE Lectures - Ep 5 - Groups (4/4)

Transcript

okay hi everyone I guess the issues are resolved now um er today I want to uh to continue talking about ER about groups and I I hope that now that that Carlos is around ER we will get to have a bit more discussion so I again I remind you questions are a not only welcome they are essential for a these sessions to be H to be

complete ER and last time I I got the feeling that you didn't get or some people didn't get the the definitions of Kernel and image ER ER right so so let me let me revise it um so if we have um a group

map this this is my shorten terminology to to homomorphism then we can Define the image of f to be the set of H okay you can write it in different ways let's say the set of all Y in h such that there exist X in G for which f of

x is equal to Y but you can also write it for short as FX X in G so you can think of image f as as the collection of all possible outputs when you you input any any element in G and the kernel so so of course image of f is a subset of H and er we saw last time that it is in fact a subgroup of

age and kind of dually the Kel of f is the set of all X in G such that f of e and here of course the e i i i suppress the the ER the index of e By by the group because it should be understood from the context that uh e is is the the neutral element of age and of course the kernel of f is a subset of G and and we saw in fact that

it is a subgroup and the picture is as follows here you have a g and H and let's say you have the the neutral element here e here e then the collection of all elements in G that go to E this is the

ker and the image is what happen is what happens if you take sorry if you take all the possible G and apply F on them so this this thing in red is the image of F and notice f is

subjective if and only if the image of f is the whole the whole group age this is actually true for any function you don't need F to be a homomorphism the image of f is defined for any function from a set G to a set age and the image of a of f is equal to to the the target set if and only if the the function is rejected dually f is injective if and only

if kel of f is a the trivial subgroup this this requires a a a bit justification because it does use the fact that f is a homomorphism but how how do we see this so um if the Kent of f is and well maybe the the E easier direction

if f is injective then then clearly the Kel of f cannot contain anything else than because otherwise it would mean that two elements e and some non non-unit element in in G are mapped to to e so this would contradict injectives conversely if kernel of f is

and you have two elements let's say x and x Prime in G are such that f of x is equal to f of x Prime then f is a homomorphism so what I can do um this is equivalent to say that f x Prime Time f x - 1 is equal to e i just multiply this the equation by by f

FX inverse and since f is a homomorphism it commutes with the binary operation and with taking inverses so I get that f of x x Prime x -1 is equal to e which is the same as saying that X Prime * x -1 is an element in the k but the kernel we assume to be trivial so this this implies or in equivalent to say that X Prime x -1 is equal to e and this

is of course equivalent to say that X Prime is equal to X so so f is indeed injective and to give you maybe a a a a toy example you take F from integers modu of 5 to integers modu of 10 H given by f of x is equal to

2x mod 10 this this function it's very easy to see that it's a homomorphism um because if you take X and Y in integers modu 5 and you you add them together and then you apply F well here the add should be addition Mod Five but this is by definition h two of x + y mod

10 and by by basic properties of modulus this is equal to 2x modul 10 plus 2 y 10 which is simply f of x plus F of Y so the fact that I have the the equality between the the uh the two parel expressions means means that I have a group map and let's see what is the what is the

image f can anybody say could be all of the integers mod no well is it I mean is every integer module 10 of the form 2x oh no I see so it's it's just F from but which half which half the even one exactly so this is the the set of 0 2 4

8 sorry six is missing okay what is the kernel of f anybody I mean it's yes I don't see no sorry I was going to say I don't see any hands raised but but anyone can just jump and talk if they want to there's no

restrictions or anything is it zero and five exactly okay well it's five is equal to zero in Z modu five so it's just zero right ah yeah so um so we know that that f is injective and of course it is going to be subjective on its image I mean the the image of f is a

subgroup of of the target group so it's subgroup of Z modul and as as I said earlier any subgroup is in is is a group in its own right I mean because it means that it's a if you restrict the binary operation from a the ambient group to the subgroup you you have all the axioms of the group ER satisfied so so you could you could view image f as a as a simply as a group in its own right and so of course you could you

could say F goes instead to Z mode 10 it goes to image F that's also a legitimate er a legitimate writing of course I'm abusing the notation a bit it's a formally speaking it's not F because it has a a different h Target set but H it's really it's really the same and and now this map this maybe we call it F Bar F Bar is

injective because F was injective plus it's it's subjective because any any function is going to be surjective onto its so plus of course it's also a group M so we get that F bar or or rather integers modu 5 is isomorphic to image of because F Bar is such an isomorphism but in fact you don't have

to have this fancy considerations you can just look at the multiplication table I mean 0 1 2 3 four and here the multiplication is is really addition modu of 5 so I write it like this Plus H mode five and and here I have a 0 to 4 68 0 2 4 6 8 and the operation is addition modu

10 but notice that I I simply I from here to here I blew up all all the multiplication table by two I mean I blew up all the numbers and I blew up the the modulus so if I if I feed this multiplication table to a computer it's the same I mean here I have a list of symbols but when I check what is the multiplication of these list of symbols it's a it's the same so so this is why at least from an elementary point of

view the two the two groups here are isomorphic okay and what we saw last time if I take um a group a group map from G to H then um of course I can look at the f but G is not going to be a isomorphic

to the image of f however if you divide by the kernel then you get such an isomorphism and the the intuitive explanation for this is that kernel of f is kind of a measurement for how close f is to H to be an injective Mark and so of course f is going to be subjective onto its image and it might not be injective but since kernel

F measures how much f is not injected once you mod out by by the kernel you get a you get an injective map so then by this you get an injective plus rejective map which is an isomorphism any questions doesn't look like there's any far yeah I see something in the chat oh the structure of a group modul the

kernel of some homomorphism f has the same structure as the image of f well yes this is what this is what the the theorem says this is this was a theorem I remind and it if you think of it you can I mean there is a certain Duality between injective and subjective Maps yes is there a question so what I'm

saying there is a certain Duality between injective and subjective map I don't want to put it in in formal terms because I think it is a bit too advanced for us now but just intuitively speaking if you C you could extend The Duality between injective and subjective maps to a kernel and image I mean because a map is is subjective if and only if the image of of this map is the entire group age and it is injective if and only if the kernel of this map is is is minimal I mean the

trivial subgroup in g h so so this this kind of Duality is is expressed in the in this isomorphism theor okay so we we are going to talk a lot about finite abilon and when when you consider finite groups in general there is a very natural

notion so let G be a group and a g an element in this this group capital G the order G and den noted o of G is the minimal

positive integer and such that g to the N is equal to e h I guess the minimal non negative integer H because it could be zero well sorry uh and if no such number

exist we set o of G to be Infinity now if a if G is finite then um then the order of any element in G has to be finite

because you get you you take the powers of G ER at some point you have to get er you have to get elements that you you already you already already expressed in in lower Powers because G is finite so at some point G to the N must be equal to E and um and what we want to do is to H kind of for for finite groups we would like to decompose the group into sort of

clusters of elements of the same order so for this we're going to do a little bit of a of a like Elementary number Theory so let me remind if M and N are natural numbers and there least common divisor

and this is denoted as LCM of M and N is the the minimal number natural number L such that M divides L and N divides now you you you know that every every

integer can be decomposed into to a product of H powers of primes ER if we have two integers can sorry Maan can you can you give more intuition on that like how you can form every single integer just multiplying primes well okay um so you you know you take an integer in our case M and you look for all the Primes let's call it this fancy P I see

I I did some math in my head and I saw it now okay but is this yes like is this proven somehow mathematically yes I mean you take the definition first of all in in the notes there is a section called Elementary number Theory so you can look at it there but it's very simple I mean let's let's take PM is all the Primes that are smaller or equal to M and what you do is you you look out of PM which are the primes

that divide M and once they divide them once let's say if if P divides M then you can then consider the set of all primes that are smaller or equal to m P okay that makes sense and and by by this inductive process you will you will Express you will Express M as a product of of primes but there could be some repetition so um so I write it like this

S1 P1 to the S1 up to PK to the SK right this this means that where P1 up to PK are primes okay and if I want to be concise then then S1 up to SK are some some integers which are bigger equal to one but if I have two integers M and

N I can take the prime decomposition of M and N um over the set the same set of primes so I write it like this PK here TK T1 where s I and TI are now allowed to be also zero so this is by I just take a I mean the prime decomposition of m and n h could could consist of different primes but if I want to kind

of er look at M and N on the the same the same level then I uh I add artificially all the Primes that appear in the factorization of M and N this is the list of my primes P1 up to PK and I allow the powers to be possibly zero so then I could write M as as the the product of powers of of the pis and N of the product of the power of the the pis H were only were only the the exponents ER may be different but the

the the number of primes and in in the decomposition on the set of Prime in the decomposition is the same so if you do this then you can H you can neatly Express N as simply as you take the product of primes and in each exponent you take the minimum is this

clear yep okay so this is this is a nice trick and H now we come to a to another famous theorem this is Kushi if G is uh finite B group

and P a prime such that P divides the order of the group G then there exist G in with order exactly p and I I remind you order exactly p means that g to the power of p is equal to okay so just in terms of the

statement you can view it as kind of a a partial Converse to H to lrange theorem lrange tells you that if you have if you have a subgroup of G then the order of the subgroup divides the order of the the ambient Group G and and kosit Theorem I mean you could ask okay so so suppose I have a number that divides the order of the group G do I actually have a subgroup of a of of this well so so kosi tells you tells you something similar we will soon see that

you can really construct subgroup of of order G but of order p in such a case but for now it's it simply gives you an element of order P okay assume and by contradiction that um there doesn't exist G in

G with P if this if this is true then um there is no element in G of order divisible by P and and why is that if if there

was if a g to the r is equal to E and and P divides R then I can take G to the r ided p if you raise it to the P power you you simply get G to the r which is assumed to be e and this is a contradiction because we we assume that there is no element of p

h so so let G1 up GN be some enumeration of a of the elements of G and uh let h GI or rather Mi be the order of GI right each of the each of the gis had some order so of

course for any i p cannot divide the the order of GI uh let M be the LCM of all the M's all the m i equals 1 up to n then P cannot divide

n cannot divide M because P does not divide each of the m and when you take M you simply take minimum power in the prime decomposition if you if you look at it in the way you the way we talked before H so if if P was was some factor in this product it would mean that P would would be a factor in product ER expressing one of the m and that that would mean that P

divides Mi which we we know that is not happen so so P cannot divide furthermore GI to the m it must be equal to e because well GI to the m i mean it M divides Mi I divides M so G to the m has to be the unit

element now for for a natural number N I write G to the minus n to be G to the minus1 to the power of then we can Define the map F from integers modul m

times itself n times to G and this goes as a f of A1 up to a is going to be equal to G1 to the A1 up to GN to the A

and I claim that f is a group map well how do we check that f is a group map recall that the in the cartisian product the the binary operation is is done coordinate wise and in integers modu M the binary operation is is addition modul m in G the operation because we don't don't assume anything on G the convention is that the operation is multiplication so what I need to check is that if I

take A1 up to a n plus B1 up to BN I get F of A1 up to a n multiplied by F of BN but let's expand this this left hand side well what is what is addition of these two these two elements we said that

addition we do addition coordinate wise mod M so I can write it as F of A1 + B1 up to a n plus BN but of course this is equal to G of A1 Plus B1 sorry G G1 up to GN to the a n plus BN and since G so this I can decompose of

course to G1 to the A1 G1 to the B1 up to GN to the a n GN to the BN and and since G is a billion I can commute I I can commute all these uh all the factors this product to n multiplied by F of so what I get is the question

mark here is indeed uh indeed true and and I got a a a group homomorphism as in the in the blue box any questions about this step not from my side I don't see anything in the chat okay so once we have this this

note f is clearly subjective well how how do I know um I take I want a source for GI so I take simply the sequence Z and here one this is in the I place this is of course is going to is going to be by the definition of f is going to be G or GI to the

one so I have a source and G1 up to GN is the the full enumeration of G so so f is is subjective now by the first isomorphism theorem I get ZM to the N this this is my shorten notation for the the enfold cartisian product of ZM with itself divided by the kernel of f is going to be isomorphic to the image of f but the

image of f is everything since since f is rejective so this is going to be isomorphic to G by the gr like I don't see why is it so subjective like if you just because you have all of the zeros and the identity at the e place and you get G of Y why does this imply that is subjective well what is remember f is is something that Maps into G and G we we took an enumeration G1 up to GN this is a fully numeration of G

sure so what do I need to show you in order to to to prove that f is subjective I need to show that for any possible output GI there exist a a an input in in the source I mean in in ZM to the power of n such that the the program Maps this this input to H to output so okay okay okay I see so you just need to prove that you can go from the domain to the image um and you can arrive to any of the images uh of the of the function or the application I I mean

this I prove that that the image of f image of f is is is all of G makes okay okay okay okay okay makes sense I see now I see I thought that I thought the it had something to do with the fact that you can move multiple multiple items in the domain can go to the same image but this property doesn't matter at all you just wanted to Dage of FG that's all that was yeah okay fair enough so by by by the first isomorphism theorem I get isomorphism of groups Z ZM to the N modul the

kernel is isomorphic to the image but the image of of f is is all of G so it's isomorphic to G okay makes sense now by gr the number of elements in the kernel times the number of elements in G must be equal to the number of elements in ZM to the right I mean kernel kernel of f is a subgroup of ZM to the N so it must divide ZM I mean

the order of of the kernel must divide ZM to the n i mean is of course m to the N um but L Grand theorem tells you tells you really this equation because it tells you that the number of um the number of elements in this group is the number of distinct distinct cetes so or the number of elements in this groups is is the number of distinct cetes so this really means that you get you get an equation like

this okay we're almost done so so um I conclude that the number of elements in G must divide m to the N but P divides the number of elements in G by by assumption and P does not divide M so P does not divide also m to the n and

that's a contradiction any questions about the theorem sorry just um to recall this is a contradiction to what uh proposition again so we assume that there is no element of P ah okay I mean the statement of the theorem says that there must be an

element of order p i mean we assume that P divides the order of the group and the statement is that I mean there is an element of order P so I I assume by contrad by contradiction that there is no such okay yeah got it makes sense other questions so I think H now would be a good time to break uh let let's meet here in 10 11 or 10 minutes from now sure uh today we will need to uh finish

at 12 at least recording wise um because I have another meeting so I mean I hope it's not an issue but uh yeah I will to the recording at least so either you can do a review or or or or we can just miss a part of the recording whatever whatever you want okay so you okay see you soon see you in minutes okay let's go okay so I I just want to make a a a correction I call the LCM H the least common divisor I think but of course it should be least common

multiplier yeah this should be the least common multiplier I mean it's the the minimal number such that both both integers M and N divide the number so of course M time n is such a number but there there possibly there could be a a smaller number that that uh that has this property ER any questions about kosi theorem there's a question in the

ah so in the case of an elliptic curve which is an a billion Group H when we prove a homomorphism between the points on the to curve e and the points in one of the Prime order sub groups this would show we are squeezing the structure of e into the prime order subgroup formed by this generator well okay we didn't talk about generators so I will H I will leave this the last part of the question open but

what is happening in a in elliptic curves is that you take the collection all ER solution to the the equation of of the elliptic curve over the prime field this is a a the order of this is is something like a p it could be it could be slightly bigger it could be slightly smaller this this is a result called H or Hass whale theorem and then assuming that this is

a if q a prime such that Q divides the order of the elliptic curve then by by by kosi it tells you that there exist an element ER let's call it we usually denote the elements of an elliptic curve by capital letters because they are like points and elliptic curve is an ailan

group and den not Ed with a additive notation so kosi theorem in this case would tell you that there exist a number well sorry an element in the a point on the elliptic curve such that P plus p itself Q times is equal to the zero element and this is of course this is denoted as as q p ER and generally speaking

if a g is an element in G of order then well I can consider let's call it age to be the set of all all positive powers of G so I have e which is g to the 0o then I have G and up to G to the N minus one because G to the N is is going to be H the the neutral element again and

H in this set all in this description of the set all the elements are distinct um if if K and say strictly smaller than n then H GK cannot be equal to GL because otherwise g l minus K would be equal to e and this is a a so

so the order of G would be smaller or equal to l minus K which is strictly smaller than n so and this this is all to say that if you have an element of order G oh sorry of order n then you can look at the the set of all power positive or non- negative powers of er of G of this element and you get a set of size of size n right you have from zero up to n minus one and moreover

so AG is a subgroup of G well of course it it has the the neutral element a if you multiply two non- negative powers of G you get again a non- negative power of G you take modu n then you you land in this set again and just to check the inverse so what is the the inverse of G to the K this is going to be G to the N minus K right because if you multiply G to the

N minus K and G to the K you get G to the N which is by assumption the the neutral Element e so this is all to say if in this case of the elliptic curve with a point P of order Q we get this this age is denoted as this Square I mean sorry a triangular brackets G this is like the

the collection of all of all powers of so in the case of an elliptic curve you you measure the number of points this this can be computed by a several algorithms you take a prime q that divides the order of the the group E of e of FP and kosi tells you that there there is an element P of order

Q and this would imply that you get a group generated by P I mean you take all the the positive powers or non- negative powers of of p and you get a e FP and the sub group is of q and this in fact well okay uh so is this answering the the question QB sorry is shouldn't it be P to the power of Q instead of Q to the power

P you mean here yeah here this is a in additive notation I mean of course in multiplicative notation I would write P to the power of Q Q this this would mean p * P * p q * but in additive notation I write QP ah okay okay cor yeah okay to mean p plus P plus p q times um I have a question yes so what you basically say if the order are or no

if the if the number of elements in an elliptic curve group has a prime which divides it then there exist a subgroup with that of that size right more than that the like the subgroup is generated by one element yes so we have a cyclic subgroup yes is that something which generally holds or I mean yeah kosi theor it does not depend on any elliptic curve structure it's it's a general statement about groups yeah but but isn't it so it does does kosi say that there exists a subgroup or does it say a set that's the

content of what what I was trying to say here generally I mean because if you hav you have G in G of order n i mean kosi theorem tells you that ER in particular if if if P divides divides the order of the group then you get a some element of order P okay but here I'm saying generally for any for any integer n if you have an element of order n then you get a subgroup by taking all the powers of this element I mean all the positive powers okay I see you see I mean why is

it so first I mean why is it a subgroup it contains the the neutral element of course if you multiply a GK and GL you you get g k plus L possibly k+ L is bigger than n but then g k plus G to the k+ L is going to be G to the k+ l modu n right yeah I mean it's going to be G to the N times some okay so so so this set is closed under

multiplication and and moreover every element has an inverse why because if take a g to the k then G to the n minus K is going to be the inverse I mean if you multiply G to the K and G to the N minus K you get G to the N which is which is e so every element in this set age has an inverse so so AG is in fact a subgroup this was the yeah so so every group has a subgroup for uh yeah for a prime factor basically so for that's what I yeah okay all right a CYCC subgroup in

fact yes okay so this you can regard it as a a partial a partial Converse to lrange lrange tells you if you have a subgroup then the order of the subgroup must divide the or the order of the the ambient group and kosi Theorem says well okay if you have a prime divisor of the the order of the ambient group then you must have a subgroup in fact cyclic disorder M okay makes sense thanks other questions all right

a we we need to have an example so we we simply uh recycle the examples we we have we know that Z 10 by kosi it must have a a subgroup of order five but in fact we we really saw a a we saw that 0 2 4 6

8 is indeed a subgroup of zon 10 and H this is in fact the only subgroup so but but that's that's another matter it's the only the only subgroup five okay so we talked about cly group groups but I I really want to uh put definition formally so let G be a group and a g some element in capital

the the group generated by G this is in fact in the general case I need to Define it as G to the N such that n is allowed to be any integer well of course I remind you G to the minus n is by gus1 to the a n

two G is called cyclic if there exist some G in G such that g is simply G okay and this H I didn't give it a name this is called the generated by G

okay notice the difference H here G triangular brackets is all the integer powers of G and in case we took all the non- negative G Can Can someone say why these two are equal in the in the case we discussed in the the the finite group case I mean

if G is finite then then um G and G must have a finite order ER so the group generated by the element G which by definition is all the powers h g to the n n in

Z is simply going to be equal e which is g to the 0 g up to G to the N minus one right and and the reason is I mean of course if you take a g to the N plus plus something plus K this is equal to G to the G to the K because G to the N is equal to to

e and if you take a g to the minus k then this is g to the minus one or it's a g to the K to the power of minus1 but we so that g to the K inverse is in fact G to the N minus K you multiply two of these you you get G to the G to the N which is e so in fact in in the case of a of a finite group I I could express the group generated by G in only the the the non- negative Powers

instead of taking Powers over all integer is this point clear any questions about the the definitions think is clear least there's no questions in the chat so far okay examples one integers modu n is cyclic it is

generated by one right you take a a one 1 + 1 + 1 + 1 + one you get all the elements of integers modul two the integers is also a cyclic group you one you can I mean to take a to take the group generated by one is to take all the um all the elements n times one such

that n is in Z so this is z but notice that I can also generate the group of integers by minus one because I allow here n to be any integer so this is going to be n * -1 n in Z and and that's again that's again the entire set of integers so this is to to show you that a generator does not need to be unique a group a Clic group can be

generated by by different elements now we take a a a cartisian product of two modules let's say a modu 2 and modul 3 and I claim that this is generated by the element 1 comma well here we have six elements so we can really H do it very explicitly take 1 comma 1 and add to it

1 comma 1 you get 1 comma 2 sorry you get 2 comma two but 2 comma 2 in the first coordinate we have module two so this is really zero 0 comma 2 then I take 1 comma 1 + 1 comma 1 + 1 comma 1 well I one comma 3 but in the second coordinate we take modu 3 so I get 1 comma 0

then I would take I just write it like this 1A 1 * 4 this is adding 1 comma 1 to itself four times I would get 0 comma 1 and a 5 * 1 comma 1 is going to um 1 comma 2 this is a 3 * 1A 1

two so so I got everything right of course I have also a 1 comma 1 and I have 0o times 1 comma 1 is simply 0 0 okay so I got yes this only works if they don't divide each other right okay this will be a a theorem yes but for now it's we just take a simple example also on the way you have defined the GPS and everything so now

it I don't know how to say that like it looks like zero is a completely different group that it's aide because you cannot get to it unless you multiply by zero so yes but when I say zero times one I mean in I mean this this is a is a is a constant source of a potential confusion um I mean when I write when I talk generally about groups I use the multiplicative notation G do okay ER and under this notation G to the

N of course is G operation G operation G with itself n sure now if I if I use additive notation H then I usually use the zero as instead of e and then instead of G to the N I write n * G this is the same it's basically G Plus G Plus G I mean G operation g n and this is what what is so when I write

here 0 * 1 * 1 it really corresponds to what we called G to the zero okay makes sense okay so this is which is always observe if G is cyclic then it is a

bilion I mean if G is C click then I can write G as a as generated by some element lowercase G and this really means I take all the all the inte integer powers of G and of course G to the K time G to the L is going to be equal to G to the L * G okay so multiplying any two elements is a in G is commutative now I claim that for any

n or any natural number in there exist cyclic group of order n and it is unique up okay I I will I will soon explain I will

explain during the proof what it means to be unique up to isomorphism but for now well the first part of the statement you should be able to to prove immediately anybody knows H why the first part of the statement is so the the blue part why is the blue part true uh because of

kosi ER you don't need kosi here all you need is a cly group of order n for every n we actually s we actually saw a cly group of order n is it because you can generate uh grp of other end with like one exactly so I mean ZN is cyclic then is C click see I mean z n for example is H now

if G is a cly group let's say I write it like this g equals the group generated by lowercase G and um a cyly then of course this we discussed earlier I can write G as all the the non- negative powers of of the generator so this is e g up to G to the N minus

one and H Define f from let's say integer small n to G by F of K is equal to G to the k f is a group map well how do I see it I need to I need

to to show that F of k+ K Prime is going to be equal to F of K multiplied by F of K Prime because again the the the operation in the in the domain group is is plus and the operation in the in the Target group is uh is multiplication but F to the k+ K Prime is simply G to the k + K Prime and this is of course equal to G to the K time G to the K Prime so f is a

group map and moreover f is clearly a bjective I mean this is a one to one correspondence I have have is integers modu n is simply all the numbers zero up to n minus one and I map each of these numbers to a g to the power of this number so so F so so f is an isomorphism okay and this this is really the meaning of this this blue part of the state sorry the the purple part of the

statement H that basically any group that is cyclic of order n it must be it must be isomorphic to integers modul n so there is up to isomorphism there is only one cly group of order n h and this this would be integer module in any questions about the the proposition

so we said that a cly group can be generated by more than one element and the question now we want to ask ourselves is how many possible generators are in integers mod n this is the next an element K in integers modu N is a

generator and when I say generator I I really mean that the group generated by K is the whole the whole ambient group if and only gcd of N and K is equal to one k gcd the the greatest common divisor is the the maximal positive integer that divides both n and K so this means that there's no other element in integers modulo n that

divides that divides M so so basically in order to be a generator this number multiplied by itself needs to produce all of the elements of uh integers modul n right ER not multiplied but but added because added okay yeah added sorry yeah my bad um I mean inde yeah so that so that means there should not if you pick I don't know a random number inside of uh integers modu n this is a generator if only if there's no other number within uh integers module n such that

this can be divided by any of the others does this make sense like you kind of need to make sure that this doesn't fult in a sub group or something like that or am I I think I mean the the statement you made is close but it's it's inaccurate eventually I mean a number is a generator if it if and only if it is co Prime to the modulus okay fair enough that makes sense this is called Co this is this is called co-prime co-prime numbers are numbers that do not have any common divisor well except except one right ER so so you you really need you really need a number that is copre to

the modulus in order to generate everything if and if you think of it just intuitively imagine that K would not be co-prime to the modulus then it would have some common divisor that is greater than one and then this common divisor once you take the power of K well you will get a I mean then K will have an order smaller than n yep okay so it if it will have an order smaller than n it could not generate everything but but we we will prove this

okay so you you maybe you can see the proof also for clarification so if K is a generator I mean actually this is this is equival since we want to prove an if and only if statement H let me put it as an an equivalence K is a generator um integers modu n is equal to 0

K up to nus1 * k um if GC D of N and K is bigger than one then I can write let's say this gcd I call GMA then I I can write n = gamma time S and K equals

gamma * T but then what I get is that s * K is s * gamma * T and S * gamma is is n so this is NT and this is zero modul but here s and t i mean s is strictly smaller than K

cannot have order in right if if I I found a number s that is smaller than n such that s * K is is zero module n then then K must must have an order that is smaller or equal to S which is which is smaller than n so this is a contradiction I mean so this is One Direction right if if the gcd of K and N is is bigger than one then then K is not a

generator um if the gcd which we call gamma of NN K is equal one we claim name numbers Zer 2K up to n minus one k are all well

otherwise let's say that SK is equal to TK for some s and t h smaller than n then m s minus minus t k equal to NX I mean they are equal module n

right so s- T * K is is Z mod n which means it's n * X for some X since K does not divide n i mean if they they have a a gcd equal one then in particular K cannot divide n so it means that K must divide X but a s minus

k which we assume to to be equal to n * X is going to be equal to n * K * y for s y so and now now I can I can uh I cancel out the k s minus t is is equal to Y sorry is equal to

zero modu n equal to n y equal to Z mod n so this this shows you that the set here in the blue box is a a set of of n distinct elements okay this of course this this last part is a contradiction I mean if s s minus t is

n n y for some Y and S and T are are strictly smaller than n well then then s T okay so this is all to say that we finish the proof and let me make a definition or in equals for n a natural number H the

oiler totient function is um this is denoted as F of n it's the number of all elements K such that K is strictly well is is smaller or equal than n bigger equal to gcd of N and K is equal to one okay this is a this is something you

can you can find on the internet or or there is like a Sage method that computes oil tsion tsion function so just in in other words using this umn is the number of is also the number of generators of distin generators of integers

module okay ER we are almost out of time so any questions about uh this last part all good and it seems that there's nothing in the chat either all right so uh uh let's stop here and meet next week