Find all integer z for which there exist a Nth degree polynomial P that $P(z)$ is not an integer, and $P(0),P(2),P(3),\cdots,P(N+1)$ are integers.

Question

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}$

Answer 1

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$).

Answer 2

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\,.$$