Recalling Sir E u l e r Euler

What is the maximum value of Euler's Totient Function ϕ ( n ) \phi(n) , for n 500 n\le500 ?


The answer is 498.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

7 solutions

Parth Lohomi
Dec 13, 2014

n n = a p a^{p} × \times b q b^{q} .....

ϕ ( n ) \phi(n) = n × ( 1 1 a n\times(1-\dfrac{1}{a} )( 1 1 b 1-\dfrac{1}{b} )........

ϕ ( n ) \phi(n) is [ n 1 n-1 ] for n n being a prime number so largest prime number \le 500 500 is 499 \color{#3D99F6}{499} so

ϕ ( n ) m a x \phi(n)_{max} = ϕ ( 499 ) \phi(499) = 498 \boxed{498}

Same method but is there a way to verify that it is indeed the maximum?

Marc Vince Casimiro - 6 years, 6 months ago

Log in to reply

Can be done using induction

Parth Lohomi - 6 years, 6 months ago

Log in to reply

Ah, I thought of it because of another problem like this but it was greater than 500. I think it was the minimum value so it must not have been a prime.

Marc Vince Casimiro - 6 years, 6 months ago

Log in to reply

@Marc Vince Casimiro This problem is based on that..... Actually I saw that you Reshare it so I created this problem!!

Parth Lohomi - 6 years, 6 months ago

well, one thing that i could observe in the expression of totient function......except the number n, product of all other expressions is less than 1 ..... so any number between 1 and 500 which has factors cannot give max value .... hence the prime (of course the largest) has to give max value.

Abhinav Raichur - 6 years, 6 months ago

Yes. Check my solution @Marc Vince Casimiro

Satvik Golechha - 6 years, 6 months ago
Kalpok Guha
Dec 14, 2014

As we know ϕ ( n ) \phi(n) =n - 1 if n is prime. The the maximum value of Euler's Totient Function ϕ ( n ) \phi(n) for n 500 n\le500 , ϕ ( n ) \phi(n) where n is largest prime <500. n=499 then ϕ ( 499 ) \phi(499) =498.

Satvik Golechha
Dec 14, 2014

We have n 500 n\le500 .

ϕ ( n ) \phi(n) is number of numbers less than and co-prime to n n . ϕ ( n ) \phi(n) will definitely be less than 500 500 .

Let n = a 1 p 1 × a 2 p 2 × . . . . . . . . . . . × a n p n n={a_1}^{p_1} \times {a_2}^{p_2} \times ........... \times {a_n}^{p_n}

ϕ ( n ) = n ( 1 1 p i ) . \phi(n)=n\prod \left(1-\dfrac{1}{p_i}\right).

It is evident that the more the number of factors of n n , the lesser is the value of ϕ ( n ) \phi(n) .

Thus, n n should have as less factors as possible, that is, n n should be a prime.

Largest prime less than 500 500 is 499 499 . ϕ ( 499 ) = 498 \phi(499)=\boxed{498} .

Rindell Mabunga
Dec 14, 2014

Euler's Totient Function of n is the number of integers x that are coprime to n. Therefore Euler's Totient Function of n is always less than n. Since 499 is the highest prime number less than 500 and there will be no Euler's Totient Function of integers less than 499 that are greater than 499, the Euler's Totient Function of 499 is the maximum value which is equal to 499 - 1 = 498

Adarsh Kumar
Dec 13, 2014

ϕ ( n ) \phi{(n)} stands for the number of integers n \leq n that are co-prime to n . n. Now,more the number of factors of n n ,the lesser the number of integers that are co-prime to it and also less than it.Thus,we are looking for the number which is 500 \leq 500 and has very less factors.Now,we know that a prime number has the least number of factors.Thus, n = n= a prime number.The number of integers that are \leq and co-prime to a prime p p are 1 , 2 , 3 , 4...... ( p 1 ) 1,2,3,4...... (p-1) .That is a total of ( p 1 ) (p-1) numbers.Thus, ϕ ( p ) = p 1 \phi(p)=p-1 for a prime number p . p. The largest prime 500 = 499. \leq 500=499. Thus,answer = ϕ ( 499 ) = 498. =\phi{(499)}=498.

How is p co-prime to p?

Sudipto Banerjee - 6 years, 6 months ago

Log in to reply

Yes,you are right,they aren't.

Adarsh Kumar - 6 years, 6 months ago
Mukul Rathi
Dec 23, 2014

Recall that the totient function of a prime p is p-1. Since 499 is prime, we have the largest value being 499-1=498

Rohit Bhagwat
Dec 14, 2014

Euler Totient function for prime p is p-1 so finding the answer boils down to finding the largest prime less than 500 which in this case is 499 hence the answer is 498.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...