Noncototient
Encyclopedia
In mathematics, a noncototient is a positive integer n that cannot be expressed as the difference between a positive integer m and the number of coprime
integers below it. That is, m − φ(m) = n, where φ stands for Euler's totient function
, has no solution for m. The cototient of n is defined as n − φ(n), so a noncototient is a number that is never a cototient.
It is conjectured that all noncototients are even. This follows from a modified form of the Goldbach conjecture: if the even number n can be represented as a sum of two distinct primes p and q, then
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
integers below it. That is, m − φ(m) = n, where φ stands for Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
, has no solution for m. The cototient of n is defined as n − φ(n), so a noncototient is a number that is never a cototient.
It is conjectured that all noncototients are even. This follows from a modified form of the Goldbach conjecture: if the even number n can be represented as a sum of two distinct primes p and q, then
-
It is expected that every even number larger than 6 is a sum of distinct primes, so probably no odd number larger than 5 is a noncototient. The remaining odd numbers are covered by the observations
and 
.
The first few noncototients are:
1010 (number)10 is an even natural number following 9 and preceding 11.-In mathematics:Ten is a composite number, its proper divisors being , and...
, 2626 (number)26 is the natural number following 25 and preceding 27.- In mathematics :26 is the only positive integer that is one greater than a square and one less than a cube .A rhombicuboctahedron has twenty-six sides....
, 3434 (number)34 is the natural number following 33 and preceding 35.-In mathematics:34 is the ninth distinct semiprime and has four divisors including unity and itself. Its neighbors, 33 and 35, also are distinct semiprimes, having four divisors each, and 34 is the smallest number to be surrounded by numbers...
, 5050 (number)This article discusses the number fifty. For the year 50 CE, see 50. For other uses of 50, see 50 50 is the natural number following 49 and preceding 51.-In mathematics:...
, 5252 (number)52 is the natural number following 51 and preceding 53.-In mathematics:Fifty-two is the 6th Bell number and a decagonal number...
, 5858 (number)58 is the natural number following 57 and preceding 59.-In mathematics:Fifty-eight has an aliquot sum of 32 and is the second composite member of the 83-aliquot tree....
, 8686 (number)86 is the natural number following 85 and preceding 87.-In mathematics:86 is the 25th distinct semiprime and the 13th of the form...
, 100100 (number)100 is the natural number following 99 and preceding 101.-In mathematics:One hundred is the square of 10...
, 116116 (number)116 is the natural number following 115 and preceding 117.-In mathematics:116 is a noncototient, meaning that there is no solution to the equation , where stands for Euler's totient function. 116! + 1 is prime...
, 122122 (number)122 is the natural number following 121 and preceding 123.-In mathematics:It is a nontotient since there is no integer with exactly 122 coprimes below it...
, 130130 (number)130 is the natural number following 129 and preceding 131.-In mathematics:130 is a sphenic number. It is a noncototient since there is no answer to the equation x - φ = 130....
, 134134 (number)134 is the natural number following 133 and preceding 135.-In mathematics:134 is a nontotient since there is no integer with exactly 134 coprimes below it. And it is a noncototient since there is no integer with 134 integers with common factors below it...
, 146146 (number)146 is the natural number following 145 and preceding 147.-In mathematics:146 is an octahedral number as well as a composite number....
, 154154 (number)One hundred and fifty-four is the natural number following one hundred and fifty-three and preceding one hundred and fifty-five.-In mathematics:* 154 is a nonagonal number...
, 170170 (number)170 is the natural number following 169 and preceding 171.-In mathematics:170 is the smallest n for which φ and σ are both square. But 170 is never a solution for φ, making it a nontotient...
, 172172 (number)172 is the natural number following 171 and preceding 173.-In mathematics:* 172 is an even number* 172 is a composite number* 172 is a deficient number* 172 is a noncototient integer...
, 186, 202, 206, 218, 222222 (number)222 is the natural number following 221 and preceding 223. It is a repdigit composite number, and its factorization makes it a sphenic number. It is also a Harshad number....
, 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, 518, 520
Erdős and Sierpinski asked whether there exist infinitely many noncototients. This was finally answered in the affirmative by Browkin and Schinzel (1995), who showed every member of the infinite family
is an example. Since then other infinite families, of roughly the same form, have been given by Flammenkamp and Luca.
External links