Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $g_m(b)$ be the coefficient of $x^m$ the power series


(When $b=1$, this is just the generating function of Fibonacci numbers.) Of course, $g_m(b)$ depends on both $m$ and $b$. Now fix $m$, and let $b$ run from 1 to $\infty$. Can the $g_m(b)$'s have a non-trivial common divisor for some $m$?

It seems reasonable to believe this cannot happen, but I don't see how to prove it. The relation among the $g_m(b)$'s for a fixed $b$ is simple. But for a fixed $m$, I don't see how to relate the $g_m(b)$'s.

share|cite|improve this question
up vote 1 down vote accepted

No. Note that $g_m$ has constant term $1$. If all values of $g_m(b)$ have a common divisor $d$, then $d | g_m(d)$, but $g_m(d) \equiv g_m(0) = 1 \bmod d$.

Initially I wanted to resolve this problem using the following lemma, which is unnecessary. But I thought I would keep it here in case anyone was interested.

Lemma: Let $f(x)$ be a polynomial which attains integer values when $x$ is an integer. If $d$ is an integer such that $d | f(x)$ for all positive integers $x$, then $d | f(x)$ for all integers $x$.

Proof. We need to observe the following facts about the finite difference operator $\Delta f(x) = f(x + 1) - f(x)$.

  1. $d | f(x)$ for all positive integers $x$ if and only if $d | f(1)$ and $d | \Delta f(x)$ for all positive integers $x$.

  2. $d | f(x)$ for all integers $x$ if and only if $d | f(1)$ and $d | \Delta f(x)$ for all integers $x$.

  3. If $f$ is a polynomial, then $\Delta f$ is a polynomial of degree $\deg f - 1$.

It follows that $d | f(x)$ for all positive integers $x$ if and only if

$$d | f(1), \Delta f(1), \Delta^2 f(1), ... \Delta^{\deg f} f(1)$$

and $d | \Delta^{\deg f+1} f(x)$ for all positive integers $x$. But $\Delta^{\deg f+1} f$ is identically zero, hence $d | \Delta^{\deg f+1} f(x)$ for all integers $x$, hence $d | f(x)$ for all integers $x$.

Incidentally, these polynomials are closely related to the Chebyshev polynomials of the second kind.

share|cite|improve this answer
Proof 1 seems not valid. Fix $p$, then every element of $\mathbb{F}_p$ is a root of $x^p-x$. Your argument only shows that a prime common divisor cannot be larger than the degree of $f$. – h__ Aug 25 '12 at 2:04
@hyh: you are right. Actually I made the argument much more complicated than necessary. – Qiaochu Yuan Aug 25 '12 at 2:08
I actually should have asked a different question to avoid your counter-example in the question: is it possible for some $m$ there is a prime $p$ which divides $g_m(b)$ for all $b$ that's coprime to $p$? i.e. is it possible for $x^{p−1}−1$ to divide $g_m(x)$ mod $p$? – h__ Aug 25 '12 at 7:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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