Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Euler's totient function has a lower bound for large values, but is there any way to pick out maximums for specific values of the function?

That is, how would I find the maximum number n such that phi(n) = 1000, for example?

share|improve this question
    
You'd probably have to utilize the prime factorizations of the numbers $p-1$ for primes $p$. –  anon Oct 31 '11 at 5:43
    
The sequence you're looking for is at oeis.org/A006511 -- although there are no references there. There's some Mathematica code but it looks like it relies on Mathematica's "phiinv" function. You might want to try looking for references to the "inverse totient" function. –  Michael Lugo Oct 31 '11 at 23:47
    
so that sequence suggests phi(7814) = 1000...is there no easy way to confirm that this is indeed the largest then? –  donnyton Nov 1 '11 at 6:31
    
You must be misreading the reference. Try to factor 7814, and see whether it's actually the case that $\phi(7814)=1000$. –  Gerry Myerson Nov 1 '11 at 21:32

2 Answers 2

This could be a hard problem, in general, but let's look at 1000.

$n$ can't be odd, since we'd have $2n\gt n$ and $\phi(2n)=\phi(n)$. Let $n=2m$.

$m$ can't have more than 3 distinct prime factors, since that would force $\phi(n)$ to be divisible by $2^4$, which it isn't.

If $p$ is prime and $p^2$ divides $n$ then $p$ divides $\phi(n)$ so $p$ is 2 or 5.

Now you can start loking at the numbers $2^r5^s$ for $r=1,2,3$ and $s=0,1,2,3$ to see which ones are $\phi(p)$ for some prime $p$ (other than 2 and 5, which can be treated separately). So for example, $\phi(11)=10$, $\phi(101)=100$, $\phi(41)=40$, and so on. Once you have the whole (finite) list, you can test the ways of putting together products of these numbers (and powers of 2 and/or 5) to see how to get $\phi(n)=1000$ and which way maximizes $n$.

It's a bit ad hoc, but I'm not sure that can be helped.

share|improve this answer
4  
@anon, it might be speedier, but it would miss $n=2\cdot3\cdot5^4=3750$. I didn't say $n$ was of the form $2^r\cdot5^s$, I said it was a product of primes (and prime powers) with $\phi(p)$ of that form. –  Gerry Myerson Oct 31 '11 at 11:50

Combining Theorem 329 in Hardy and Wright with the upper bound on $\sigma(n)$ in Robin (1984), we get $$ \phi(n) > \frac{6 n \log \log n}{\pi^2 \left( e^\gamma (\log \log n)^2 + 0.6482 \right)},$$ where $\gamma = 0.5772156649...$ is the Euler-Masceroni constant.

As a result, $\phi(n) > 1000$ unless $ n \leq 6872.$

I'm just saying.

1111 = 11 * 101  phi =  1000 = 2^3 * 5^3
1255 = 5 * 251  phi =  1000 = 2^3 * 5^3
1375 = 5^3 * 11  phi =  1000 = 2^3 * 5^3
1875 = 3 * 5^4  phi =  1000 = 2^3 * 5^3
2008 = 2^3 * 251  phi =  1000 = 2^3 * 5^3
2222 = 2 * 11 * 101  phi =  1000 = 2^3 * 5^3
2500 = 2^2 * 5^4  phi =  1000 = 2^3 * 5^3
2510 = 2 * 5 * 251  phi =  1000 = 2^3 * 5^3
2750 = 2 * 5^3 * 11  phi =  1000 = 2^3 * 5^3
3012 = 2^2 * 3 * 251  phi =  1000 = 2^3 * 5^3
3750 = 2 * 3 * 5^4  phi =  1000 = 2^3 * 5^3
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

One thing I noticed after the fact is that 41 does not appear. This is as it should be. For 2 and powers of 2, we have $\phi(2^{k+1} = 2^k.$ However, for any odd prime $p$ such as 5, it is not possible to have any $\phi(n) = p$ or $\phi(n) = p^2$ or, in general, $\phi(n) = p^k.$ In particular it is impossible to have $\phi(n) = 25.$ As a result, if $\phi(n) = 1000,$ it is impossible to have $41 | n.$ Oh, any prime dividing this $n$ must have $(p-1) | 1000,$ and if the exponent is going to be larger than 1 we also need $p | 1000.$ So, with 41, the exponent is 1, and we then need to find some relatively prime $m$ with $\phi(m) = 25,$ impossible.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.