euler phi function
This is a topic that many people are looking for. thevoltreport.com is a channel providing useful information about learning, life, digital marketing and online courses …. it will help you have an overview and solid multi-faceted knowledge . Today, thevoltreport.com would like to introduce to you Euler totient function made easy. Following along are instructions in the video below:
here are the four problems that Ill go through today this is the euler totient function and we use the Greek letter Phi to represent it and so often well just say in the case of the first question what is Phi 41 so lets talk about Phi with the orientation function in English its the number of integers between 1 and n whose GCD within is 1 if youd like to look at it more mathematically we can create a set and these two vertical lines mean we count the number of elements of the set and its the set of X from where X is between 1 and n and the GCD of X and n is equal to 1 so a simple example is 5/6 were concerned with the numbers between 1 & 6 so we write them down underneath we just write the GCD of those numbers with the number 6 and you can see theres only two that have a GCD of 1 and so 5 6 is equal to 2 now this works well for 6 we can count it that way but once you get into bigger numbers you need some rules that make it easier so the first rule were going to use is this one if P is a prime then Phi of P is equal to P minus 1 and we can use that for our first problem which Ive indicated here 541 so solution the number 41 is prime so 541 is equal to 41 minus 1 which is equal to 40 and you can probably see why that is 41 is prime it only has two divisors 1 and 41 itself so every number between 1 and 40 has a GCD of 1 with the number 41 before I go on to number 2 just remind you Ive got tons and tons of videos for our first and second year university students how things work fun mathematics a whole lot of things so have a look at that if youre interested lets go under our second question now where were asked to calculate 5 32 and 32 its not a prime number so we cant use a real one but what we can do is use our l2 and that says that if P to the N is a prime power then Phi of P to the N is equal to P to the N minus P to the N minus 1 and
you sort of see why thats true weve got P to the N minus P the N minus 1 well let PD n is the actual number that were trying to get the result for and what were taking off is P to the N minus 1 and thats the number of times P to the N is divisible by P so you might think about that later and you probably get comfortable with this with this rule and we can use that now for 532 because 32 is a prime power so heres a solution we have 32 equals 2 to the 5 so 5 32 equals to the 5 months to the 4 equals 16 okay now lets go on to the next one 535 this is actually a very interesting one because its the product of two prime numbers and it turns out that this is arguably this rule Im going to show you Rule three is arguably the most financially important equation in the history of mankind its arguable but its probably one of them because it underpins most of the encryption that we use today if youre interested at a intro level have a look at my video the life of prime part 1 if you want something a little bit harder have a look at how encryption works and if you want the whole all the gory details have a look at RSA code made easy and youll see where the oiler totient function comes into it but anyway our rule number 3 tells us what to do if weve got weve got the product of two numbers that are co-prime or the GCD of those two numbers is equal to 1 so it says that if the GCD of M and n is equal to 1 in 5 n times n is just equal to 5 m times 5 in so we can use that in in this case because weve got 4 35 is equal to 5 7 times 5 equals 5 7 times 5 5 we can use that rule 3 because 7 & 5 have a GCD of 1 and now we just go 7 minus 1 times 5 minus 1 which is the rule for the primes and we get 24 great nearly nearly done just thought Id put this up this is just something Im been working on lately and trying to sort something out and you can see there theres the Phi
got their fights its ugly its a phi of a flawed expression here in on a / j its really really messy I dont think Im going to be able to work it out but I just wanted you to see that this Euler tation function does come up very often in number theory type papers okay now lets go on to Phi of 600 now theres no new rules here we just have to use the rules that weve got so far so what we can do is firstly lets Express 600 as the product of 2 to the 3 times 3 times 5 squared and now we can look at the two skewed and the 3 and say well the GCD of 2 cubed + 3 is 1 and the GCD of 3 and 5 squared is 1 and so we can actually split this up using rule 3 so we get 5 2 cubed times 5 3 times 5 5 squared now we can use in the case of 2 cubed we can use that prime power rule so we get 2 cubed – 2 squared 5 3 we just use the proper throw rule number one the prime rule you get 3 – 1 + 5 5 squared we can use the prime product rule and we get the answer of 160 now just before I finish up there is another way to do these problems but I dont normally recommend them the the rules that Ive given you are important rules to understand in terms of the sort of situations youll use the euler totient function at university so its important that you try and get comfortable with rules 1 2 & 3 but there is a formula for 5 in and it says this suppose the only prime numbers are prime divisors of n R P 1 P 2 3 2 PK then five in is just n times you can see it 1-1 on P times one minus one on P two and the product continues right up to one minus one on pk so let me just put that up for if we wanted to do that for 600 we could solve it in this way the only prime divisors of 602 three and five and you can see Ive done the calculations here fortunately I get the same answer 160 so thats it for the euler totient function made easy I hope you found it useful you
tags:
phi, randell, heyman, randellheyman, randell heyman, randal hayman, eulers theorem, arithmetic functions, number of coprime, discrete mathematics, finite ma…
Thank you for watching all the articles on the topic Euler totient function made easy. All shares of thevoltreport.com are very good. We hope you are satisfied with the article. For any questions, please leave a comment below. Hopefully you guys support our website even more.