Nonkotóciens számok

A matematika, azon belül a számelmélet területén a nonkotóciens számok olyan pozitív egész n számok, melyek nem fejezhetők ki valamely m pozitív egész szám és a nála kisebb relatív prímek számának különbségeként, így értéke megegyezik az n-nél nem nagyobb, n-nel legalább egy közös prímtényezővel bíró számokéval.

Tehát az m − φ(m) = n egyenletnek, ahol φ az Euler-függvény, nincs megoldása m-re. Az n szám kotóciense éppen n − φ(n), tehát egy nonkotóciens olyan szám, ami soha nem fordul elő kotóciensként.

Úgy sejtik, hogy az összes nonkotóciens szám páros. Ez a Goldbach-sejtés egy erősebb formájából következik: ha az n páros szám kifejezhető p és q különböző prímszámok összegeként, akkor

${\displaystyle pq-\varphi (pq)=pq-(p-1)(q-1)=p+q-1=n-1.\,}$

Várhatóan minden 6-nál nagyobb páros szám kifejezhető két különböző prímszám összegeként, amiből az következne, hogy egyetlen 5-nél nagyobb prímszám sem nonkotóciens. A fennmaradó páratlan számokat a következő megfigyelések fedik le: ${\displaystyle 1=2-\phi (2),3=9-\phi (9)}$ és ${\displaystyle 5=25-\phi (25)}$.

Páros számokra megmutatható, hogy:

${\displaystyle 2pq-\varphi (2pq)=2pq-(p-1)(q-1)=pq+p+q-1=(p+1)(q+1)-2}$

Tehát minden olyan n páros szám kotóciens, amire igaz, hogy n+2 felírható (p+1)·(q+1) alakban, ahol p és q prímek.

Az első néhány nonkotóciens szám:

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 ... (A005278 sorozat az OEIS-ben)

Az n számok kotóciens értékei (n = 0-tól kezdve)

0, 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, ... (A051953 sorozat az OEIS-ben)

A legkisebb k egész szám, amire k kotóciense éppen n (kezdve n = 0-val, 0, ha nem létezik ilyen k):

0, 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, ... (A063507 sorozat az OEIS-ben)

A legnagyobb k egész szám, amire k kotóciense éppen n (kezdve n = 0-val, 0, ha nem létezik ilyen k):

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, ... (A063748 sorozat az OEIS-ben)

Az olyan k-k száma, melyre k-φ(k) éppen n (n = 0-tól kezdve):

2, ∞, 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, ... (A063740 sorozat az OEIS-ben)

Erdős (1913-1996) és Sierpinski (1882-1969) fogalmazták meg a kérdést, hogy vajon végtelen sok nonkotóciens szám létezik-e. Ezt végül Browkin és Schinzel (1995) erősítették meg, akik megmutatták, hogy a ${\displaystyle 2^{k}\cdot 509203}$ végtelen számcsalád példa ezekre (lásd Riesel-számok). Azóta több, hasonló formában felírt végtelen számcsaládot találtak, lásd Flammenkamp and Luca (2000).

Jegyzetek

• (1995) „On integers not of the form n-φ(n)”. Colloq. Math. 68, 55–58. o.  
• (2000) „Infinite families of noncototients”. Colloq. Math. 86, 37–41. o.  
• Guy, Richard K.. Unsolved problems in number theory, 3rd, Springer-Verlag, 138–142. o. (2004). ISBN 978-0-387-20860-2 

További információk

• Noncototient definition from MathWorld