Show that for an odd integer $n ≥ 5$, $5^{n-1}\binom{n}{0}-5^{n-2}\binom{n}{1}+…+\binom{n}{n-1}$ is not a prime number.

Question

I would prefer no total solutions and just a hint as to whether or not I’m at a dead end with my solution method.

So far this is my work:

From the binomial expansion,

$$\sum_{j=0}^n 5^{n-j}(-1)^j\binom{n}{j}= (5+(-1))^n = 4^n$$

Thus,

$$\sum_{j=0}^{n-1}5^{n-1-j}(-1)^j\binom{n}{j} = \frac{4^n+1}{5}$$ However, $\frac{4^n+1}{5} = \frac{(4+1)}{5}(4^{n-1}-4^{n-2}+…+1)= 4^{n-1}-4^{n-2}+…+1$.

Here I am stuck. My attempts have been to find a factorization of the polynomial $\sum_{j=0}^k (-x)^j $ where $k$ is even. However, I’m reasonably certain there’s an argument to be made that the polynomial is irreducible modulo $2$ implying that it’s irreducible in $\mathbb{Q}$.

This leads me to thinking that this route is a dead end since I can’t find any specific primes which reduce the expression nicely under a mod.

Answer 1

You want to show that for odd integer $n$, $ \frac{ 4^n + 1 } { 5}$ is composite.

You're on the right track, though this numerator isn't irreducible, so hint: Find the factorization.

Writing $n = 2k+1$, does $ 4 \times 4^{2k} + 1$ remind you of any factorizations?

Hint: Sophie Germain's identity is $a^4 + 4b^4 = [ (a+b)^2 + b^2] [(a-b)^2 + b^2]$

For odd integer $n$, this allows us to factorize the numerator $4^n + 1$ into 2 terms, both greater than 5 (and one of which is a multiple of 5). Hence, the expression is composite.