# How to prove that $\gcd(f_n(1),f_n(2),f_n(3),…)=1$ , where $f_n=\frac{x^{n+1}+(a-1)x^{k+1}-a}{x-1}$?

I have polynomial of the form :

$f_n= x^n+x^{n-1}+\cdots+x^{k+1}+ax^k+ax^{k-1}+\cdots+a$

where $\gcd(n+1,k+1)=1$ , $a\in \mathbb{Z^{+}}$ , $a$ is odd number , $a>1$, and $a_1\neq 1$

and I want to show that :

$\gcd(f_n(1),f_n(2),f_n(3),...)=1$

In order to do that I have expressed polynomial in the form of sums :

$f_n=\displaystyle \sum_{i=k+1}^n x^{i}+\displaystyle \sum_{i=0}^k ax^i$

Applying formulas for sum of geometric progression I got following expression :

$$f_n=\frac{x^{n+1}+(a-1)x^{k+1}-a}{x-1}$$

So :

$f_n(2)=P(a)=2^{n+1}+(a-1)\cdot 2^{k+1}-a$

$f_n(3)=Q(a)=\frac{3^{n+1}+(a-1)\cdot 3^{k+1}-a}{2}$

$f_n(4)=R(a)=\frac{4^{n+1}+(a-1)\cdot 4^{k+1}-a}{3}$

Any idea how to prove that :

$\gcd(P(a),Q(a),R(a))=1$ ?

-
Where does that question come from? (i.e. where did you find it) It is very... weird. =) – Patrick Da Silva Nov 22 '11 at 7:49
@PatrickDaSilva,There is strong heuristic evidence that $f_n$ is irreducible.If one can prove this statement then according to Bunyakovsky conjecture polynomial $f_n$ produces infinitely many prime numbers.. – pedja Nov 22 '11 at 8:07

Further conditions are needed. For example, let $$f(x)=x^{10}+x^9+x^8+x^7+x^6+x^5+3x^4+3x^3+3x^2+3x+3.\qquad\qquad (\ast)$$ Then for every integer $i$, $f(i)$ is divisible by $3$.

There is nothing special about $a=3$. Similar examples can be constructed for any odd prime $a$, and probably for every odd $a$.

By putting suitable conditions on $n-k$ (the number of terms that are pure powers of $x$), one should be able to avoid constructions similar to the one that produced $(\ast)$.

Added: The OP suggested that it is sufficient to assume that $n$ and $k$ are of different parity. Indeed it is.

First we show that if $p$ is a prime that doesn't divide $a$, then there is a positive integer $i$ such that $p$ does not divide $f_n(i)$. This is easy, since if we put $i=p$, every term is divisible by $p$ except possibly the rightmost term $a$. So if $p$ does not divide $a$, then $p$ does not divide $f_n(p)$.

If $n$ and $k$ have different parity, the "head" $x^n+\cdots +x^{k+1}$ consists of $n-k$ terms, where $n-k$ is odd. Let $i=a-1$. Since $a-1 \equiv -1 \pmod {a}$, the sum $(a-1)^n+\cdots +(a-1)^{k+1}$ is congruent to $(-1)^n +\cdots +(-1)^{k+1}$ modulo $a$. There is obvious cancellation, and since $n-k$ is odd, we conclude that the sum is congruent to $1$ or $-1$ modulo $a$. The "tail" $a(x^k+\cdots+1)$ does not change the situation modulo $a$. We conclude that $f_n(a-1)$ is congruent to $\pm 1$ modulo $a$. In particular, $f_n(a-1)$ is relatively prime to $a$.

This ends things. If $d$ is the greatest common divisor of the $f_n(i)$, and $p$ divides $d$, then $p$ must divide $a$. But if $p$ divides $a$, then $p$ cannot divide $f_n(a-1)$, since $f_n(a-1)$ is of the shape $ak \pm 1$.

Comment: Let $p_1, p_2, \cdots, p_k$ be the prime divisors of $a$. We have shown that if $n$ and $k$ have opposite parity, then $$\gcd(f_n(p_1), f_n(p_2), \dots, f_n(p_k), f_n(a-1))=1.$$

-
,if $a_1=1$ then $f_n$ isn't always irreducible...what kind of conditions on $n-k$ do you suggest ? I am looking for family of n_th degree univariate polynomials which satisfaying conditions of Bunyakovsky conjecture... – pedja Nov 22 '11 at 12:47
@pedja: Don't know. The gcd of function values being $1$ should not be hard to satisfy. I was kind of surprised that making all function values congruent to $0$ modulo $p$ was so easy. $x^n+a(x^{n-1}+\cdots +1)$ should give relatively prime function values. – André Nicolas Nov 22 '11 at 16:45
Andre,Maybe you can give answer to my previous question related to this one..math.stackexchange.com/q/82974/15660 – pedja Nov 22 '11 at 17:05
$f_n=a_nx^n+a_{n-1}x^{n-1}+....a_1x+a_0$ , $a_1\neq 1$ means that $k \geq 1$ – pedja Nov 22 '11 at 17:26
,It seems that $n-k\equiv 1 \pmod 2$ is sufficient condition... – pedja Nov 30 '11 at 9:19