Help with Euler's Phi function

In summary, the author is trying to find a number that satisfies the equation phi(x) = 5000000. He has found that if x is prime, then phi(x) = x-1. However, he is not sure how to find a solution for phi(x) = whatever when x is not prime. He needs a hint from the reader.
  • #1
joshuathefrog
14
0

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(pk) = pk - pk-1 = pk * (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!
 
Physics news on Phys.org
  • #2
Welcome to PF, joshuathefrog! :smile:

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:
  • #3
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
Well, can you fit pk-1(p-1) to it?
 
  • #5
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
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
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
Yep! :smile:
 
  • #9
Fantastic! Thanks for the help!
 
  • #10
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
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
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
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
That should have read phi(65) = 48.
 

FAQ: Help with Euler's Phi function

What is Euler's Phi function?

Euler's Phi function, also known as the totient function, is a mathematical function that counts the number of positive integers less than or equal to a given number that are relatively prime to that number.

How is Euler's Phi function calculated?

Euler's Phi function is calculated by finding the prime factorization of a given number and using the formula φ(n) = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pk), where n is the given number and p1, p2, ..., pk are the distinct prime factors of n.

What is the significance of Euler's Phi function?

Euler's Phi function has a variety of applications in number theory, cryptography, and other fields of mathematics. It is also a fundamental tool in the study of modular arithmetic.

Can Euler's Phi function be used for large numbers?

Yes, Euler's Phi function can be used for large numbers. However, as the number gets larger, the calculation becomes more complex and time-consuming.

Are there any other functions similar to Euler's Phi function?

Yes, there are several other functions that are similar to Euler's Phi function, such as Carmichael's function and Möbius function. These functions also involve counting the number of positive integers that are relatively prime to a given number.

Similar threads

Replies
11
Views
2K
Replies
2
Views
1K
Replies
3
Views
1K
Replies
2
Views
2K
Replies
11
Views
2K
Back
Top