[Click here for a PDF of this post]

In a previous post I wondered how to prove that for integer \(d \in [1,N]\)

\begin{equation}\label{eqn:numberGame:20}
((N-1) d) \text{mod} N + ((N-1) d) \text{div} N = N-1.
\end{equation}

Here’s a proof in two steps. First for \(N = 10\), and then by search and replace for arbitrary \(N\).

\(N = 10\)

Let

\begin{equation}\label{eqn:numberGame:40}
x = 9 d = 10 a + b,
\end{equation}

where \(1 \le a, b < 9\), and let \begin{equation}\label{eqn:numberGame:180} y = a + b, \end{equation} the sum of the digits in a base \(10\) numeral system. We wish to solve the following integer system of equations \begin{equation}\label{eqn:numberGame:60} \begin{aligned} 9 d &= 10 a + b \\ y &= a + b \\ \end{aligned}. \end{equation} Scaling and subtracting we have \begin{equation}\label{eqn:numberGame:80} 10 y - 9 d = 9 b, \end{equation} or \begin{equation}\label{eqn:numberGame:100} y = \frac{9}{10} \lr{ b + d }. \end{equation} Because \(y\) is an integer, we have to conclude that \(b + d\) is a power of \(10\), and \(b + d \ge 10\). Because we have a constraint on the maximum value of this sum \begin{equation}\label{eqn:numberGame:120} b + d \le 2 ( 9 ), \end{equation} we can only conclude that \begin{equation}\label{eqn:numberGame:140} b + d = 10. \end{equation} or \begin{equation}\label{eqn:numberGame:160} \boxed{ b = 10 - d. } \end{equation} Back substitution into \ref{eqn:numberGame:40} we have \begin{equation}\label{eqn:numberGame:200} \begin{aligned} 10 a &= 9 d - b \\ &= 9 d - 10 + d \\ &= 10 d - 10 \\ &= 10 \lr{ d - 1 }, \end{aligned} \end{equation} or \begin{equation}\label{eqn:numberGame:220} \boxed{ a = d - 1. } \end{equation} Summing \ref{eqn:numberGame:220} and \ref{eqn:numberGame:160}, the sum of digits is \begin{equation}\label{eqn:numberGame:240} a + b = d - 1 + 10 - d = 9. \end{equation}

For arbitrary \(N\)

There was really nothing special about \(9, 10\) in the above proof, so generalizing requires nothing more than some search and replace. I used the following vim commands for this “proof generalization”

:,/For arb/-1 y
:+/For arb/+1
:p
:,$ s/\<9\>/(N-1)/cg
:,$ s/\<10\>/N/cg
:,$ s/numberGame:/&2:/g

Let

\begin{equation}\label{eqn:numberGame:2:40}
x = (N-1) d = N a + b,
\end{equation}

where \(1 \le a, b < N-1\), and let \begin{equation}\label{eqn:numberGame:2:180} y = a + b, \end{equation} the sum of the digits in a base \(N\) numeral system. We wish to solve the following integer system of equations \begin{equation}\label{eqn:numberGame:2:60} \begin{aligned} (N-1) d &= N a + b \\ y &= a + b \\ \end{aligned}. \end{equation} Scaling and subtracting we have \begin{equation}\label{eqn:numberGame:2:80} N y - (N-1) d = (N-1) b, \end{equation} or \begin{equation}\label{eqn:numberGame:2:100} y = \frac{N-1}{N} \lr{ b + d }. \end{equation} Because \(y\) is an integer, we have to conclude that \(b + d\) is a power of \(N\), and \(b + d \ge N\). Because we have a constraint on the maximum value of this sum \begin{equation}\label{eqn:numberGame:2:120} b + d \le 2 ( N-1 ), \end{equation} we can only conclude that \begin{equation}\label{eqn:numberGame:2:140} b + d = N. \end{equation} or \begin{equation}\label{eqn:numberGame:2:160} \boxed{ b = N - d. } \end{equation} Back substitution into \ref{eqn:numberGame:2:40} we have \begin{equation}\label{eqn:numberGame:2:200} \begin{aligned} N a &= (N-1) d - b \\ &= (N-1) d - N + d \\ &= N d - N \\ &= N \lr{ d - 1 }, \end{aligned} \end{equation} or \begin{equation}\label{eqn:numberGame:2:220} \boxed{ a = d - 1. } \end{equation} Summing \ref{eqn:numberGame:2:220} and \ref{eqn:numberGame:2:160}, the sum of digits is \begin{equation}\label{eqn:numberGame:2:260} a + b = d - 1 + N - d = N-1. \end{equation} This completes the proof of \ref{eqn:numberGame:20}.