# Showing that prime factors of a number is congruent to $1 \pmod 5$

I have come across numbers of the form $$b=1+10a+50a^2+125a^3+125a^4$$ where $$a$$ is a positive integer.

Looking at the prime factors of $$b$$, I am conjecturing that all prime factors of $$b$$ are $$\equiv 1 \pmod 5$$. But I cannot prove this. Looking at $$b$$ in $$\bmod 5$$, we see that $$b \equiv 1 \pmod 5$$. If $$p$$ is a prime divisor of $$b$$, then I cannot necessarily conclude that $$p \equiv 1 \pmod 5$$, for example $$91 \equiv 1 \pmod 5$$, but $$91 = 7 \times 13$$. However, I think with the way that $$b$$ is defined, it can be shown that its prime divisors are actually congruent to $$1 \pmod 5$$.

Here are the first few numerical data for the choices of $$a$$:

$$a=1, b = 311, \{ 311 \}$$ $$a=2, b=3221, \{ 3221 \}$$ $$a=3, b=13981, \{ 11,31,41 \}$$

• After a bit of testing, it really looks like this conjecture runs deeper than I anticipated... Commented Feb 8, 2023 at 5:55
• Verified till $a=10000$ using python
– D S
Commented Feb 8, 2023 at 7:11
• Hint : $$b=\frac{(5a+1)^5-1}{25a}$$ Commented Feb 8, 2023 at 7:51

Peter beat me to it in the comments, but here is a general result. Let $$\Phi_n(x)$$ denote the $$n^{th}$$ cyclotomic polynomial. This is the unique sequence of monic integer polynomials satisfying

$$x^n - 1 = \prod_{d \mid n} \Phi_d(x)$$

which exist and are unique by Möbius inversion. Then:

Claim: If $$a$$ is an integer, then all the prime factors $$p$$ of $$\Phi_n(a)$$ which do not divide $$n$$ are congruent to $$1 \bmod n$$.

This result can be used, among other things, to prove that there are infinitely many primes congruent to $$1 \bmod n$$ in an elementary way without the full strength of Dirichlet's theorem.

Sketch. Let $$p$$ be a prime not dividing $$n$$ which divides $$\Phi_n(a)$$. The idea is to show that $$\Phi_n(a) \equiv 1 \bmod p$$ if and only if $$a \bmod p$$ has multiplicative order $$n$$ in the group of units $$\mathbb{F}_p^{\times}$$. Since by definition $$\Phi_n(a) \mid a^n - 1$$ we have that $$a^n \equiv 1 \bmod p$$, so $$a$$ has order dividing $$n$$. Letting $$f(x) = x^n - 1$$, we have that since $$f'(x) = nx^{n-1}$$ is nonzero $$\bmod p$$ by hypothesis, the roots of $$f(x) \bmod p$$ all have multiplicity $$1$$, and since by definition

$$x^n - 1 = \prod_{d \mid n} \Phi_n(x)$$

it follows that $$\Phi_d(a) \not \equiv 0 \bmod p$$ for all proper divisors $$d$$ of $$n$$ (or else $$a$$ would be a root of multiplicity greater than $$1$$), hence that $$a^d \not \equiv 1 \bmod p$$ for all proper divisors $$d$$ of $$n$$. So $$a \bmod p$$ has order exactly $$n$$ as desired.

Since $$\mathbb{F}_p^{\times}$$ has order $$p-1$$, by Lagrange's theorem $$p-1$$ must be divisible by $$n$$. $$\Box$$

This result strongly suggests that your polynomial $$f(x) = 1 + 10x + 50x^2 + 125x^3 + 125x^4$$ is related to $$\Phi_5(x) = 1 + x + x^2 + x^3 + x^4$$ in some way. We can relate them as follows:

$$\begin{eqnarray*} 5f(x) &=& 5 + 10(5x) + 10(5x)^2 + 5(5x)^3 + (5x)^4 \\ &=& \frac{(5x + 1)^5 - 1}{5x} \\ &=& \Phi_5(5x + 1). \end{eqnarray*}$$

So $$f(x) = \frac{(5x + 1)^5 - 1}{25x}$$ as Peter says in the comments. So if $$p \neq 5$$ is a prime dividing $$f(a)$$ for some integer $$a$$ then $$p$$ divides $$\Phi_5(5a + 1)$$ and then the claim above shows that $$p \equiv 1 \bmod 5$$. Moreover, since $$f(a) \equiv 1 \bmod 5$$, $$p$$ is never equal to $$5$$.

• shouldn't it be $\prod\limits_{d \mid n} \Phi_d(x)$ and not $\prod\limits_{d \mid n} \Phi_n(x)$? Otherwise, everything else makes sense. thanks
– Josh
Commented Feb 8, 2023 at 16:03

As Peter's comment states,

$$b = \frac{(5a+1)^5-1}{25a}$$

Thus, for any prime $$p \mid b$$, then also $$p \mid (5a+1)^5 - 1$$. Using the multiplicative order, with

$$m = \operatorname{ord}_p(5a+1)$$

then $$m \mid 5$$. However, $$m \neq 1$$ since $$(5a+1)-1 = 5a$$ and $$\gcd(5a, b) = 1$$, so $$m = 5$$. Both Fermat's little theorem and Euler's totient function give that $$(5a+1)^{p-1}\equiv 1\pmod{p}$$, which means that

$$5 \mid p - 1 \; \; \to \; \; p \equiv 1 \pmod{5}$$