i.e. Find the least integer $B$ such that $4B$ is not in the image of $\phi$. The original problem is to find a $B$ such that $4B$ is not an order for some multiplicative group $\mathbb{Z}^*_{n}$. The answer is $B=17$.

I had read the two reference below.

How to solve the equation $\phi(n) = k$?

Some remarks on Euler’s totient function

But I do not know where to start to tackle this problem.

I suppose it may related to the fact that

if $\gcd(m, n) = 1$, then $\phi(mn) = \phi(m) \phi(n)$.

So we may start with $\phi(5)=4$
But at second thought, if $gcd(m, n) \neq 1$, the there is factor as $gcd(m,n)\over \phi( gcd(m,n) )$, which can had factor of 4. My qeustion is, besides try and error, is there other way to find $B$ by hand?

  • $\begingroup$ The even nontotients are given in oeis.org/A005277. $68$ is the first one divisible by $4$. From the comments "If p is prime then the following two statements are true. I. 2p is in the sequence iff 2p+1 is composite (p is not a Sophie Germain prime). II. 4p is in the sequence iff 2p+1 and 4p+1 are composite. - Farideh Firoozbakht, Dec 30 2005" You can verify that $68$ satisfies II $\endgroup$ – Ross Millikan May 1 '17 at 19:42
  • $\begingroup$ Thank alot. The "4p is in the sequence iff 2p+1 and 4p+1 are composite" apply to the conidtion B is prime. How abot the case B is not a prime? $\endgroup$ – Rikeijin May 1 '17 at 19:51
  • $\begingroup$ Then it takes more work. You use the prime factorization of B and reflect on the link between the prime factorization of B and $\phi(B)$ and the multiplicative nature of $\phi$. $\endgroup$ – Ross Millikan May 1 '17 at 19:54

First prove that $B=17$ satisfies the requirement, so there is no $n$ with $\phi(n)=68$. As $\phi$ is multiplicative, to get a factor $17$ in $\phi(n)$ you either need $17^2$ dividing $n$, but then you get four factors of $2$ in $\phi(n)$, or a prime of the form $2\cdot 17+1$ or $4 \cdot 17 +1$, but those are not prime. Any higher prime of the form $17k+1$ will give more factors besides $17$ than $4$. Now just show that all smaller B fail by displaying an $n$ with the proper $\phi(n)$. $\phi(5)=4, \phi(16)=8,$ etc. They are not hard to find for small numbers if you think about the link between prime factorization and totient.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.