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$?
Best Answer
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.