Help with Euler's Phi function

[joshuathefrog]

Homework Statement

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

Homework Equations

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

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

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!

 

[I like Serena]

Welcome to PF, joshuathefrog!

Perhaps a useful observation is that:
phi(p^k) = p^k-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?

 

[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 2⁶ * 5⁷. But, I don't yet see what I can do with this information.

 

[I like Serena]

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

 

[joshuathefrog]

Since phi is multiplicative, I could say that phi(2⁶)*phi(5⁷) = 2⁵(1) * 5⁶(4) = 32(15625)(4) = 2,000,000.

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

 

[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(p^m qⁿ).
What will the resulting number be?
And how should you choose the powers m and n, so you can get a match with 5000000?

 

[joshuathefrog]

Ah, ok.

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

phi(2⁵5⁸) = 2⁴(1)5⁷(4) = 2⁴5⁷2² = 2⁶5⁷ = 5,000,000.

So, my answer would be x = 2⁵5⁸. Look ok?

 

[I like Serena]

Yep!

 

[joshuathefrog]

Fantastic! Thanks for the help!

 

[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 2⁶5⁶13, I wrote that phi(2^l)phi(5^m)phi(13ⁿ) = 2^l-1(1)5^m-1(4)13^n-1(12).

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

Thoughts?

 

[joshuathefrog]

Another thought here:

I have that l=1, m=7, and n=3, such that phi(2³)*phi(5⁷)*phi(13) = 2⁶ * 5⁶ * 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?

 

[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.

 

[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!

 

[joshuathefrog]

That should have read phi(65) = 48.