# Help with Euler's Phi function

1. Dec 11, 2011

### joshuathefrog

1. The problem statement, all variables and given/known data

Find x such that phi(x) = 5,000,000, where phi(x) is Euler's function.

2. Relevant equations

I know that if x is prime, then phi(x) = x-1.

Also, phi(pk) = pk - pk-1 = pk * (1 - 1/p).

3. The attempt at a solution

Since 5,000,001 is not a prime number (divisible by 3), I know that x is not a prime number, and so x must be composite.

Past this, I'm not really sure how to begin. The book that I'm using (Elementary Number Theory by Burton) includes lots of example for finding phi(whatever), but none for how to solve phi(x) = whatever. A nudge in the right direction would be helpful!

2. Dec 11, 2011

### I like Serena

Welcome to PF, joshuathefrog!

Perhaps a useful observation is that:
phi(pk) = pk-1(p-1)

Another observation is that it will probably not be a unique number to yield 5000000.
So let's just try to construct some number that would satisfy the equation.

Which and how many prime factors can you find in the resulting number?
Assuming such a prime factor is a repeated factor, which extra factor would you find in the resulting number?

Last edited: Dec 11, 2011
3. Dec 11, 2011

### joshuathefrog

Thanks for the response. I don't have to find ALL solutions to the problem. I just need to find one solution, or, if no solutions exist, prove that no solutions exist.

I know that the prime factorization of 5,000,000 is 26 * 57. But, I don't yet see what I can do with this information.

4. Dec 11, 2011

### I like Serena

Well, can you fit pk-1(p-1) to it?

5. Dec 11, 2011

### joshuathefrog

Since phi is multiplicative, I could say that phi(26)*phi(57) = 25(1) * 56(4) = 32(15625)(4) = 2,000,000.

Would this be going in the right direction towards a solution?

6. Dec 11, 2011

### I like Serena

You're starting from the wrong end.
You're taking phi from the resulting number, but you need a number x such that if you take phi you get the resulting number.

Suppose phi(x)=phi(pm qn).
What will the resulting number be?
And how should you choose the powers m and n, so you can get a match with 5000000?

7. Dec 11, 2011

### joshuathefrog

Ah, ok.

So, I think that if I let p=2 and q=5, and m=5 and n=8, then

phi(2558) = 24(1)57(4) = 245722 = 2657 = 5,000,000.

So, my answer would be x = 2558. Look ok?

8. Dec 11, 2011

### I like Serena

Yep!

9. Dec 11, 2011

### joshuathefrog

Fantastic! Thanks for the help!

10. Dec 11, 2011

### joshuathefrog

I'm trying to solve other problems of the same type. I have that phi(x) = 13,000,000.

Since the prime factorization of 13,000,000 is 265613, I wrote that phi(2l)phi(5m)phi(13n) = 2l-1(1)5m-1(4)13n-1(12).

I can express 4 as 22, but 12 = 3*22, and I don't see how to get 3 out of the right side of the equation.

Thoughts?

11. Dec 13, 2011

### joshuathefrog

Another thought here:

I have that l=1, m=7, and n=3, such that phi(23)*phi(57)*phi(13) = 26 * 56 * 13 * 3.

I want to divide the 3 out so that I am only left with the prime factorization of 13,000,000 on the right hand side. However, there does not exist a y such that phi(y) = 3. Therefore, this problem has no solution.

Does think sound right, or am I making a mistake here?

12. Dec 14, 2011

### I like Serena

You deduced that 13 cannot be a prime factor of x, since that would give you a redundant factor 3.

So what about for instance 4x13+1=53?
phi(53)=4x13.

13. Dec 14, 2011

### joshuathefrog

I figured out my mistake. I was letting l=1 when really I meant that l=2. I know that phi(60 = 48, so I divide the right side by 48 and divide the left side by phi(60). That solves the problem.

Just a stupid mistake. But thanks for the help!!

14. Dec 14, 2011

### joshuathefrog

That should have read phi(65) = 48.