3
$\begingroup$

How do I show that there are infinitely many even numbers which are nontotients ?

I have proved that $\phi(n)$ is even $\forall\space n>2$ by showing that for the set $Z_n^*$ of all natural numbers less that and coprime to $n,\space |Z_n^*|$ is even.

This I did by showing that $1\in Z_n^*, \space n-1 \in Z_n^*$ and $\forall x \in Z_n^*, \space x^{-1} mod \space n \in Z_n^*$. Also $\forall x \ne {1,n-1} \space x\ne x^{-1}$.

I am unable to think of a way to prove that there are infinitely many even numbers k such that $\forall n \space \phi(n) \ne k$

$\endgroup$
1
  • $\begingroup$ Here are some infinite subsets of nontotients: oeis.org/A005277 Maybe you could start with these. $\endgroup$ – Dzoooks Aug 15 '18 at 18:07
3
$\begingroup$

Suppose, $N=2p$ where $p\ge 5$ is prime and $2p+1$ is not prime. To ensure that $2p+1$ is not prime, it is enough to choose $p\equiv 1\mod 3$

If $\varphi(M)=N$ , then for every prime factor $q\mid M$ we have $q-1\mid N$

Hence , only the prime factors $2$ and $3$ are possible because neither $p+1$ nor $2p+1$ is prime.

But if $M$ only has prime factors $2$ and $3$, $\varphi(M)$ must be a power of $2$ contradicting $\varphi(M)=2p$. Hence , $N$ is a non-totient.

$\endgroup$
1

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.