In number theory, a nontotient is a positive integer n which is not a totient number: it is not in the image of Euler's totient function φ, that is, the equation φ(x) = n has no solution x. In other words, n is a nontotient if there is no integer x that has exactly n coprimes below it. All odd numbers are nontotients, except 1, since it has the solutions x = 1 and x = 2. The first few even nontotients are this sequence:
: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, ...
The least value of k such that the totient of k is n are (0 if no such k exists) are this sequence:
: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, ...
The greatest value of k such that the totient of k is n are (0 if no such k exists) are this sequence:
: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, ...
The number of ks such that φ(k) = n are (start with n = 0) are this sequence:
:0, 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, ...
Carmichael's conjecture is that there are no 1s in this sequence.
An even nontotient may be one more than a prime number, but never one less, since all numbers below a prime number are, by definition, coprime to it. To put it algebraically, for p prime: φ(p) = p − 1. Also, a pronic number n(n − 1) is certainly not a nontotient if n is prime since φ(p<sup>2</sup>) = p(p − 1).
If a natural number n is a totient, n · 2<sup>k</sup> is a totient for all natural numbers k.
There are infinitely many even nontotient numbers: indeed, there are infinitely many distinct primes p (such as 78557 and 271129, see Sierpinski number) such that all numbers of the form 2<sup>a</sup>p are nontotient, and every odd number has an even multiple which is a nontotient.
{|class="wikitable"
|n||numbers k such that φ(k) = n||n||numbers k such that φ(k) = n||n||numbers k such that φ(k) = n||n||numbers k such that φ(k) = n
|-
|1||1, 2||37||||73||||109||
|-
|2||3, 4, 6||38||||74||||110||121, 242
|-
|3||||39||||75||||111||
|-
|4||5, 8, 10, 12||40||41, 55, 75, 82, 88, 100, 110, 132, 150||76||||112||113, 145, 226, 232, 290, 348
|-
|5||||41||||77||||113||
|-
|6||7, 9, 14, 18||42||43, 49, 86, 98||78||79, 158||114||
|-
|7||||43||||79||||115||
|-
|8||15, 16, 20, 24, 30||44||69, 92, 138||80||123, 164, 165, 176, 200, 220, 246, 264, 300, 330||116||177, 236, 354
|-
|9||||45||||81||||117||
|-
|10||11, 22||46||47, 94||82||83, 166||118||
|-
|11||||47||||83||||119||
|-
|12||13, 21, 26, 28, 36, 42||48||65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210||84||129, 147, 172, 196, 258, 294||120||143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396, 450, 462
|-
|13||||49||||85||||121||
|-
|14||||50||||86||||122||
|-
|15||||51||||87||||123||
|-
|16||17, 32, 34, 40, 48, 60||52||53, 106||88||89, 115, 178, 184, 230, 276||124||
|-
|17||||53||||89||||125||
|-
|18||19, 27, 38, 54||54||81, 162||90||||126||127, 254
|-
|19||||55||||91||||127||
|-
|20||25, 33, 44, 50, 66||56||87, 116, 174||92||141, 188, 282||128||255, 256, 272, 320, 340, 384, 408, 480, 510
|-
|21||||57||||93||||129||
|-
|22||23, 46||58||59, 118||94||||130||131, 262
|-
|23||||59||||95||||131||
|-
|24||35, 39, 45, 52, 56, 70, 72, 78, 84, 90||60||61, 77, 93, 99, 122, 124, 154, 186, 198||96||97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420||132||161, 201, 207, 268, 322, 402, 414
|-
|25||||61||||97||||133||
|-
|26||||62||||98||||134||
|-
|27||||63||||99||||135||
|-
|28||29, 58||64||85, 128, 136, 160, 170, 192, 204, 240||100||101, 125, 202, 250||136||137, 274
|-
|29||||65||||101||||137||
|-
|30||31, 62||66||67, 134||102||103, 206||138||139, 278
|-
|31||||67||||103||||139||
|-
|32||51, 64, 68, 80, 96, 102, 120||68||||104||159, 212, 318||140||213, 284, 426
|-
|33||||69||||105||||141||
|-
|34||||70||71, 142||106||107, 214||142||
|-
|35||||71||||107||||143||
|-
|36||37, 57, 63, 74, 76, 108, 114, 126||72||73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270||108||109, 133, 171, 189, 218, 266, 324, 342, 378||144||185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630
|}
References
- L. Havelock, A Few Observations on Totient and Cototient Valence from PlanetMath