#12 Polynomials, Sequences and Number Theory

For \(k\ge1\), \(a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})\). A constant term gives zero difference. A sum of such expressions with integer coefficients is also divisible by \(a-b\). Hence the statement holds for every \(f\in\mathbb Z[x]\).

The first statement follows from the difference of powers formula. For the second, \(a^{2n+1}+b^{2n+1}=a^{2n+1}-(-b)^{2n+1}\), which is divisible by \(a-(-b)=a+b\).

Since \(n+m\equiv n\pmod m\), for every monomial \((n+m)^k\equiv n^k\pmod m\). Hence \(f(n+m)\equiv f(n)\pmod m\). Thus the residues repeat with period \(m\), possibly not the minimal period.

Solve \(n^2+n+1\equiv0\pmod7\). Checking residues gives: for \(n\equiv2\), \(4+2+1=7\), and for \(n\equiv4\), \(16+4+1=21\). No other residues work. The answer is \(n\equiv2\) or \(4\pmod7\).

Compute: \(u_{n+1}=3(n+1)^2+2(n+1)+1=3n^2+8n+6\), and \(u_{n-1}=3(n-1)^2+2(n-1)+1=3n^2-4n+2\). Then \(u_{n+1}-2u_n+u_{n-1}=6\). This is \(2\) times the leading coefficient \(3\).

From \(n-0\mid f(n)-f(0)\), we get \(f(n)\equiv f(0)\pmod n\). If \(n\mid f(n)\) for all \(n\), then \(n\mid f(0)\) for all \(n\), hence \(f(0)=0\). Conversely, if \(f(0)=0\), then \(f(n)-f(0)\) is divisible by \(n\), so \(n\mid f(n)\).

Since \(f(0)=0\), the polynomial \(x\) divides \(f(x)\) in \(\mathbb Z[x]\). Since \(f(1)=0\), \(x-1\) also divides \(f(x)\). They are coprime, so \(x(x-1)\mid f(x)\) in \(\mathbb Z[x]\). Thus \(f(n)=n(n-1)g(n)\) for some \(g\in\mathbb Z[x]\), proving the divisibility.

The numbers \(n\) and \(n-1\) have opposite parity, so their product is divisible by \(2\). Hence \(P(n)\in\mathbb Z\). However, the coefficient of \(x^2\) is \(\frac12\), not an integer. Thus \(P\) is not a polynomial with integer coefficients.

Let \(n\equiv r\pmod m\), \(0\le r

The pairs \((F_n,F_{n+1})\) modulo \(m\) have at most \(m^2\) possible values, so some pair repeats. The transition \((x,y)\mapsto(y,x+y)\) is reversible modulo \(m\): from \((y,z)\) we recover \((z-y,y)\). Hence, once a pair repeats, the period extends backward to the initial pair \((0,1)\). Therefore the sequence is periodic from the start.

Use the identity \(F_{r+d}=F_{d-1}F_r+F_dF_{r+1}\). If \(F_d\mid F_r\), then both terms on the right are divisible by \(F_d\). Hence \(F_d\mid F_{r+d}\). Starting with \(r=d\), induction gives \(F_d\mid F_{2d},F_{3d},\ldots\). If \(n=td\), then \(F_d\mid F_n\).

Modulo \(m\), there are only \(m^2\) possible pairs \((u_n,u_{n+1})\). Hence among the first \(m^2+1\) pairs, two coincide. From the first repetition onward, all later values are determined by the same recurrence, so the residue sequence repeats. This gives eventual periodicity.

Let \(p=f(a)\) be a positive prime. For every integer \(t\), \(a+pt\equiv a\pmod p\), hence \(f(a+pt)\equiv f(a)\equiv0\pmod p\). Since \(f\) is nonconstant, \(|f(a+pt)|\) is unbounded as \(t\) grows. For sufficiently large \(t\), we get a positive value greater than \(p\) but divisible by \(p\). It is composite, a contradiction.

We prove this by induction on \(k\). For \(k=1\), the formula is known. By the binomial theorem,

\[(t+1)^{k+1}-t^{k+1}=(k+1)t^k+\sum_{j=0}^{k-1}\binom{k+1}{j}t^j.\]

Sum over \(t=1,\ldots,n\). The left side telescopes to \((n+1)^{k+1}-1\). By the induction hypothesis, sums of lower powers are already polynomials. Therefore \((k+1)S_k(n)\), and hence \(S_k(n)\), is a polynomial. Its leading term comes from \((n+1)^{k+1}/(k+1)\), so the degree is \(k+1\).

Modulo \(19\), \(2^4=16\equiv-3\). Thus it is enough to have \(2^n\equiv4\pmod{18}\), because the order of \(2\) modulo \(19\) divides \(18\). The residues \(2^n\pmod{18}\) are periodic, and \(2^n\equiv4\pmod{18}\) when \(n\equiv2\pmod6\). Hence for all \(n\equiv2\pmod6\), the number \(2^{2^n}+3\) is divisible by \(19\). For \(n>2\), it is greater than \(19\), hence composite. There are infinitely many such \(n\).

Take \(m=1\) and \(p(x)=x^k+N-1\). Then \(p\in\mathbb Z[x]\), its degree is \(k\), and \(p(1)=1+N-1=N\). The construction is complete.

If \(n^2\mid f(n)\), then in particular \(n\mid f(n)\), so by the criterion for \(n\mid f(n)\), \(f(0)=0\), hence \(f(x)=xh(x)\) with \(h\in\mathbb Z[x]\). Now \(n^2\mid f(n)=nh(n)\) gives \(n\mid h(n)\) for all \(n\). Applying the criterion again, \(h(0)=0\), so \(h(x)=xg(x)\). Therefore \(f(x)=x^2g(x)\). The converse is immediate: \(f(n)=n^2g(n)\).

The operator \(\Delta P(x)=P(x+1)-P(x)\) sends integer values to integer values. Therefore \(\Delta^dP(0)\) is an integer. If the leading coefficient of \(P\) is \(c\), then each application of \(\Delta\) lowers the degree by \(1\) and multiplies the leading coefficient by the current degree. After \(d\) applications, we get the constant polynomial \(d!c\). Hence \(d!c=\Delta^dP(0)\in\mathbb Z\).

Let \(m>n\). From \(F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n\), we get \(F_m\equiv F_{m-n}F_{n+1}\pmod{F_n}\). Since \(\gcd(F_{n+1},F_n)=1\), it follows that \(\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)\). This is exactly the Euclidean step on the indices.

Repeating the step gives \(\gcd(F_m,F_n)=\gcd(F_g,F_0)\), where \(g=\gcd(m,n)\). Since \(F_0=0\), this equals \(F_g\).

Modulo \(m\), the sequence of pairs \((F_n,F_{n+1})\) is purely periodic and starts from \((0,1)\). Hence there is a period \(T>0\) such that \((F_T,F_{T+1})\equiv(0,1)\pmod m\). In particular, \(F_T\equiv0\pmod m\).

The same pair repeats after every period, so \((F_{qT},F_{qT+1})\equiv(0,1)\pmod m\) for all \(q\ge1\). Therefore \(m\mid F_{qT}\) for infinitely many indices \(qT\).