# Sum of digits modulo a polynomial

I made the following problems a while ago but I can't solve them (though I don't think it's too hard)

1.Let $s(n)$ be the digits sum of $n$. Let also $f(n)$, $g(n)$ $\in Z[X]$ . Assume that: $$s(n) \equiv f(n) \pmod{g(n)}$$ for every $n$ (as long as $g(n)$ isn't $0$).

Then show that $g$ is a constant polynomial and $f$ has degree exactly $1$.

As I think you already observed the only congruences that will work are derived from the classical $s(n) \equiv n \pmod{9}$ , for example :

$s(n) \equiv 19n-18 \pmod{9}$

What I tried :

Immediately I thought about the most important thing that connects polynomials and number theory : $$a-b \mid g(a)-g(b)$$

Using this I got stuff like this :

$$g(n) \mid kg(n) \mid g(n+kg(n))-g(n)$$ so $$g(n) \mid g(n+kg(n))$$

Now I made $k$ a super big power of $10$ bigger than $n$ ($k=10^l>n$)

So it's obvious that $s(n+kg(n))=n+g(n)$ for every such $k$

Now use the initial relation for two such $k$'s : $x$ and $y$ to get : $$s(n+xg(n)) \equiv f(n+xg(n)) \pmod{g(n)}$$ and the analogue for $y$ which then subtracted gives :

$$f(n+xg(n)) \equiv f(n+yg(n)) \pmod{g(n)}$$ but this is already true so...I'm stuck.

Now the second problem :

2.Let $a$ be a positive integer and $g \in Z[X]$. Assume that: $$s(n) \equiv a^n \pmod{g(n)}.$$ Then show that $g$ is constant.

What I tried : I think that in this problem the previous method works better .

As before you can get :

$$a^{n+xg(n)} \equiv a^{n+yg(n)} \pmod{g(n)}$$

We can choose from the beginning an $n$ such that $g(n)$ and $a$ are coprime else it follows that $s(n)$ and $a$ are never coprime which is false for the $n$ made of $a+1$ ones .

So (assuming $x>y$ ) :

$$a^{(x-y)g(n)} \equiv 1 \pmod{g(n)}$$

This is where I'm stuck but I think that more can be done this way .

I think these problems are very interesting and (maybe) can be solved by only elementary means . I'd appreciate any thoughts .Thanks in advance for all the help.

Here is a solution to question 1. I am still thinking about question 2.

## Solution to Question 1

First, we want to replace the polynomial $f$ with its remainder when divided by $g$. So we could write $f(x) = h(x) g(x) + r(x)$, where $\deg r < \deg g$. Unfortunately, $h(x)$ and $r(x)$ could have rational coefficients rather than integer coefficients. So instead, multiply out by their common denominator, and write $$M f(n) = h(n) g(n) + r(n)$$ for some positive integer $M$, where $h, r$ are polynomials with integer coefficients, and $\deg r < \deg g$.

Now, fix an integer $k$, $k \ge 1$. Notice, there are infinitely many positive integers $n$ for which $s(n) = k$. So there are infinitely many $n$ such that $g(n) \mid f(n) - k$. This implies $g(n) \mid M f(n) - Mk = h(n) g(n) + r(n) - Mk$, which implies $g(n) \mid r(n) - Mk$ for infinitely many $n$.

However, $\deg r < \deg g$. If $\deg r \ge 1$, then $\deg g > \deg r$ implies that for sufficiently large $n$, $g(n) > r(n) - Mk > 0$, which contradicts that $g(n)$ divides $r(n) - Mk$ for infinitely many $n$. So $r(n)$ is constant, say $r(n) = R \in \mathbb{Z}$.

In summary, there is a constant $R$ such that for any $k$, there are infinitely many values of $n$ such that $g(n)$ divides $R - Mk$. But pick $k$ so that $R - Mk \ne 0$, and we get that $\boldsymbol{g(n)}$ must be a constant polynomial, as required.

Working further, let $g(n) = G \in \mathbb{Z}$. Let $c$ be the constant coefficient of $f$. For any prime $k \in \mathbb{Z}$, we have that $f(kp) \equiv c \pmod{G}$. Therefore, as $G \mid f(n) - s(n)$ for all $n$, $s(kG) \equiv c \pmod{G}$ for all $k$. But pick $k = 10^j + 1$, where $j$ is large enough that $s(kG) = s(G) + s(G)$. Then we get $s(G) + s(G) \equiv c \equiv s(G)$, so $s(G) \equiv 0$, so $G \mid s(G)$. But this implies $G \le s(G)$, which can only happen if $G < 10$. So $G \in \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

But we also have from $s(G) = G$ that $G \mid S(kG)$ for all $k \in \mathbb{G}$. $G$ cannot be $2, 4, 5,$ or $8$, because then $1000$ is a multiple of $G$, and $G \mid S(1000) = 1$. Similarly, $G$ cannot be $6$, else $G \mid S(12) = 3$, and $G$ cannot be $7$, else $G \mid S(14) = 5$. So $\boldsymbol{g(n) = G \in \{1, 3, 9\}}$.

We are almost there. Let $p(x) = f(x) - x$. It is a familiar fact that for any of these three $G$, $s(n) \equiv n \pmod{G}$ for all $n$. So $f(n) \equiv s(n) \equiv n \pmod{G}$ for all $n$. So $p(n) \equiv 0 \pmod{G}$ for all $n$.

Thus, all possible solutions are: \begin{align*} g(n) &= 1 \text{ and } f(n) \text{ is any polynomial;} \\ g(n) &= 3 \text{ and } f(n) = n + p(n), \text{ where } p(n) \text{ is a polynomial that is always a multiple of 3;} \\ g(n) &= 9 \text{ and } f(n) = n + p(n), \text{ where } p(n) \text{ is a polynomial that is always a multiple of 9.} \end{align*}

As a side note, it is not true that $f$ has degree exactly $1$, as you claimed. Nor is it even true that e.g. in the case $g(n) = 9$, $f(n) = n + 9q(n)$ for some polynomial $q$. For example, $f(n)$ could be $n + (n-1)(n-2)(n-3)\cdots (n-9)$. The polynomial $p$ always returns a multiple of $9$ when evaluated, but might not be a multiple of $9$ itself.