2
$\begingroup$

Proving that the function $f(x)=x^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ with $a_1,a_2,...,a_n$ integers has a maximum GCD of $n!$ over all integral inputs $x.$ For example, I have thought of $x^2+x$ as proof since for each number it would be $x(x+1),$ one of which would be divisible by $2.$

I have thought of this, and it seems kind of obvious, but I can't think of a way to be true. I mainly have a problem with proving it cannot be greater.
I know equality occurs when it's a polynomial such as

$$x(x+1)(x+2)...(x+n-1)$$

since that is divisible by $n!$ always, but I can't prove that it is the greatest.

Is there an NT proof for this?

$\endgroup$
2
  • 2
    $\begingroup$ GCD is a common divisor of 2 or more numbers: But I only saw $x^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ in your question... 😅 Can you tell me the other number(s)? $\endgroup$ Aug 25, 2018 at 2:39
  • $\begingroup$ I mean plugging in functions and the constant. For example, for $n=2$ $x^2+x+2$ has a gcd of $2$ over all numbers as it is $x(x+1)+2,$ and $x$ or $x+1$ must be divisible by $2.$ I will change this in the problem statement. $\endgroup$
    – Jason Kim
    Aug 25, 2018 at 2:46

1 Answer 1

3
$\begingroup$

Proof is by induction on $n$ that the $GCD$ of $f(x)=\sum_{i=0}^n a_ix^i$ is at most $|a_n|n!$. If $n=1$, then it is clear that the numbers $a_1x+a_0$ and $a_1(x+1)+a_0$ have a GCD of at most $|a_1|$ (which is their difference). Suppose the claim is true for $n$ and let $f(x)=a_{n+1}x^{n+1}+\ldots +a_0$ be a polynomial with integer coefficients. Let $d$ be the GCD of all $f(x), x\in \mathbb{Z}$. We show that $d\leq |a_{n+1}|(n+1)!$. We must have $d|(f(x+1)-f(x))$ for all $x$ and so $d\leq GCD(g(x))$, where $g(x)=f(x+1)-f(x)$. Now $$g(x)=f(x+1)-f(x)=a_{n+1}(x+1)^{n+1}-a_{n+1}x^{n+1} +a_n((x+1)^n-x^n)+\ldots +a_1=a_{n+1}(n+1)x^n+q(x),$$ where $q(x)$ is of degree less than $n$. By the inductive hypothesis, we must have $d \leq GCD(g(x))\leq |a_{n+1}(n+1)|n!=|a_{n+1}|(n+1)!$.

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