# There are infinitely many non-harshad Fibonacci numbers

A harshad number is an integer that is divisible by the sum of its digits. For example, $$280$$ is a harshad number as it is divisible by $$2+8+0=10$$. Prove that there are infinitely many non-harshad Fibonacci numbers.

This question was posed in the exercises after a chapter on Dirichlet's Theorem on primes in arithmetic progression.

Now, I know that there are infinitely primes that are not Fibonacci numbers. This can be proved by checking the Fibonacci numbers modulo $$11$$ and realizing that they can never be of the form $$11k+4$$. I don't know whether this is any useful though.

The main problem is that I cannot relate Harshad numbers in any way with primes or with arithmetic progressions. This post gives an explicit construction of a Harshad number with digit sum $$s$$. Maybe, this can be used to get Harshad numbers of digit sum $$p$$ prime - I have no idea.

I was given this hint : First show that the sum of the digits of $$F_n$$ is $$O(n)$$. Then show that for any prime $$p$$, any prime factor $$q$$ of $$F_p$$ is $$\equiv \pm 1\pmod p$$.

I have no idea how to show any one of these two. Especially, how do I get to know the asymptotic behavior of sum of digits of $$F_n$$?

• The only prime Harshad numbers are the single-digit primes 2, 3, 5, and 7. So, if there are infinitely many Fibonacci primes (which is an open problem), then there are also infinitely many non-Harshad Fibonacci numbers. Commented Oct 13, 2023 at 16:54
• @GeoffreyTrang that's a good observation, but I don't think they meant it to be solved like this! Commented Oct 14, 2023 at 13:08

We can see that the sum of digits of $$F_n$$ is $$O(n)$$ because $$F_n < \phi^n$$, so $$F_n$$ has at most $$\log_{10}(\phi)n < 0.21 n$$ digits, and their digit sum is at most $$9 \cdot 0.21 n = 1.89 n$$.
For the second part, we have $$F_p \equiv 0 \pmod q$$ iff $$\alpha(q) | p$$, where $$\alpha$$ is the Fibonacci entry point. Since $$p$$ is prime, this implies $$\alpha(q) = p$$. According to a comment on the OEIS entry, $$\alpha(q)$$ divides either $$q+1$$ or $$q-1$$ (expect for $$p=q=5$$, but that isn't a problem), so $$q \equiv \pm 1 \pmod{p}$$.
This implies that the smallest factor of $$F_p$$ is at least $$p-1$$. However, since that sum of digits is at most $$1.89p$$, for it to divide $$F_p$$ (for large enough $$p$$) is has to be prime, and one of $$p-1, p+1$$. But both of these must be even, and can't be prime. This shows that for all primes $$p>5$$, $$F_p$$ isn't a Harshad number.
This doesn't actually use Dirichlet's theorem. However, if instead of bounding the digit sum by $$1.89 n$$ you only bound it by $$C n$$, you still have $$2p-1, 2p+1, 4p-1, 4p+1, 6p-1, 6p+1, \dots, Cp-1$$, and you can get rid of these possibilities by having $$2p-1 \equiv 0 \pmod 3, 2p+1 \equiv 0 \pmod 5 , 4p-1\equiv 0 \pmod 7, \dots$$, which has infinitely many solution thanks to the Chinese remainder theorem and Dirichlet's theorem.