How can factorization prove the compositeness of a given expression?

[anemone]

Prove that for every positive integer $a$, the integer $5^{4a}+5^{3a}+5^{2a}+5^a+1$ is composite.

 

[anemone]

Hint:

Spoiler

Try to think along the line of the following expression:

$x^8+x^6+x^4+x^2+1$

 

[kaliprasad]

I generally do not provide a solution leaving out a few cases but in this case I could cover all the cases with one exception

Spoiler

we have the polynomial
$P(a)=\dfrac{5^{5a}-1}{5^a-1}$

There are 3 cases
a is 1 so P(1) = 781 = 11 * 71 not a prime

a is even say 2b

we get
$P(x)=\dfrac{5^{10b}-1}{5^{2b}-1} = \dfrac{5^{5b}-1}{5^{b}-1} \dfrac{5^{5b}+1}{5^b+1}$
$= \dfrac{(5^{4b}+5^{3b} + 5^{2b}+5^b+1)(5^{5b}+1)}{5^b+1}$

now we see that $5^b+1$ must divide the numerator and it is not same as any term of the numerator as both terms are bigger so we shall be left with 2 terms in numerator and it is not a prime

Now we need to consider when a is odd and > 1

then
numerator can be expressed as product in 2 different ways 1) $(5^a-1)(1+5^a+5^{2a}+5^{3a} + 5^{4a})$2) $(5^5-1)(1+5^5+5^{2*5}+5^{3*5} + 5^{5*(a-1)})$

now the denominator cannot be cancelling one of the terms in numerator in both the cases and hence this is not a prime

but with one exception that is a = 5.

this is left out

 

[Nono713]

I generally do not provide a solution leaving out a few cases but in this case I could cover all the cases with one exception

Spoiler

we have the polynomial
$P(a)=\dfrac{5^{5a}-1}{5^a-1}$

There are 3 cases
a is 1 so P(1) = 781 = 11 * 71 not a prime

a is even say 2b

we get
$P(x)=\dfrac{5^{10b}-1}{5^{2b}-1} = \dfrac{5^{5b}-1}{5^{b}-1} \dfrac{5^{5b}+1}{5^b+1}$
$= \dfrac{(5^{4b}+5^{3b} + 5^{2b}+5^b+1)(5^{5b}+1)}{5^b+1}$

now we see that $5^b+1$ must divide the numerator and it is not same as any term of the numerator as both terms are bigger so we shall be left with 2 terms in numerator and it is not a prime

Now we need to consider when a is odd and > 1

then
numerator can be expressed as product in 2 different ways 1) $(5^a-1)(1+5^a+5^{2a}+5^{3a} + 5^{4a})$2) $(5^5-1)(1+5^5+5^{2*5}+5^{3*5} + 5^{5*(a-1)})$

now the denominator cannot be cancelling one of the terms in numerator in both the cases and hence this is not a prime

but with one exception that is a = 5.

this is left out

Spoiler

Can you explain how $5^{5a} - 1 = (5^5-1)(1+5^5+5^{2*5}+5^{3*5} + 5^{5*(a-1)})$? Also, I am not sure your proof works for $a$ power of 5 (not just $a = 5$ but every power of 5) can you verify.

 

[Opalg]

Prove that for every positive integer $a$, the integer $5^{4a}+5^{3a}+5^{2a}+5^a+1$ is composite.

Another partial solution.
[sp]If $a$ is not a multiple of $5$ then the numbers $a$, $2a$, $3a$, $4a$ are congruent $\pmod5$ to $1$, $2$, $3$, $4$, in some order. Now working mod $11$, you find that $5^a$, $5^{2a}$, $5^{3a}$, $5^{4a}$ are congruent $\pmod{11}$ to $5$, $3$, $4$, $9$. It follows that $5^{4a}+5^{3a}+5^{2a}+5^a+1 \equiv 9+4+3+5+1 = 22 \equiv0 \pmod{11}$.

The same result applies if you work mod $71$ instead of mod $11$, because both $p=11$ and $p=71$ have the property that $5^5\equiv1\pmod p$.

It follows that if $a$ is not a multiple of $5$ then $5^{4a}+5^{3a}+5^{2a}+5^a+1$ is divisible by $11\times 71 = 781$. But I could not find any way to prove the result when $a$ is a multiple of $5$.[/sp]

 

[kaliprasad]

Spoiler

Can you explain how $5^{5a} - 1 = (5^5-1)(1+5^5+5^{2*5}+5^{3*5} + 5^{5*(a-1)})$? Also, I am not sure your proof works for $a$ power of 5 (not just $a = 5$ but every power of 5) can you verify.

Spoiler

This is based on expansion of

$a^{mn} - 1= (a^m)^n - 1= (a^m-1)(1 + a^m +\cdots + a^{m(n-1)})$

 

[Nono713]

Spoiler

This is based on expansion of

$a^{mn} - 1= (a^m)^n - 1= (a^m-1)(1 + a^m +\cdots + a^{m(n-1)})$

Spoiler

Ah, I see, thanks, an ellipsis was missing. Though I think that still is not strong enough to solve the problem for $a$ power of 5, since in that case $5^a - 1$ may very well be composite and automatically is a multiple of $5^5 - 1$, leaving open whether $1 + 5^5 + 5^{2 \cdot 5} + \cdots$ is prime or not, unless I misunderstood.

Here is another partial solution slightly stronger than Opalg's:

Spoiler

Suppose $5^{4a} + 5^{3a} + 5^{2a} + 5^a + 1$ is composite for some $a \geq 1$. Then for every prime $p$ dividing that expression we have:
$$5^{4a} + 5^{3a} + 5^{2a} + 5^a + 1 \equiv 0 \pmod{p}$$
That is:
$$\frac{5^{5a} - 1}{5^a - 1} \equiv 0 \pmod{p}$$
Which implies that:
$$5^{5a} \equiv 1 \pmod{p} ~ ~ ~ \text{and} ~ ~ ~ 5^a \not \equiv 1 \pmod{p}$$
Observe that these equations imply $5^a$ has order 5 modulo $p$, since 5 is prime. Now let $k$ be an integer not multiple of 5, then we have:
$$\left ( 5^{5a} \right )^k \equiv 5^{5ak} \equiv 1 \pmod{p}$$
And since $k$ is not a multiple of 5 and $5^a$ has order 5 modulo $p$, it must follow that:
$$\left ( 5^{a} \right )^k \equiv 5^{ak} \not \equiv 1 \pmod{p}$$
So we conclude that:
$$\frac{5^{5ak} - 1}{5^{ak} - 1} \equiv 0 \pmod{p}$$
Such that:
$$5^{4ak} + 5^{3ak} + 5^{2ak} + 5^{ak} + 1 \equiv 0 \pmod{p}$$
And so we conclude that $f(ak)$ is a multiple of $f(a)$ and so is also composite. With the above theorem it suffices to show that the expression is composite for powers of 5. In particular, it is composite at $a = 1 = 5^0$, hence is composite at all $a$ not multiple of 5, and it can be verified that it is also composite at $a = 5$, hence it is composite at all $a$ not multiple of 25. We can keep going and check that the expression is composite for $a = 25$ as well, showing that the expression is composite for all $a$ not multiple of 125, but I don't know how to prove that it must be composite for all powers of 5, which is required to show it is composite for all integer $a$.​

 

[anemone]

Thanks to kaliprasad, Opalg, and Bacterius for trying and partially solving this challenge!:)

I have a solution at hand that merely used the factorization technique to prove the given expression is a composite, and I will share it here now:

Spoiler

Observe the following representations:

$x^8+x^6+x^4+x^2+1=(x^4+x^3+x^2+x+1)(x^4-x^3+x^2-x+1)$---(1)

and

$x^4+x^3+x^2+x+1=(x^2+3x+1)^2-5x(x+1)^2$---(2)

When $n=2a$ is even, we can substitute $x=5^a$ into equation (1) to get a factorization.

When $n=2a-1$ is odd, we can substitute $x=5^{2a-1}$ into equation (2) to get a difference of squares, which can then be factored.