# Nontotient Number

• November 30th 2008, 12:20 PM
chiph588@
Nontotient Number
A nontotient number $n \in \mathbb{N}$ is a number such that there is no $x \in \mathbb{N}$ where $\phi(x) = n$.

The smallest such number is 14.

My question is how would one prove whether a number is nontotient or not?
• November 30th 2008, 12:50 PM
ThePerfectHacker
Quote:

Originally Posted by chiph588@
A nontotient number $n \in \mathbb{N}$ is a number such that there is no $x \in \mathbb{N}$ where $\phi(x) = n$.

The smallest such number is 14.

My question is how would one prove whether a number is nontotient or not?

I disagree. The smallest number is $3$. Because $\phi (x)$ is always even for $x>2$.
• November 30th 2008, 12:56 PM
chiph588@
whoops, i forgot to mention the trivial answer of odd numbers...
• December 2nd 2008, 11:39 AM
ThePerfectHacker
Quote:

Originally Posted by chiph588@
A nontotient number $n \in \mathbb{N}$ is a number such that there is no $x \in \mathbb{N}$ where $\phi(x) = n$.

The smallest such number is 14.

My question is how would one prove whether a number is nontotient or not?

You first need to show that $2,4,6,8,10,12$ are all non-nontotient.
After that you need to show that $14$ is a non-totient number.

We want $n$ so that $\phi (n) = 14$.
Write $n = p_1^{a_1}\cdot ... \cdot p_m^{a_m}$.
Then we have $\phi (n) = p_1^{a_1-1} \cdot ... \cdot p_m^{a_m - 1}(p_1-1)(p_2 - 1)...(p_m -1) = 2\cdot 7$.
The RHS has only one factor of $2$.
Therefore we cannot have $m\geq 2$ where $p_i$ are odd primes.
The RHS has also a factor of $7$.
This forces $n=2^a 7^b$ where $a=0,1$ and $b=0,1$.
This never works to give $\phi(n) = 14$.
Thus, $14$ is nontotient.