Non-cotient

The quotient of a number is defined as . It is the Euler phi function (also Totient from above) which indicates how many to prime natural numbers there are, as no larger are. The value thus indicates the number of natural numbers that have at least one prime factor in common. ${\displaystyle n}$ ${\displaystyle n-\varphi (n)}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-\varphi (n)}$ ${\displaystyle 0<x\leq n}$ ${\displaystyle n}$

In number theory , a non-cotient (from the English non-cotient ) is a natural number that is not a cotient, i.e. if the equation is ${\displaystyle n}$

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

has no solution for . In other words: is a non-cotient if there is no natural number for which there are exactly numbers that have at least one prime factor in common and are less than or equal to. ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x}$

Examples

• The cotients , i.e. the number of natural numbers that have at least one prime factor in common, are (for ): ${\displaystyle n-\varphi (n)}$ ${\displaystyle x<n}$ ${\displaystyle n}$ ${\displaystyle n=1,2,3,\ldots }$

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27,… (Follow A051953 in OEIS )

• The number is a non-cotient because there is no natural number for which there are exact numbers that have at least one prime factor in common and are less than or equal to. ${\displaystyle n=10}$ ${\displaystyle x}$ ${\displaystyle n=10}$ ${\displaystyle x}$ ${\displaystyle x}$
• The number is not a non-cotient: ${\displaystyle n=12}$

The number is relatively prime to the six numbers , with all other 12 numbers, which are smaller or equal , it has a prime factor in common. So is . The quotient of the number is therefore the same . So is not a non-cotient. More must not be sought (though and the Kototienten had). ${\displaystyle x=18}$ ${\displaystyle k\in \{1,5,7,11,13,17\}}$ ${\displaystyle x=18}$ ${\displaystyle 18-\varphi (18)=18-6=12}$ ${\displaystyle x=18}$ ${\displaystyle 12}$ ${\displaystyle n=12}$ ${\displaystyle x}$ ${\displaystyle x_{2}=20}$ ${\displaystyle x_{3}=22}$ ${\displaystyle n=12}$

• The following numbers are the smallest noncotients:

10, 26, 34, 50, 52, 58, 86, 100, 116, 122, 130, 134, 146, 154, 170, 172, 186, 202, 206, 218, 222, 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, ... (Follow A005278 in OEIS )

• The next list gives the smallest , whose cotient is (for ascending ; if there is no number with a cotient , the number 0 is given): ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=0,1,2,3,\ldots }$ ${\displaystyle n}$

1, 2, 4, 9, 6, 25, 10, 15, 12, 21, 0 , 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0 , 63, 52, 161, 42, 87, 48, 93, 0 , 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0 , 235, 0 , 329, 78, 159, 98, 105, 0 , 371, 84, 177, 122, 135, 96, 305, 90, 427, ... (sequence A063507 in OEIS )

If one appears at the -th position in the list above (where you have to start counting), then it is a non-cotient, because there is obviously no one whose cotient is (as for example at the 10th, 26th, 34th, 50th, 52nd and 58th positions, all of which are noncotients). ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n=0}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$

• The next list gives the largest , whose cotient is (for ascending ; if there is no number with a cotient , the number 0 is given; the value for is ∞, because all prime numbers have the cotient and there is therefore no largest number, whose cotient is): ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=0,1,2,3,\ldots }$ ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n=1}$ ${\displaystyle n=1}$

1, ∞, 4, 9, 8, 25, 10, 49, 16, 27, 0 , 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0 , 187, 52, 841, 58, 961, 64, 253, 0 , 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0 , 667, 0 , 2809, 106, 703, 104, 697, 0 , 3481, 118, 3721, 122, ... (sequence A063748 in OEIS )

If one appears at the -th position in the list above , it is a non-cotient as in the previous list (you have to start counting with). ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle n=0}$

• The next list gives the number of those whose cotient is (for ascending ): ${\displaystyle k}$ ${\displaystyle k-\varphi (k)=n}$ ${\displaystyle n=0,1,2,3,\ldots }$

1, ∞, 1, 1, 2, 1, 1, 2, 3, 2, 0 , 2, 3, 2, 1, 2, 3, 3, 1, 3, 1, 3, 1, 4, 4, 3, 0 , 4, 1, 4, 3, 3, 4, 3, 0 , 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0 , 3, 0 , 6, 2, 4, 2, 5, 0 , 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, 5, 1, 7, 1, 8, 1, 5, 2, 6, 1, 9, 2, 6, 0 , 4, 2, 10, 2, 4, 2, 5, 2, 7, 5, 4, 1, 8, 0 , 9, 1, 6, 1, 7, ... (sequence A063740 in OEIS )

Example:

In the 26th position of the above list (you have to start counting) is the number . This means that there are numbers whose cotient is the same . Thus is a non-cotient. ${\displaystyle n=0}$ ${\displaystyle k=0}$ ${\displaystyle 0}$ ${\displaystyle n=26}$ ${\displaystyle n=26}$

• The following is a table from which it is easier to read off the non-cotients. In the first column are the ascending numbers, in the second column are those numbers whose cotient is and in the third column you can read off the number of numbers that are in the second column. Every time there is a zero in this third column, i.e. if there are no numbers that have a cotient, it is a non-cotient (which is colored yellow): ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

properties

• There are an infinite number of non-cotients.

The question on this answer was raised in 1959 by Wacław Sierpiński and in 1973 by Paul Erdős and answered by Jerzy Browkin and Andrzej Schinzel in 1995, who were able to show that all numbers of the form are with natural non-cotients. In 2000 Achim Flammenkamp and Florian Luca were able to add more infinite families , all of which are non-cotient: ${\displaystyle 2^{k}\cdot 509203}$ ${\displaystyle k\geq 1}$

Be a natural number. Then all numbers are of the form with non-cotients (the numbers in the set brackets are all trickle numbers ). ${\displaystyle m\geq 1}$ ${\displaystyle n=2^{m}\cdot k}$ ${\displaystyle k\in \{509203,2554843,9203917,9545351,10645867,11942443,65484763\}}$

assumptions

• It is believed that all non-cotients are even numbers. That would follow from Goldbach's strong conjecture : If it is odd, then, according to Goldbach's conjecture, for two prime numbers would be and . Then there would be a cotient. The consequence of Goldbach's conjecture is that all odd numbers would be cotients, that is, conversely, all non-cotients would have to be even. ${\displaystyle n}$ ${\displaystyle n+1=p+q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle pq-\varphi (pq)=pq-(p-1)(q-1)=p+q-1=n}$

See also

• Euler's phi function
• Highly quoted number
• Highly touted number
• High composite number
• Nontotient
• Perfect total number
• Scarce total number

Web links

• Eric W. Weisstein : Totient Function . In: MathWorld (English).
• Eric W. Weisstein : Noncotient . In: MathWorld (English).
• Arndt Brünner: subsets and prime factor decompositions, Euler's Phi function and faculties. Calculation of Euler's Phi function. Retrieved February 29, 2020 . 
• Aleksander Grytczuk, Barbara Mędryk: On a result of Flammenkamp-Luca concerning Noncototient sequence. Tsukuba .J. Math. 29 (2), 2005, pp. 533-538 , accessed on February 29, 2020 . 

Individual evidence

1. ↑ Wacław Sierpiński : Number Theory, Part II , Warszawa, 1959 (Polish)
2. ^ Paul Erdős : About the numbers of the form and ${\displaystyle \sigma (n)-n}$ ${\displaystyle n-\varphi (n)}$ , Elem. Math. (1973), 83-86
3. ↑ Achim Flammenkamp, ​​Florian Luca: Infinite families of noncototients. Introduction. Colloquium Mathematicum 86 (1), 2000, pp. 37-41 , accessed on February 29, 2020 . 
4. ↑ Jerzy Browkin, Andrzej Schinzel : On integers not of the form n-φ (n). Theorem. Colloquium Mathematicum 68 (1), 1995, pp. 55-58 , accessed on February 29, 2020 . 
5. ↑ Achim Flammenkamp, ​​Florian Luca: Infinite families of noncototients. Theorem. Colloquium Mathematicum 86 (1), 2000, pp. 37-41 , accessed on February 29, 2020 .