Calculating Euler's Totient Function for Large Numbers: Is There a Better Way?

[Dinheiro]

Homework Statement

How would you calculate, without computers,
$\phi(m) = 12?$
Would you just try enough m integers one by one until it works?
What if m were bigger like
$\phi(m) = 52?$
Is there a softer way to solve without guessing the number?

Homework Equations

Number's theory equations

The Attempt at a Solution

$\phi(m) = m(1-1/p1)(1-1/p2)...$
where p|m

 

[Dick]

Homework Statement

How would you calculate, without computers,
$\phi(m) = 12?$
Would you just try enough m integers one by one until it works?
What if m were bigger like
$\phi(m) = 52?$
Is there a softer way to solve without guessing the number?

Homework Equations

Number's theory equations

The Attempt at a Solution

$\phi(m) = m(1-1/p1)(1-1/p2)...$
where p|m

Find the prime factorization. For numbers like these that's easy. Then use the formula you quoted in your attempt at a solution.

 

[Dinheiro]

So, without computers, no softer way?

 

[Dick]

So, without computers, no softer way?

For 12 and 52 you don't need a computer to factorize it. The prime factors of 12 are 2 and 3. So $\phi(12)$ is 12(1-1/2)(1-1/3)=4. I didn't need a computer for that. And it's certainly easier than checking all of the numbers from 1...12 to see if they are relatively prime to 12. What kind of numbers are you thinking about? If it's easy to factor it's easy to find the totient.

 

[Dinheiro]

Thanks, but note that
$\phi(m) = 12$
not m = 12.
I want to find m.
xD

 

[Dick]

Thanks, but note that
$\phi(m) = 12$
not m = 12.
I want to find m.
xD

I read the question badly. Sorry. 12 is easy. 13 is prime so $\phi(13)=12$. All I can suggest is try to use that phi is multiplicative. So if you want 52 then 52=2*26. So one factor should be a number that satisfies $\phi(m)=2$, plenty of those. Then you want another relatively prime m such that $\phi(m)=26$. So you can break it down somewhat. I'm sort of getting stuck there.

 

[Dick]

Doh, wait. 53 is prime too. So?