# Euler's totient function

1. Aug 4, 2014

### Dinheiro

1. The problem statement, all variables and given/known data
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?

2. Relevant equations
Number's theory equations

3. The attempt at a solution
$\phi(m) = m(1-1/p1)(1-1/p2)...$
where p|m

2. Aug 4, 2014

### Dick

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

3. Aug 4, 2014

### Dinheiro

So, without computers, no softer way?

4. Aug 4, 2014

### Dick

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.

Last edited: Aug 4, 2014
5. Aug 4, 2014

### Dinheiro

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

6. Aug 4, 2014

### Dick

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.

7. Aug 4, 2014

### Dick

Doh, wait. 53 is prime too. So?

Last edited: Aug 4, 2014