Euler Totient problem

streethot · #1 $Old$ October 14th, 2009, 07:48 PM

Find all n such that:

$\varphi(n)=12$

chisigma · #2 $Old$ October 14th, 2009, 08:40 PM

The $\varphi(*)$ is a multiplicative function so that if m and n are coprime, then...

$\varphi(m\cdot n)= \varphi(m)\cdot \varphi(n)$ (1)

For $n=1$ and $n=2$ is $\varphi(n)=1$ and $\forall n>2$ $\varphi(n)$ is an even number, so that the solutions of the equation...

$\varphi (m\cdot n)=12$ (2)

... are obtained by systematic search of couples of coprime numbers m and n for which is...

$\varphi(m)=12, \varphi(n)=1$

$\varphi(m)=6, \varphi(n)=2$ (3)

Since $\varphi(13)=12$ solutions are...

$13 \cdot 1 =13$

$13\cdot 2 = 26$

Since $\varphi(7)=6$ also solutions are...

$7 \cdot 3 = 21$

$7 \cdot 4= 28$

$7 \cdot 6 = 42$

Finally is $\varphi (9)= 6$ so that solution is...

$9\cdot 4 = 36$

The numbers k for which is $\varphi(k)=12$ are...

$k=13,21,26,28,36,42$

Kind regards

$\chi$ $\sigma$

harkapobi · #3 $Old$ November 5th, 2009, 08:40 AM

Quote:

Originally Posted by chisigma $View Post$

The $\varphi(*)$ is a multiplicative function so that if m and n are coprime, then...

$\varphi(m\cdot n)= \varphi(m)\cdot \varphi(n)$ (1)

For $n=1$ and $n=2$ is $\varphi(n)=1$ and $\forall n>2$ $\varphi(n)$ is an even number, so that the solutions of the equation...

$\varphi (m\cdot n)=12$ (2)

... are obtained by systematic search of couples of coprime numbers m and n for which is...

$\varphi(m)=12, \varphi(n)=1$

$\varphi(m)=6, \varphi(n)=2$ (3)

Since $\varphi(13)=12$ solutions are...

$13 \cdot 1 =13$

$13\cdot 2 = 26$

Since $\varphi(7)=6$ also solutions are...

$7 \cdot 3 = 21$

$7 \cdot 4= 28$

$7 \cdot 6 = 42$

Finally is $\varphi (9)= 6$ so that solution is...

$9\cdot 4 = 36$

The numbers k for which is $\varphi(k)=12$ are...

$k=13,21,26,28,36,42$

$\chi$ $\sigma$

Hi, thank you for directing me here. Its good to see an example, but i dont understand this method.

Why do you multiply 7 by 3, 4 and 6? And how do you get $\phi(7) = 6$ and $\phi(9) = 6$ . I know you can easily work these out but aren't both of these just an instance of the same sort of question as $\phi(m) = 12$ ? Aren't there more $\phi(m) = 6$ ?

Sorry if i'm being a bit slow, all this is very confusing for me.

chisigma · #4 $Old$ November 5th, 2009, 09:20 PM

The basic assumptions are...

a) is $\varphi(n)=1$ only for $n=1$ and $n=2$ . For all $n>2$ , $\varphi (n)$ is an even number...

b) is $\varphi(m\cdot k)=\varphi(m)\cdot \varphi(k)$ if and only if m and k are coprime...

On the basis of b) the identification of an n for which $\varphi(n)=12$ is for the fact that must be $n=m\cdot k$ where m and k are coprime and $\varphi(m)\cdot \varphi(k) = 12$ . There are the following possibilities...

$\varphi(m)=12$ , $\varphi(k)=1$

$\varphi(m)=6$ , $\varphi(k)=2$

The situation...

$\varphi(m)=4$ , $\varphi(k)=3$

... as proposed by tonio in the original post, is impossible on the basis of a)...

Kind regards

$\chi$ $\sigma$