7
$\begingroup$

Let $P(x)$ be a polynomials of degree $N$ with real coefficients such that $P(0),P(2),P(3),\cdots,P(N+1)$ are integers. Find all integer $z$ for which there exist a polynomial $P$ that $P(z)$ is not an integer.

Note that we don't refer to $P(1)$.

my question: Is there any rules for $z$?

example : $N=1$

If 2nd degree polynomial $P(x)$ holds that $P(0)$ and $P(2)$ are integers, then we can say that $P(2k)$ is an integer for all integers $k$, but it is not always true that $P(2k+1)$ is an integer.(e.g. $P(x)=x/2$) So the all $z$ that we are searching for are all integers $z$ which hold $z\equiv 1 \pmod 2$ .

my attempt

We have some propositions which might help.

  • If a polynomial of degree $N$ with rational coefficients takes integer values on $0,1,2,\ldots,N$, then it takes integer values on any integer points.

  • Let $k\in\mathbb{Z}$ . If a integer-valued polynomial of degree $N$ is divisible by $k$ on $0,1,2,\ldots,N$, it is divisible by $k$ in any integer point.

  • Let $q$ is a prime number. If a integer-valued polynomial of degree $q-1$ is not divisible by $q$ on all points of $0,1,2,\ldots,q-1$, it is not divisible by $q$ on any integer.

We can generalize them for the points on $k,k+l,k+2l,k+3l\ldots$ (where $k,l\in\mathbb{Z})$.

And I have a conjecture.

If $P(0),P(2),P(3),\cdots,P(N+1)\equiv0\pmod{N+1}$ , then $P$ takes integer values on all integer points.

in other words,

For any denominator of the value of polynomial $P$ on integer point, it is a divisor of $N+1$ .

I think that this is why $P(x)$ have some relations to the factor of $N+1$.

attempt on PC:

I tested some (about hundreds each) cases. I found that $P(x)$ can be classified by when $P(x)$ becomes an integer. (see the bottom of this post)

Then I found some rules.

When $N+1$ is prime:

If $N+1$ is a prime number, then the $z$ which we are looking for satisfy that $z\equiv 1\pmod{N+1}$.

When $N+1$ is composite:

If $N+1$ can be factored into $N+1=p_1^{a_1}\cdot p_2^{a_2}\cdots {p_m}^{a_m}$, then the $z$ are some of the $z$ which satisfy this: $$z\equiv 1,N+2,N+2+p_1,N+2+2p_1,\ldots,N+2+b_1 p_1\pmod{{p_{1}}^{\lceil log_{p_1}{N} \rceil+a_1-1}}\lor\\ z\equiv 1,N+2,N+2+p_2,N+2+2p_2,\ldots,N+2+b_2p_2\pmod{{p_{2}}^{\lceil log_{p_2}{N} \rceil+a_2-1}}\lor\\ \vdots\\ z\equiv 1,N+2,N+2+p_m,N+2+2p_m,\ldots,N+2+b_{m}p_{m}\pmod{{p_{m}}^{\lceil log_{p_m}{N}\rceil+a_m-1}}$$ where $b_k$ is the largest integer such that $n+2+b_k\cdot p_k<{p_{k}}^{\lceil log_{p_k}{N} \rceil+a_k-1}$

When $N+1=2^m$

When $N+1=2^m (m\in\mathbb{N})$, in particular, the $z$ are most of the $z$ which satisfy that $$z\equiv 1,N+2,N+4,N+6,\ldots ,2^{2m-1}-1 \pmod{2^{2m-1}}$$

I couldn't figure out the rules when the number drops.

  • $N=1$: $z\equiv 1\pmod{2}$
  • $N=3$: $z\equiv 1,5,7\pmod{8}$
  • $N=7$: $z\equiv 1,9,11,13,15,17,21,25,27,29,31\pmod{32}$
  • $N=15$: $z\equiv 1,17,19,21,23,25,27,29,31,33,37,41,45,49,51,53,55,57,59,61,63,65,73,81,83,85,87,89,91,93,95,97,101,105,109,113,115,117,119,121,123,125,127\pmod{128}$
  • $N=31$: $z\equiv 1,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,69,73,77,81,85,89,93,97,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127,129,137,145,153,161,163,165,167,169,171,173,175,177,179,181,183,185,187,189,191,193,197,201,205,209,213,217,221,225,227,229,231,233,235,237,239,241,243,245,247,249,251,253,255,257,273,289,291,293,295,297,299,301,303,305,307,309,311,313,315,317,319,321,325,329,333,337,341,345,349,353,355,357,359,361,363,365,367,369,371,373,375,377,379,381,383,385,393,401,409,417,419,421,423,425,427,429,431,433,435,437,439,441,443,445,447,449,453,457,461,465,469,473,477,481,483,485,487,489,491,493,495,497,499,501,503,505,507,509,511\pmod{512}$

I tried to make it prettify, but it didn't help.

  • $N=1$: $z\equiv 1\pmod{2}$
  • $N=3$: $z\equiv 1\pmod{4}\lor z\equiv 7\pmod{8}$
  • $N=7$: $z\equiv 1\pmod{8} \lor z\equiv 13\pmod{16} \lor z\equiv 11,15,21,27,31\pmod{32}$
  • $N=15$: $z\equiv 1\pmod{16}\lor z\equiv 25\pmod{32}\lor z\equiv 21,29,41,53,61\pmod{64}\lor z\equiv 19,23,27,31,37,45,51,55,59,63,73,83,87,91,95,101,109,115,119,123,127\pmod{128}$
  • $N=31$: $z\equiv 1\pmod{32}\lor z\equiv 49\pmod{64}\lor z\equiv 41,57,81,105,121\pmod{128}\lor z\equiv~37,45,53,61,73,89,101,109,117,125,145,165,173,181,189,201,217,229,237,245,253\pmod{256}\lor z\equiv~35,39,43,47,51,55,59,63,69,77,85,93,99,103,107,111,115,119,123,127,137,153,163,167,171,175,179,183,187,191,197,205,213,221,227,231,235,239,243,247,251,255,273,291,295,299,303,307,311,315,319,325,333,341,349,355,359,363,367,371,375,379,383,393,409,419,423,427,431,435,439,443,447,453,461,469,477,483,487,491,495,499,503,507,511\pmod{512}$

Here is the list for $z$.

  • $N=1$ : $z\equiv 1\pmod{2}$
  • $N=2$ : $z\equiv 1\pmod{3}$
  • $N=3$ : $z\equiv 1\pmod{4}\lor z\equiv 7\pmod{8}$
  • $N=4$ : $z\equiv 1 \pmod{5}$
  • $N=5$ : $z\equiv 1,7 \pmod{8} \lor z\equiv 1,7 \pmod{9}$
  • $N=6$ : $z\equiv 1 \pmod{7}$
  • $N=7$ : $z\equiv 1\pmod{8} \lor z\equiv 13\pmod{16} \lor z\equiv 11,15,21,27,31\pmod{32}$
  • $N=8$ : $z\equiv 1\pmod{9} \lor z\equiv 13,16,22,25\pmod{27}$
  • $N=9$ : $z\equiv 1,11,13,15 \pmod{16} \lor z\equiv 1,11,16,21 \pmod{25}$
  • $N=10$ : $z\equiv 1 \pmod{11}$
  • $N=11$ : $z\equiv 1,13\pmod{16}\lor z\equiv 1,13,16,19,22,25\pmod{27} \lor z\equiv 15,21,25,31\pmod{32}$
  • $N=12$ : $z\equiv 1\pmod{13}$
  • $N=13$ : $z\equiv 1,15\pmod{16}\lor z\equiv 1,15,22,29,36,43\pmod{49}$
  • $N=14$ : $z\equiv 1,16,21\pmod{25}\lor z\equiv 1,16,19,25\pmod{27}$
  • $N=15$ : $z\equiv 1\pmod{16}\lor z\equiv 25\pmod{32}\lor z\equiv 21,29,41,53,61\pmod{64}\lor z\equiv 19,23,27,31,37,45,51,55,59,63,73,83,87,91,95,101,109,115,119,123,127\pmod{128}$
N= 1:1(mod2)
N= 2:1(mod3)
N= 3:1(mod4) or 7(mod8)
N= 4:1(mod5)
N= 5:1,7(mod8) or 1,7(mod9)
N= 6:1(mod7)
N= 7:1(mod8) or 13(mod16) or 11,15,21,27,31(mod32)
N= 8:1(mod9) or 13,16,22,25(mod27)
N= 9:1,11,13,15(mod16) or 1,11,16,21(mod25)
N=10:1(mod11)
N=11:1,13(mod16) or 1,13,16,19,22,25(mod27) or 15,21,25,31(mod32)
N=12:1(mod13)
N=13:1,15(mod16) or 1,15,22,29,36,43(mod49)
N=14:1,16,21(mod25) or 1,16,19,25(mod27)
N=15:1(mod16) or 25(mod32) or 21,29,41,53,61(mod64) or 19,23,27,31,37,45,51,55,59,63,73,83,87,91,95,101,109,115,119,123,127(mod128)
N=16:1(mod17)
N=17:1,19(mod27) or 1,19,21,23,25,27,29,31(mod32) or 22,25,37,49,52,64,76,79(mod81)
N=18:1(mod19)
N=19:1,21(mod25) or 1,21,25,29(mod32) or 23,31,37,41,45,49,55,63(mod64)
N=20:1,22,25(mod27) or 1,22,29,36,43(mod49)
N=21:1,23,25,31(mod32) or 1,23,34,45,56,67,78,89,100,111(mod121)
N=22:1(mod23)
N=23:1,25(mod27) or 1,25(mod32) or 29,41,49,61(mod64) or 27,31,45,59,63,73,81,91,95,109,123,127(mod128)
N=24:1(mod25) or 31,36,41,46,56,61,66,71,81,86,91,96,106,111,116,121(mod125)
N=25:1,27,29,31(mod32) or 1,27,40,53,66,79,92,105,118,131,144,157(mod169)
N=26:1(mod27) or 37,46,64,73(mod81) or 31,34,40,43,49,52,58,61,67,70,76,79,91,100,112,115,121,124,130,133,139,142,148,151,157,160,172,181,193,196,202,205,211,214,220,223,229,232,238,241(mod243)
N=27:1,29(mod32) or 31,45,49,63(mod64) or 1,29,36,43(mod49)
N=28:1(mod29)
N=29:1,31(mod32) or 1,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73,76,79(mod81) or 1,31,36,41,46,51,56,61,66,71,76,81,86,91,96,101,106,111,116,121(mod125)
N=30:1(mod31)
N=31:1,33,49(mod64) or 41,57,81,105,121(mod128) or 37,45,53,61,73,89,101,109,117,125,145,165,173,181,189,201,217,229,237,245,253(mod256) or 35,39,43,47,51,55,59,63,69,77,85,93,99,103,107,111,115,119,123,127,137,153,163,167,171,175,179,183,187,191,197,205,213,221,227,231,235,239,243,247,251,255,273,291,295,299,303,307,311,315,319,325,333,341,349,355,359,363,367,371,375,379,383,393,409,419,423,427,431,435,439,443,447,453,461,469,477,483,487,491,495,499,503,507,511(mod512)
N=32:1,34,37,43,46,52,55,61,64,70,73,79(mod81) or 1,34,45,56,67,78,89,100,111(mod121)
N=33:1,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63(mod64) or 1,35,52,69,86,103,120,137,154,171,188,205,222,239,256,273(mod289)
N=34:1,36,43(mod49)or 1,36,41,46,51,61,66,71,76,86,91,96,101,111,116,121(mod125)
N=35:1,37,41,45,49,53,57,61(mod64) or 39,47,55,63,69,73,77,81,85,89,93,97,103,111,119,127(mod128) or 1,37,46,55,64,73(mod81) or 40,43,49,52,67,70,76,79,91,100,109,121,124,130,133,148,151,157,160,172,181,190,202,205,211,214,229,232,238,241(mod243)
N=36:1(mod37)
N=37:1,39,41,47,49,55,57,63(mod64) or 1,39,58,77,96,115,134,153,172,191,210,229,248,267,286,305,324,343(mod361)
N=38:1,40,43,46,49,52,55,67,70,73,76,79(mod81) or 1,40,53,66,79,92,105,118,131,144,157(mod169)
N=39:1,41,49,57(mod64) or 45,61,73,81,89,97,109,125(mod128) or 43,47,53,59,63,77,93,107,111,117,123,127,137,145,153,161,171,175,181,187,191,205,221,235,239,245,251,255(mod256) or 1,41,46,51,66,71,76,91,96,101,116,121(mod125)
N=40:1(mod41)
N=41:1,43(mod49) or 1,43,45,47,49,59,61,63(mod64) or 1,43,46,52,55,70,73,79(mod81)
N=42:1(mod43)
N=43:1,45,49,61(mod64) or 47,53,57,63,77,81,93,97,111,117,121,127(mod128) or 1,45,56,67,78,89,100,111(mod121)
N=44:1,46,55,73(mod81) or 49,52,64,76,79,100,109,130,133,145,157,160,181,190,211,214,226,238,241(mod243) or 1,46,51,71,76,96,101,121(mod125)
N=45:1,47,49,63(mod64) or 1,47,70,93,116,139,162,185,208,231,254,277,300,323,346,369,392,415,438,461,484,507(mod529)
N=46:1(mod47)
N=47:1,49(mod64) or 1,49,52,55,76,79(mod81) or 57,81,97,121(mod128) or 53,61,89,117,125,145,161,181,189,217,245,253(mod256) or 51,55,59,63,73,85,93,105,115,119,123,127,153,179,183,187,191,201,213,221,233,243,247,251,255,273,289,307,311,315,319,329,341,349,361,371,375,379,383,409,435,439,443,447,457,469,477,489,499,503,507,511(mod512)
N=48:1(mod49) or 57,64,71,78,85,92,106,113,120,127,134,141,155,162,169,176,183,190,204,211,218,225,232,239,253,260,267,274,281,288,302,309,316,323,330,337(mod343)
N=49:1,51,53,55,57,59,61,63(mod64) or 1,51,76,101(mod125) or 56,61,66,71,81,86,91,96,106,111,116,121,151,181,186,191,196,206,211,216,221,231,236,241,246,276,306,311,316,321,331,336,341,346,356,361,366,371,401,431,436,441,446,456,461,466,471,481,486,491,496,526,556,561,566,571,581,586,591,596,606,611,616,621(mod625)
N=50:1,52,55,79(mod81) or 1,52,69,86,103,120,137,154,171,188,205,222,239,256,273(mod289)
N=51:1,53,57,61(mod64) or 55,63,85,89,93,97,119,127(mod128) or 1,53,66,79,92,105,118,131,144,157(mod169)
N=52:1(mod53)
N=53:1,55,57,63(mod64) or 1,55(mod81) or 64,73,109,145,154,190,226,235(mod243) or 58,61,67,70,76,79,91,100,118,127,139,142,148,151,157,160,172,181,199,208,220,223,229,232,238,241,271,301,304,310,313,319,322,334,343,361,370,382,385,391,394,400,403,415,424,442,451,463,466,472,475,481,484,514,544,547,553,556,562,565,577,586,604,613,625,628,634,637,643,646,658,667,685,694,706,709,715,718,724,727(mod729)
N=54:1,56,67,78,89,100,111(mod121) or 1,56,61,66,71,76,81,86,91,96,101,106,111,116,121(mod125)
N=55:1,57(mod64) or 61,89,97,125(mod128) or 59,63,73,81,93,105,113,123,127,153,161,187,191,201,209,221,233,241,251,255(mod256) or 1,57,64,71,78,85,92,99,106,113,120,127,134,141,148,155,162,169,176,183,190,197,204,211,218,225,232,239,246,253,260,267,274,281,288,295,302,309,316,323,330,337(mod343)
N=56:1,58,61,64,67,70,73,76,79(mod81) or 1,58,77,96,115,134,153,172,191,210,229,248,267,286,305,324,343(mod361)
N=57:1,59,61,63(mod64) or 1,59,88,117,146,175,204,233,262,291,320,349,378,407,436,465,494,523,552,581,610,639,668,697,726,755,784,813(mod841)
N=58:1(mod59)
N=59:1,61(mod64) or 1,61,64,70,73,79(mod81) or 1,61,66,71,76,86,91,96,101,111,116,121(mod125) or 63,93,97,127(mod128)
N=60:1(mod61)
N=61:1,63(mod64) or 1,63,94,125,156,187,218,249,280,311,342,373,404,435,466,497,528,559,590,621,652,683,714,745,776,807,838,869,900,931(mod961)
N=62:1,64,73(mod81) or 67,70,76,79,91,100,109,118,127,136,148,151,157,160,172,181,190,199,208,217,229,232,238,241(mod243) or 1,64,71,78,85,92,99,113,120,127,134,141,148,162,169,176,183,190,197,211,218,225,232,239,246,260,267,274,281,288,295,309,316,323,330,337(mod343)
N=63:1(mod64) or 97(mod128) or 81,113,161,209,241(mod256) or 73,89,105,121,145,177,201,217,233,249,289,329,345,361,377,401,433,457,473,489,505(mod512) or 69,77,85,93,101,109,117,125,137,153,169,185,197,205,213,221,229,237,245,253,273,305,325,333,341,349,357,365,373,381,393,409,425,441,453,461,469,477,485,493,501,509,545,581,589,597,605,613,621,629,637,649,665,681,697,709,717,725,733,741,749,757,765,785,817,837,845,853,861,869,877,885,893,905,921,937,953,965,973,981,989,997,1005,1013,1021(mod1024) or 67,71,75,79,83,87,91,95,99,103,107,111,115,119,123,127,133,141,149,157,165,173,181,189,195,199,203,207,211,215,219,223,227,231,235,239,243,247,251,255,265,281,297,313,323,327,331,335,339,343,347,351,355,359,363,367,371,375,379,383,389,397,405,413,421,429,437,445,451,455,459,463,467,471,475,479,483,487,491,495,499,503,507,511,529,561,579,583,587,591,595,599,603,607,611,615,619,623,627,631,635,639,645,653,661,669,677,685,693,701,707,711,715,719,723,727,731,735,739,743,747,751,755,759,763,767,777,793,809,825,835,839,843,847,851,855,859,863,867,871,875,879,883,887,891,895,901,909,917,925,933,941,949,957,963,967,971,975,979,983,987,991,995,999,1003,1007,1011,1015,1019,1023,1057,1091,1095,1099,1103,1107,1111,1115,1119,1123,1127,1131,1135,1139,1143,1147,1151,1157,1165,1173,1181,1189,1197,1205,1213,1219,1223,1227,1231,1235,1239,1243,1247,1251,1255,1259,1263,1267,1271,1275,1279,1289,1305,1321,1337,1347,1351,1355,1359,1363,1367,1371,1375,1379,1383,1387,1391,1395,1399,1403,1407,1413,1421,1429,1437,1445,1453,1461,1469,1475,1479,1483,1487,1491,1495,1499,1503,1507,1511,1515,1519,1523,1527,1531,1535,1553,1585,1603,1607,1611,1615,1619,1623,1627,1631,1635,1639,1643,1647,1651,1655,1659,1663,1669,1677,1685,1693,1701,1709,1717,1725,1731,1735,1739,1743,1747,1751,1755,1759,1763,1767,1771,1775,1779,1783,1787,1791,1801,1817,1833,1849,1859,1863,1867,1871,1875,1879,1883,1887,1891,1895,1899,1903,1907,1911,1915,1919,1925,1933,1941,1949,1957,1965,1973,1981,1987,1991,1995,1999,2003,2007,2011,2015,2019,2023,2027,2031,2035,2039,2043,2047(mod2048)
N=64:1,66,71,76,91,96,101,116,121(mod125) or 1,66,79,92,105,118,131,144,157(mod169)
N=65:1,67,70,73,76,79(mod81) or 1,67,78,89,100,111(mod121) or 1,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127(mod128)
N=66:1(mod67)
N=67:1,69,73,77,81,85,89,93,97,101,105,109,113,117,121,125(mod128) or 71,79,87,95,103,111,119,127,133,137,141,145,149,153,157,161,165,169,173,177,181,185,189,193,199,207,215,223,231,239,247,255(mod256) or 1,69,86,103,120,137,154,171,188,205,222,239,256,273(mod289)
N=68:1,70,73,79(mod81) or 1,70,93,116,139,162,185,208,231,254,277,300,323,346,369,392,415,438,461,484,507(mod529)
N=69:1,71,76,96,101,121(mod125) or 1,71,73,79,81,87,89,95,97,103,105,111,113,119,121,127(mod128) or 1,71,78,85,92,99,246,267,274,281,288,295,316,323,330,337(mod343)
N=70:1(mod71)
N=71:1,73,81,89,97,105,113,121(mod128) or 1,73,76,79,82,100,109,127,136,154,157,160,163,181,190,208,217,235,238,241(mod243) or 77,93,109,125,137,145,153,161,169,177,185,193,205,221,237,253(mod256) or 75,79,85,91,95,107,111,117,123,127,141,157,173,189,203,207,213,219,223,235,239,245,251,255,265,273,281,289,297,305,313,321,331,335,341,347,351,363,367,373,379,383,397,413,429,445,459,463,469,475,479,491,495,501,507,511(mod512)
N=72:1(mod73)
N=73:1,75,77,79,81,91,93,95,97,107,109,111,113,123,125,127(mod128) or 1,75,112,149,186,223,260,297,334,371,408,445,482,519,556,593,630,667,704,741,778,815,852,889,926,963,1000,1037,1074,1111,1148,1185,1222,1259,1296,1333(mod1369)
N=74:1,76,79(mod81) or 1,76,101(mod125) or 81,86,91,96,106,111,116,121,151,176,206,211,216,221,231,236,241,246,276,301,331,336,341,346,356,361,366,371,401,426,456,461,466,471,481,486,491,496,526,551,581,586,591,596,606,611,616,621(mod625)
N=75:1,77,81,93,97,109,113,125(mod128) or 79,85,89,95,111,117,121,127,141,145,157,161,173,177,189,193,207,213,217,223,239,245,249,255(mod256) or 1,77,96,115,134,153,172,191,210,229,248,267,286,305,324,343(mod361)
N=76:1,78,89,100,111(mod121) or 1,78,85,92,99,127,134,141,148,176,183,190,197,225,232,239,246,274,281,288,295,323,330,337(mod343)
N=77:1,79(mod81) or 1,79,81,95,97,111,113,127(mod128) or 1,79,92,105,118,131,144,157(mod169)
N=78:1(mod79)
N=79:1,81,86,91,96,101,106,111,116,121(mod125) or 1,81,97,113(mod128) or 89,121,145,161,177,193,217,249(mod256) or 85,93,105,117,125,153,185,213,221,233,245,253,273,289,305,321,341,349,361,373,381,409,441,469,477,489,501,509(mod512) or 83,87,91,95,101,109,115,119,123,127,149,157,169,181,189,211,215,219,223,229,237,243,247,251,255,281,313,339,343,347,351,357,365,371,375,379,383,405,413,425,437,445,467,471,475,479,485,493,499,503,507,511,529,545,561,577,595,599,603,607,613,621,627,631,635,639,661,669,681,693,701,723,727,731,735,741,749,755,759,763,767,793,825,851,855,859,863,869,877,883,887,891,895,917,925,937,949,957,979,983,987,991,997,1005,1011,1015,1019,1023(mod1024)
N=80:1(mod81) or 109,136,190,217(mod243) or 91,100,118,127,145,154,172,181,199,208,226,235,271,298,334,343,361,370,388,397,415,424,442,451,469,478,514,541,577,586,604,613,631,640,658,667,685,694,712,721(mod729) or 85,88,94,97,103,106,112,115,121,124,130,133,139,142,148,151,157,160,166,169,175,178,184,187,193,196,202,205,211,214,220,223,229,232,238,241,253,262,280,289,307,316,328,331,337,340,346,349,355,358,364,367,373,376,382,385,391,394,400,403,409,412,418,421,427,430,436,439,445,448,454,457,463,466,472,475,481,484,496,505,523,532,550,559,571,574,580,583,589,592,598,601,607,610,616,619,625,628,634,637,643,646,652,655,661,664,670,673,679,682,688,691,697,700,706,709,715,718,724,727,757,784,814,817,823,826,832,835,841,844,850,853,859,862,868,871,877,880,886,889,895,898,904,907,913,916,922,925,931,934,940,943,949,952,958,961,967,970,982,991,1009,1018,1036,1045,1057,1060,1066,1069,1075,1078,1084,1087,1093,1096,1102,1105,1111,1114,1120,1123,1129,1132,1138,1141,1147,1150,1156,1159,1165,1168,1174,1177,1183,1186,1192,1195,1201,1204,1210,1213,1225,1234,1252,1261,1279,1288,1300,1303,1309,1312,1318,1321,1327,1330,1336,1339,1345,1348,1354,1357,1363,1366,1372,1375,1381,1384,1390,1393,1399,1402,1408,1411,1417,1420,1426,1429,1435,1438,1444,1447,1453,1456,1486,1513,1543,1546,1552,1555,1561,1564,1570,1573,1579,1582,1588,1591,1597,1600,1606,1609,1615,1618,1624,1627,1633,1636,1642,1645,1651,1654,1660,1663,1669,1672,1678,1681,1687,1690,1696,1699,1711,1720,1738,1747,1765,1774,1786,1789,1795,1798,1804,1807,1813,1816,1822,1825,1831,1834,1840,1843,1849,1852,1858,1861,1867,1870,1876,1879,1885,1888,1894,1897,1903,1906,1912,1915,1921,1924,1930,1933,1939,1942,1954,1963,1981,1990,2008,2017,2029,2032,2038,2041,2047,2050,2056,2059,2065,2068,2074,2077,2083,2086,2092,2095,2101,2104,2110,2113,2119,2122,2128,2131,2137,2140,2146,2149,2155,2158,2164,2167,2173,2176,2182,2185(mod2187)
N=81:1,83,85,87,89,91,93,95,97,115,117,119,121,123,125,127(mod128) or 1,83,124,165,206,247,288,329,370,411,452,493,534,575,616,657,698,739,780,821,862,903,944,985,1026,1067,1108,1149,1190,1231,1272,1313,1354,1395,1436,1477,1518,1559,1600,1641(mod1681)
N=82:1(mod83)
N=83:1,85,89,93,97,117,121,125(mod128) or 1,85,88,91,94,97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,145,148,151,154,157,160,163,166,169,172,175,178,181,184,187,190,193,196,199,202,205,208,211,214,217,220,223,226,229,232,235,238,241(mod243) or 87,95,101,105,109,113,119,127,149,153,157,161,181,185,189,193,215,223(mod256) or 
1,85,92,99,134,141,148,183,190,197,232,239,246,281,288,295,330,337(mod343)
N=84:1,86,91,96,101,111,116,121(mod125) or 1,86,103,120,137,154,171,188,205,222,239,256,273(mod289)
N=85:1,87,89,95,97,119,121,127(mod128) or 1,87,130,173,216,259,302,345,388,431,474,517,560,603,646,689,732,775,818,861,904,947,990,1033,1076,1119,1162,1205,1248,1291,1334,1377,1420,1463,1506,1549,1592,1635,1678,1721,1764,1807(mod1849)
N=86:1,88,91,97,100,106,109,115,118,124,127,133,136,142,145,151,154,160,163,169,172,178,181,187,190,196,199,205,208,214,217,223,226,232,235,241(mod243) or 1,88,117,146,175,204,233,262,291,320,349,378,407,436,465,494,523,552,581,610,639,668,697,726,755,784,813(mod841)
N=87:1,89,100,111(mod121) or 1,89,97,121(mod128) or 93,105,113,125,153,161,185,193,221,233,241,253(mod256) or 91,95,109,123,127,157,169,177,189,219,223,237,251,255,281,289,313,321,347,351,365,379,383,413,425,433,445,475,479,493,507,511(mod512)
N=88:1(mod89)
N=89:1,91,96,101,116,121(mod125) or 1,91,93,95,97,123,125,127(mod128) or 1,91,100,109,118,127,136,145,154,163,172,181,190,199,208,217,226,235(mod243) or 130,133,148,151,157,160,175,178,184,187,202,205,211,214,229,232,238,241,253,262,271,280,289,298,307,316,325,337,340,346,349,364,367,373,376,391,394,400,403,418,421,427,430,445,448,454,457,472,475,481,484,496,505,514,523,532,541,550,559,568,580,583,589,592,607,610,616,619,634,637,643,646,661,664,670,673,688,691,697,700,715,718,724,727(mod729)
N=90:1,92,105,118,131,144,157(mod169) or 1,92,99,141,148,190,197,239,246,288,295,337(mod343)
N=91:1,93,97,125(mod128) or 95,109,113,127,157,161,189,193,223,237,241,255(mod256) or 1,93,116,139,162,185,208,231,254,277,300,323,346,369,392,415,438,461,484,507(mod529)
N=92:1,94,97,100,103,106,109,121,124,127,130,133,136,148,151,154,157,160,163,175,178,181,184,187,190,202,205,208,211,214,217,229,232,235,238,241(mod243) or 1,94,125,156,187,218,249,280,311,342,373,404,435,466,497,528,559,590,621,652,683,714,745,776,807,838,869,900,931(mod961)
N=93:1,95,97,127(mod128) or 1,95,142,189,236,283,330,377,424,471,518,565,612,659,706,753,800,847,894,941,988,1035,1082,1129,1176,1223,1270,1317,1364,1411,1458,1505,1552,1599,1646,1693,1740,1787,1834,1881,1928,1975,2022,2069,2116,2163(mod2209)
N=94:1,96,101,121(mod125) or 1,96,115,134,153,172,191,210,229,248,267,286,305,324,343(mod361)
N=95:1,97,100,106,109,124,127,133,136,151,154,160,163,178,181,187,190,205,208,214,217,232,235,241(mod243) or 1,97(mod128) or 113,161,193,241(mod256) or 105,121,177,233,249,289,321,361,377,433,489,505(mod512) or 101,109,117,125,145,169,185,209,229,237,245,253,305,357,365,373,381,401,425,441,465,485,493,501,509,545,577,613,621,629,637,657,681,697,721,741,749,757,765,817,869,877,885,893,913,937,953,977,997,1005,1013,1021(mod1024) or 99,103,107,111,115,119,123,127,137,153,165,173,181,189,201,217,227,231,235,239,243,247,251,255,273,297,313,337,355,359,363,367,371,375,379,383,393,409,421,429,437,445,457,473,483,487,491,495,499,503,507,511,561,611,615,619,623,627,631,635,639,649,665,677,685,693,701,713,729,739,743,747,751,755,759,763,767,785,809,825,849,867,871,875,879,883,887,891,895,905,921,933,941,949,957,969,985,995,999,1003,1007,1011,1015,1019,1023,1057,1089,1123,1127,1131,1135,1139,1143,1147,1151,1161,1177,1189,1197,1205,1213,1225,1241,1251,1255,1259,1263,1267,1271,1275,1279,1297,1321,1337,1361,1379,1383,1387,1391,1395,1399,1403,1407,1417,1433,1445,1453,1461,1469,1481,1497,1507,1511,1515,1519,1523,1527,1531,1535,1585,1635,1639,1643,1647,1651,1655,1659,1663,1673,1689,1701,1709,1717,1725,1737,1753,1763,1767,1771,1775,1779,1783,1787,1791,1809,1833,1849,1873,1891,1895,1899,1903,1907,1911,1915,1919,1929,1945,1957,1965,1973,1981,1993,2009,2019,2023,2027,2031,2035,2039,2043,2047(mod2048)
N=96:1(mod97)
N=97:1,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127(mod128) or 1,99,148,197,246,295(mod343) or 106,113,120,127,134,141,155,162,169,176,183,190,204,211,218,225,232,239,253,260,267,274,281,288,302,309,316,323,330,337,393,449,456,463,470,477,484,498,505,512,519,526,533,547,554,561,568,575,582,596,603,610,617,624,631,645,652,659,666,673,680,736,792,799,806,813,820,827,841,848,855,862,869,876,890,897,904,911,918,925,939,946,953,960,967,974,988,995,1002,1009,1016,1023,1079,1135,1142,1149,1156,1163,1170,1184,1191,1198,1205,1212,1219,1233,1240,1247,1254,1261,1268,1282,1289,1296,1303,1310,1317,1331,1338,1345,1352,1359,1366,1422,1478,1485,1492,1499,1506,1513,1527,1534,1541,1548,1555,1562,1576,1583,1590,1597,1604,1611,1625,1632,1639,1646,1653,1660,1674,1681,1688,1695,1702,1709,1765,1821,1828,1835,1842,1849,1856,1870,1877,1884,1891,1898,1905,1919,1926,1933,1940,1947,1954,1968,1975,1982,1989,1996,2003,2017,2024,2031,2038,2045,2052,2108,2164,2171,2178,2185,2192,2199,2213,2220,2227,2234,2241,2248,2262,2269,2276,2283,2290,2297,2311,2318,2325,2332,2339,2346,2360,2367,2374,2381,2388,2395(mod2401)
N=98:1,100,111(mod121) or 1,100,109,127,136,154,163,181,190,208,217,235(mod243) or 103,106,118,130,133,145,157,160,184,187,199,211,214,226,238,241,262,271,289,298,316,325,346,349,361,373,376,388,400,403,427,430,442,454,457,469,481,484,505,514,532,541,559,568,589,592,604,616,619,631,643,646,670,673,685,697,700,712,724,727(mod729)
N=99:1,101(mo125) or 1,101,105,109,113,117,121,125(mod128) or 103,111,119,127,165,169,173,177,181,185,189,193,231,239,247,255(mod256) or 106,111,116,121,151,176,201,231,236,241,246,276,301,326,356,361,366,371,401,426,451,481,486,491,496,526,551,576,606,611,616,621(mod625)
N=100:1(mod101)

$P(z)$ is not integer when...

  • $N=2$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{3}$
  • $N=3$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{4}$
    • $z\equiv 1\pmod{4}\lor z\equiv 7\pmod{8}$
  • $N=4$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{5}$
  • $N=5$:
    • $z\in\emptyset$
    • $z\equiv 1,7\pmod{8}$
    • $z\equiv 1,7\pmod{9}$
    • $z\equiv 1,7 \pmod{8} \lor z\equiv 1,7 \pmod{9}$
  • $N=6$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{7}$
  • $N=7$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{8}$
    • $z\equiv 1\pmod{8} \lor z\equiv 13\pmod{16}$
    • $z\equiv 1\pmod{8} \lor z\equiv 13\pmod{16} \lor z\equiv 11,15,21,27,31\pmod{32}$
  • $N=8$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{9}$
    • $z\equiv 1\pmod{9} \lor z\equiv 13,16,22,25\pmod{27}$
  • $N=9$:
    • $z\in\emptyset$
    • $z\equiv 1,11,13,15\pmod{16}$
    • $z\equiv 1,11,16,21\pmod{25}$
    • $z\equiv 1,11,13,15 \pmod{16} \lor z\equiv 1,11,16,21 \pmod{25}$
  • $N=10$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{11}$
  • $N=11$:
    • $z\in\emptyset$
    • $z\equiv 1,13\pmod{16}$
    • $z\equiv 1,13,16,19,22,25\pmod{27}$
    • $z\equiv 1,13\pmod{16}\lor z\equiv 15,21,25,31\pmod{32}$
    • $z\equiv 1,13 \pmod{16} \lor z\equiv 1,13,16,19,22,25\pmod{27}$
    • $z\equiv 1,13\pmod{16}\lor z\equiv 1,13,16,19,22,25\pmod{27} \lor z\equiv 15,21,25,31\pmod{32}$
  • $N=12$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{13}$
  • $N=13$:
    • $z\in\emptyset$
    • $z\equiv 1,15\pmod{16}$
    • $z\equiv 1,15,22,29,36,43\pmod{49}$
    • $z\equiv 1,15\pmod{16}\lor z\equiv 1,15,22,29,36,43\pmod{49}$
  • $N=14$:
    • $z\in\emptyset$
    • $z\equiv 1,16,21\pmod{25}$
    • $z\equiv 1,16,19,25\pmod{27}$
    • $z\equiv 1,16,21\pmod{25}\lor z\equiv 1,16,19,25\pmod{27}$
  • $N=15$:
    • $z\in\emptyset$
    • $z\equiv 1\pmod{16}$
    • $z\equiv 1\pmod{16}\lor z\equiv 25\pmod{32}$
    • $z\equiv 1\pmod{16}\lor z\equiv 25\pmod{32}\lor z\equiv 21,29,41,53,61\pmod{64}$
    • $z\equiv 1\pmod{16}\lor z\equiv 25\pmod{32}\lor z\equiv 21,29,41,53,61\pmod{64}\lor z\equiv 19,23,27,31,37,45,51,55,59,63,73,83,87,91,95,101,109,115,119,123,127\pmod{128}$
$\endgroup$
3
  • 3
    $\begingroup$ The $x$ for which the condition should be found are integers? If so, write $p(x)$ in the basis $q_k(x)=\binom{x}{k}$, instead of in the basis $x^k$. $\endgroup$ – conditionalMethod Nov 30 '19 at 13:19
  • $\begingroup$ @dodicta It probably has something to do with the fact whether $n + 1$ is prime or composite. Check to see if the factors of $n + 1$ have anything to do with the modular structures. $\endgroup$ – Madeleine Birchfield Dec 23 '19 at 21:20
  • $\begingroup$ The bounty on this question is related to the Pearl Dive project. Read more about the Pearl dive in meta $\endgroup$ – Jyrki Lahtonen Apr 14 '20 at 11:33
2
+200
$\begingroup$

Note that there exists a unique integer-valued polynomial $Q(x)\in\mathbb{Q}[x]$ of degree at most $N-1$ such that $$Q(k)=P(k)\text{ for }k=2,3,\ldots,N+1\,.$$ This polynomial is given by $$Q(x):=\sum_{k=0}^{N-1}\,\Biggl(\sum_{r=0}^k\,(-1)^r\,\binom{k}{r}\,P(k+2-r)\Biggr)\,\binom{x-2}{k}\,.$$ Note that $$\begin{align}Q(0)&=\sum_{k=0}^{N-1}\,(-1)^k\,(k+1)\,\Biggl(\sum_{r=0}^k\,(-1)^r\,\binom{k}{r}\,P(k+2-r)\Biggr)\\&=\sum_{s=0}^{N-1}\,\sum_{r=0}^{N-1-s}\,(-1)^{s}\,(s+r+1)\,\binom{s+r}{s}\,P(s+2) \\ &=\sum_{s=0}^{N-1}\,(-1)^s\,(s+1)\,P(s+2)\,\left(\sum_{r=0}^{N-1-s}\,\binom{r+s+1}{s+1}\right) \\&=\sum_{s=0}^{N-1}\,(-1)^s\,(s+1)\,\binom{N+1}{s+2}\,P(s+2)\,.\end{align}$$ Hence, if we define $\tilde{P}(x)$ to be $P(x)-Q(x)$, then $$\tilde{P}(2)=\tilde{P}(3)=\ldots=\tilde{P}(N+1)=0\,.$$ Consequently, there exist a rational number $a$ such that $$\tilde{P}(x)=a\,R(x)\,,$$ where $$R(x):=\frac{(x-2)\,(x-3)\,\cdots\,(x-N-1)}{N!}=\binom{x-2}{N}$$ is an integer-valued polynomial. Then, we only need $$(N+1)\,a=(-1)^N\,\tilde{P}(0)\in\mathbb{Z}\,.$$ That is, $$\tilde{P}(x)=\frac{(-1)^N\,\tilde{P}(0)}{N+1}\,R(x)\,.$$ Thus, from $P(x)=\tilde{P}(x)+Q(x)$, we obtain $$P(x)=\frac{(-1)^N\,A^P_N}{N+1}\,\binom{x-2}{N}+\sum_{k=0}^{N-1}\,\Biggl(\sum_{r=0}^k\,(-1)^r\,\binom{k}{r}\,P(k+2-r)\Biggr)\,\binom{x-2}{k}\,,$$ where $$\begin{align}A^P_N&:=\tilde{P}(0)=P(0)-Q(0) \\&=P(0)-\sum_{s=0}^{N-1}\,(-1)^s\,(s+1)\,\binom{N+1}{s+2}\,P(s+2) \\&=-\sum_{s=0}^{N+1}\,(-1)^s\,(s-1)\,\binom{N+1}{s}\,P(s)\,.\end{align}$$

Let $U^P_N$ be the subset of $\mathbb{Z}$ containing all $z\in\mathbb{Z}$ such that $$\frac{N+1}{\gcd\big(A^P_N,N+1\big)}\,\Bigg\vert\, \binom{z-2}{N}\,.$$ Thus, for an integer $z$, $P(z)\notin\mathbb{Z}$ if and only if $$\frac{N+1}{\gcd\big(A^P_N,N+1\big)} \,{\not\Bigg\vert}\, R(z)=\binom{z-2}{N}\,,$$ or equivalently, $z\in V^P_N:=\mathbb{Z}\setminus U^P_N$. The answer of course depends on $P$ and $N$.

If $\sigma_0(m)$ denote the number of positive integer dividing a given positive integer $m$, then for a given positive integer $N$, there are exactly $\sigma_0(N+1)$ pairwise distinct sets $U^P_N$ (as they only depend on $\gcd\big(A^P_N,N+1\big)$). This agrees with the list you have found.

In other words, if we denote by $\bar{U}^{D}_N$, where $D$ is a positive integer such that $D\mid N+1$, the set $U^{P}_N$ with $A^P_N=D$, then for any polynomial $P(x)\in\mathbb{Z}[x]$ satisfying $P(0),P(2),P(3),\ldots,P(N+1)\in\mathbb{Z}$, $$U_N^P=\bar{U}_N^D$$ if and only if $\gcd\big(A^P_N,N+1\big)=D$. Likewise, we set $\bar{V}_N^D:=\mathbb{Z}\setminus\bar{U}_N^D$. It remains to determine all possible sets $\bar{U}^D_N$, for a given $N$. Note that we have $\bar{U}_N^{N+1}=\mathbb{Z}$, so $\bar{V}_N^{N+1}=\emptyset$.

I think this is probably not doable manually for large $N$, but it narrows down the search a lot. For a simple case such as when $N+1$ is a prime number, then there are only two sets $\bar{U}_N^D$, which are $$\bar{U}_N^{1}=\big\{z\in\mathbb{Z}\,\big|\,z\not\equiv1\pmod{N+1}\big\}$$ and $\bar{U}_N^{N+1}=\mathbb{Z}$. This leads to $$\bar{V}_N^1=\big\{z\in\mathbb{Z}\,\big|\,z\equiv1\pmod{N+1}\big\}$$ and $\bar{V}_N^{N+1}=\emptyset$.

The sets $\bar{U}_N^D$ and $\bar{V}_N^D$ live in $\mathbb{Z}/m\mathbb{Z}$, where $m$ is a positive integer not greater than $\dfrac{(N+1)!}{D}$. Suppose that $$\frac{N+1}{D}=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$$ and $$N!=p_1^{\beta_1}p_2^{\beta_2}\cdots p_r^{\beta_r}\,,$$ where $p_1,p_2,\ldots,p_r$ are pairwise distinct prime natural numbers, and $\alpha_j,\beta_j\in\mathbb{Z}_{\geq 0}$ for $j=1,2,\ldots,r$. Then, $m$ can be taken to be $$M_N^D:=\prod_{\substack{j\in\{1,2,\ldots,r\}\\ \alpha_j>0}}\,p_j^{\alpha_j+\beta_j}\,.$$ The smallest possible $m$ can be significantly lower than $M_N^D$ (but it must divide $M_N^D$).

$\endgroup$
0
1
$\begingroup$

Partial answer: such $P$ exists iff $N+1$ does not divide the binomial coefficient $\binom{z-2}{N}$, in which case one may take the polynomial $$P(x) = \frac1{N+1} \binom{x-2}N \,.$$

So for example if $N+1$ is prime, this is the case iff $z \equiv 1 \pmod{N+1}$.


We may write a degree $N$ polynomial $P$ as a linear combination of the polynomials $$\binom {x-2} k$$ for $k \in \{0, \ldots, N\}$. Write $P(x) = \sum_{k=0}^N a_k \binom{x-2} k$. Then $P(2), \ldots, P(N+1)$ are integers iff $a_0, \ldots, a_{N-1}$ are integers. If those are integers, then $P(0)$ is an integer iff $$a_N \binom{-2}N = a_N (-1)^N (N+1)$$ is an integer; i.e. iff $(N+1) \cdot a_N$ is an integer.


Now take $z \in \mathbb Z$. Then a degree $N$ polynomial $P$ with $P(z) \notin \mathbb Z$ and $P(0), P(2), P(3), \ldots, P(N+1) \in \mathbb Z$ must be of the form $P(x) = \sum_{k=0}^N a_k \binom{x-2} k$ with $a_k$ as above and $$a_N \binom{z-2}N \notin \mathbb Z \,.$$ Equivalently, writing $a_N = b/(N+1)$, for such $P$ to exist there has to exist $b \in \mathbb Z$ with $$\frac b{N+1}\binom{z-2}N \notin \mathbb Z \,.$$ Equivalently, $$N+1 \nmid \binom{z-2}N\,.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.