Nontotient

In number theory , the totient of a natural number is defined as the number of coprime natural numbers that are not greater than . is also called Euler's phi function . A nontotient (from the English nontotient ) is a natural number that is not a totient, i.e. a number for the equation ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varphi }$ ${\displaystyle n}$

${\displaystyle \varphi (x)=n}$

has no solution for . In other words: a natural number is a nontotient if there is no natural number for which there are exactly coprime numbers . ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle \leq x}$

Examples

• The number is a nontotient because there is no natural number for which there are exactly coprime numbers that are smaller than . ${\displaystyle n=7}$ ${\displaystyle x}$ ${\displaystyle n=7}$ ${\displaystyle x}$
• The number is not a nontotient: ${\displaystyle n=4}$

The prime number is relatively prime to numbers, so is also . So the equation has at least one solution , so it is not a nontotient. More must not be sought (although the numbers , and the Totienten had). ${\displaystyle p=5}$ ${\displaystyle p-1=4}$ ${\displaystyle \varphi (5)=4}$ ${\displaystyle \varphi (x)=n=4}$ ${\displaystyle x=5}$ ${\displaystyle n=4}$ ${\displaystyle x}$ ${\displaystyle x_{2}=8}$ ${\displaystyle x_{3}=10}$ ${\displaystyle x_{4}=12}$ ${\displaystyle n=4}$

• The number is not a nontotient: ${\displaystyle n=1}$

As a special case of the empty product (neither a prime number nor a composite number), the number is also coprime to itself, so is . In addition, the number is too prime, so is too . So the equation even has two solutions and , so is not a nontotient. ${\displaystyle x=1}$ ${\displaystyle \varphi (1)=1}$ ${\displaystyle x=2}$ ${\displaystyle 1}$ ${\displaystyle \varphi (2)=1}$ ${\displaystyle \varphi (x)=n=1}$ ${\displaystyle x_{1}=1}$ ${\displaystyle x_{2}=2}$ ${\displaystyle n=1}$

• The following numbers are the smallest even nontotients:

14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, 302, 304, 308, 314, 318, ... (sequence A005277 in OEIS )

• The next list gives the smallest , whose totient is (for ascending ) ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=1,2,3,\ldots }$

1, 3, 0 , 5, 0 , 7, 0 , 15, 0 , 11, 0 , 13, 0 , 0 , 0 , 17, 0 , 19, 0 , 25, 0 , 23, 0 , 35, 0 , 0 , 0 , 29, 0 , 31, 0 , 51, 0 , 0 , 0 , 37, 0 , 0 , 0 , 41, 0 , 43, 0 , 69, 0 , 47, 0 , 65, 0 , 0 , 0 , 53, 0 , 81, 0 , 87, 0 , 59, 0 , 61, 0 , 0 , 0 , 85, 0 , 67, 0 , 0 , 0 , 71, 0 , 73, 0 , 0 , 0 , 0 , 0 , 79, 0 , 123, 0 , 83, 0 , 129, 0 , 0 , 0 , 89, ... (sequence A049283 in OEIS )

If one appears in the -th position in the above list , then it is a non-totient, because there is obviously no one whose totient is. ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$

• The next list gives the largest whose totient is (for ascending ) ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=1,2,3,\ldots }$

2, 6, 0 , 12, 0 , 18, 0 , 30, 0 , 22, 0 , 42, 0 , 0 , 0 , 60, 0 , 54, 0 , 66, 0 , 46, 0 , 90, 0 , 0 , 0 , 58, 0 , 62, 0 , 120, 0 , 0 , 0 , 126, 0 , 0 , 0 , 150, 0 , 98, 0 , 138, 0 , 94, 0 , 210, 0 , 0 , 0 , 106, 0 , 162, 0 , 174, 0 , 118, 0 , 198, 0 , 0 , 0 , 240, 0 , 134, 0 , 0 , 0 , 142, 0 , 270, 0 , 0 , 0 , 0 , 0 , 158, 0 , 330, 0 , ... (sequence A057635 in OEIS )

If one appears in the -th position in the above list , then it is a non-totient, because there is obviously no one whose totient is. ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$

• The following list indicates the number of different ones for which applies (for ascending ): ${\displaystyle k}$ ${\displaystyle \varphi (k)=n}$ ${\displaystyle n=1,2,3,\ldots }$

2, 3, 0 , 4, 0 , 4, 0 , 5, 0 , 2, 0 , 6, 0 , 0 , 0 , 6, 0 , 4, 0 , 5, 0 , 2, 0 , 10, 0 , 0 , 0 , 2, 0 , 2, 0 , 7, 0 , 0 , 0 , 8, 0 , 0 , 0 , 9, 0 , 4, 0 , 3, 0 , 2, 0 , 11, 0 , 0 , 0 , 2, 0 , 2, 0 , 3, 0 , 2, 0 , 9, 0 , 0 , 0 , 8, 0 , 2, 0 , 0 , 0 , 2, 0 , 17, 0 , 0 , 0 , 0 , 0 , 2, 0 , 10, 0 , 2, 0 , 6, 0 , 0 , 0 , 6, 0 , 0 , 0 , 3, ... (sequence A014197 in OEIS )

Example :

In the -th place is the number . This means that there are solutions to the equation . Thus is a nontotient. ${\displaystyle n=5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \varphi (k)=n=5}$ ${\displaystyle n=5}$

There is a conjecture by Robert Daniel Carmichael from 1907 which states that there are either no or at least two solutions to the equation for each (see Carmichael's conjecture about the totient function ( s )). The assumption is therefore equivalent to the fact that a 1 never appears in the above list. ${\displaystyle \varphi (x)=n}$ ${\displaystyle n}$

• A table follows, from which one can read off the nontotients a little easier. In the first column are the ascending numbers, in the second column are those numbers whose totient is and in the third column you can read the number of numbers in the second column. Every time there is a zero in this third column, i.e. if there are no numbers that have a totient , it is a nontotient (which is colored yellow): ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

properties

• Be a prime number . Then there is never a nontotient. ${\displaystyle p\in \mathbb {P} }$ ${\displaystyle p-1}$

Proof :

Every prime number is relatively prime to numbers (namely to all natural numbers which are smaller than ). Thus is and is the totient of . So is not a nontotient. ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle p}$ ${\displaystyle \varphi (p)=p-1}$ ${\displaystyle p-1}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle \Box }$

• Be a prime number . Then the number of the rectangle is never a nontotient. ${\displaystyle p\in \mathbb {P} }$ ${\displaystyle p\cdot (p-1)}$

Proof :

Because of the calculation rules for Euler's Phi function for prime powers one obtains . Thus is and is the totient of . So is not a nontotient. ${\displaystyle \varphi (p^{2})=p^{2}\cdot (1-{\frac {1}{p}})=p^{2}-p=p\cdot (p-1)}$ ${\displaystyle \varphi (p^{2})=p\cdot (p-1)}$ ${\displaystyle p(p-1)}$ ${\displaystyle p^{2}}$ ${\displaystyle p\cdot (p-1)}$ ${\displaystyle \Box }$

• All odd numbers except the number are nontotients. ${\displaystyle n=1}$
• For every natural number there is a prime number , so is a nontotient. ${\displaystyle m}$ ${\displaystyle p}$ ${\displaystyle mp}$
• There are infinitely many prime numbers , so all numbers are of the form with nontotients (such as the Sierpinski numbers and ). ${\displaystyle p}$ ${\displaystyle 2^{a}\cdot p}$ ${\displaystyle a\in \mathbb {N} }$ ${\displaystyle p=78557}$ ${\displaystyle p=271129}$
• Every odd number has an even multiple, which is a nontotient.
• There are infinitely many even nontotients (follows from the previous properties).

See also

• Euler's phi function
• Highly quoted number
• Highly touted number
• High composite number
• Non-cotient
• Perfect total number
• Scarce total number

Web links

• Eric W. Weisstein : Totient Function . In: MathWorld (English).
• Eric W. Weisstein : Nontotient . In: MathWorld (English).
• Arndt Brünner: subsets and prime factor decompositions, Euler's Phi function and faculties. Calculation of Euler's Phi function. Accessed February 15, 2020 (German). 
• Mingzhi Zhang: On Nontotients. Journal of Number Theory 43 (2), February 1993, pp. 168-172 , accessed February 26, 2020 . 

Individual evidence

1. ↑ Mingzhi Zhang: On Nontotients. Theorem 1. Journal of Number Theory 43 (2), February 1993, pp. 168-172 , accessed February 26, 2020 . 
2. ↑ Mingzhi Zhang: On Nontotients. Theorem 5. Journal of Number Theory 43 (2), February 1993, pp. 168-172 , accessed February 26, 2020 . 
3. ↑ Mingzhi Zhang: On Nontotients. Journal of Number Theory 43 (2), February 1993, pp. 168-172 , accessed February 26, 2020 .