# Nontotient Number

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

The smallest such number is 14.

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

Originally Posted by chiph588@
A nontotient number $\displaystyle n \in \mathbb{N}$ is a number such that there is no $\displaystyle x \in \mathbb{N}$ where $\displaystyle \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 $\displaystyle 3$. Because $\displaystyle \phi (x)$ is always even for $\displaystyle x>2$.
• Nov 30th 2008, 12:56 PM
chiph588@
whoops, i forgot to mention the trivial answer of odd numbers...
• Dec 2nd 2008, 11:39 AM
ThePerfectHacker
Quote:

Originally Posted by chiph588@
A nontotient number $\displaystyle n \in \mathbb{N}$ is a number such that there is no $\displaystyle x \in \mathbb{N}$ where $\displaystyle \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 $\displaystyle 2,4,6,8,10,12$ are all non-nontotient.
After that you need to show that $\displaystyle 14$ is a non-totient number.

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