8
$\begingroup$

I came up with the following question. I could not find a way to solve it, and haven't seen it anywhere also. Is this an open problem?

Problem statement: Consider a prime number p. Consider all numbers having it as a factor. Repeatedly sum the digits of those numbers until you get a number less than or equal to p. In this sequence, will you ever get a p? Is it guaranteed that you get for various values of p (larger ones)?

For example, a "sum" is defined as applying + together on all digits and get the resulting number. You apply "sum" again on it, if it is larger than p, of course.

Thanks Salahuddin

  • 0
    yea, ok. It is a subsequence of existing one, yes. @ratchet freak: Expanding base to 100 is nice, looks like it is solvable like that, not considering 1s and zeroes solutions also. ok, got it.2012-11-15

2 Answers 2

15

Let $p$ be a prime other than $2$ or $5$. By Fermat's Theorem, $10^{p-1}\equiv 1\pmod{p}$. Consider the sum $N=1+10^{p-1}+10^{2(p-1)}+10^{3(p-1)}+\cdots +10^{(p-1)(p-1)}$ (note there is a total of $p$ terms). Each term in the sum is congruent to $1$ modulo $p$, so $N\equiv 0\pmod{p}$. And the digit sum of $N$ is $p$.

  • 1
    @Salahuddin not really, just a subsequence of this: http://oeis.org/A0690352012-11-14
1

Assume $p\notin\{2,5\}$, in which case $10$ is invertible mod $p$, and its multiplicative order $n$ modulo $p$ is (by definition) such that the power $10^n$ is $1$ modulo $p$ (or one can take $n=p-1$, which will do as well). Now the number $ N=\sum_{i=0}^{p-1}10^{in} $ has sum of digits $p$ and is divisible by $p$. For $p\in\{2,5\}$ take $N=10p$.

More generally (for $p\notin\{2,5\}$), if $a_1,\ldots,a_p$ are distinct integers, one can take $N=\sum_{i=1}^{p}10^{na_i}$, for infinitely many solutions. Or you could have some repeated entries in the list $a_1,\ldots,a_p$, as long as no value occurs more than $9$ times, to make for a change of all those boring digits $1$ (the digits $0$ remain though).

  • 0
    See the last sentence I added. I bet you are now going to ask about solutions that do not use the digits $0$. Or so that it takes at least twice adding up the digits to get to $p$. The point is it is the condition of being divisible by $p$ is not so hard to match, so with varying amounts of effort, I think one can make solutions of all kinds of types.2012-11-14