% Jonathan Frech, August to September 2019


\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[onehalfspacing]{setspace}
\setlength{\parindent}{0pt}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage[english]{babel}

\usepackage{nicefrac}

\newcommand{\N}{\mathbb{N}}
\newcommand{\ds}{\mathrm{ds}}
\newcommand{\fds}{\mathrm{fds}}

\usepackage{amsthm}
\newtheorem*{theorem}{Theorem}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}


\title{Digit Sums}
\author{Jonathan Frech}
\date{August to September 2019}


\begin{document}
	\maketitle
	
	Throughout this document the notation $0\in\N\neq\N^+$ is used. Furthermore, the letter $b\geq 2$ will always denote a base.
	
	\begin{theorem}[Unique $b$-adic representation]
		Let $n\in\N$ a natural number. There exists a unique $b$-adic representation
		\[
			n = \sum_{j=0}^k a_j\cdot b^j
		\]
		where $k\in\N$ is minimally chosen with $0\leq a_j < b$ for all $0\leq j\leq k$.
	\end{theorem}
	\begin{proof}
		Existence of the above representation will first be shown by inducting on natural numbers less than $b^{k+1}$.\\
		\textbf{Base case.} For natural numbers $0\leq n<b^1$ the representation $a_0 := n$ exists.\\
		\textbf{Induction step.} Let $0\leq n<b^{k+1}$ be a natural number. Euclidian division gives natural numbers $0\leq n_\star < b^k$ and $0\leq a_\star < b$ such that $n = b\cdot n_\star + a_\star$. By induction on $n_\star$ the representation 
		\[
			n = b\cdot n_\star + a_\star = b\cdot\left( \sum_{j=0}^{k_\star}a_j\cdot b^j \right) + a_\star
		\]
		exists.\\
		
		To show uniqueness, note that for all $k\in \N$ and $0\leq a_j< b$ the inequality
		\[
			b^k > b^k-1 = (b-1) \cdot \sum_{j=0}^{k-1}b^j \geq \sum_{j=0}^{k-1}a_j\cdot b^j
		\]
		holds. Now suppose, a number had two different representations. Since both contain finitely many digits, there has to be a maximum index $j$ such that the digits $a_j\neq a_j'$ differ. However, since both represent the same and by the above inequality this requires two digits with a higher index to differ, contradicting the maximality of $j$.
	\end{proof}
	
	
	\newpage
	
	
	\begin{definition}[Digit sum]
		Let $n\in\N$ a natural number with its unique $b$-adic representation $n=\sum a_jb^j$. Let
		\[
			\ds_b(n) := \sum_{j=0}^k a_j
		\]
		denote the $b$-adic digit sum of $n$.\\
		
		Note that $\ds_b\big|_{\N_{<b}} = \mathrm{id}\big|_{\N_{<b}}$ as well as that $\ds_b\big|_{\N_{\geq b}}$ is strictly monotonically decreasing.
	\end{definition}
	
	\begin{definition}[Finite fixpoint limit]
		Let $A$ be a set and $f:A\to A$ a mapping. It denotes
		\[
			f^\infty: A\to A, x\mapsto
			\begin{cases}
				x & \text{if}\ x = f(x), \\
				f^\infty(f(x)) & \text{otherwise}
			\end{cases}
		\]
		the finite fixpoint limit of $f$, provided the recursion terminates.
	\end{definition}
	
	\begin{remark}[Continuation of transitive relations]
		Let $A$ be a set, $f:A\to A$ a mapping for which $f^\infty$ exists and $\sim\ \subset A\times A$ a transitive relation such that $x\sim f(x)$ for all $x\in A$. Then
		\[
			x\sim f^\infty(x)
		\]
		follows for all $x\in A$.
	\end{remark}
	\begin{proof}
		Since $f^\infty$ exists, the chain
		\[
			x \sim f(x) \sim f(f(x)) \sim \dots \sim f^\infty(x)
		\]
		requires only finitely many relations, implying per transitivity $x\sim f^\infty(x)$.
	\end{proof}
	
	\begin{definition}[Final digit sum]
		Let
		\[
			\fds_b := \ds_b^\infty
		\]
		denote the $b$-adic final digit sum, whereby its existence is guaranteed by $\N$ being well-ordered and by $\ds_b$ strictly monotonically decreasing for non-fixpoints.\\
		
		Note that $\mathrm{im}(\fds_b)=\N_{<b}$.
	\end{definition}
	
	
	\newpage
	
	
	\begin{theorem}[Congruence to the digit sum]
		Let $n\in\N$ be a natural number. Then
		\[
			n \equiv \ds_b(n) \mod (b-1).
		\]
	\end{theorem}
	\begin{proof}
		\begin{align*}
			n &= \sum_{j=0}^ka_j\cdot b^i = \sum_{j=0}^k a_j + \sum_{j=1}^ka_j\cdot(b^j-1) \\
			&= \ds_b(n) + \sum_{j=1}^ka_j\cdot \left((b-1)\cdot \sum_{i=0}^{j-1}b^i\right) \\
			&= \ds_b(n) + (b-1)\cdot \left(\sum_{j=1}^ka_j\cdot\sum_{i=0}^{j-1}b^i\right) \\
			&\equiv \ds_b(n) \mod (b-1)
		\end{align*}
	\end{proof}
	
	\begin{lemma}[Congruence implies divisor equivalence]
		Let $m,n,n',d\in N$ be natural numbers such that
		\[
			n \equiv n' \mod m
		\]
		as well as $d\mid m$. Then
		\[
			d\mid n \iff d \mid n'.
		\]
	\end{lemma}
	\begin{proof}
		With $d\mid m$ and $m \mid (n-n')$ it follows that
		\[
			d\mid (n-n')
		\]
		and thus divisor equivalence.\\
		
		Note that the reverse does not hold, as $\{m=6,n=5,n'=7\}$ shows.
	\end{proof}
	
	\begin{corollary}[Divisibility equivalence]
		Let $n,d\in\N$ be two natural numbers with $d\mid (b-1)$. Then
		\[
			d \mid n \iff d \mid \ds_b(n).
		\]
	\end{corollary}
	\begin{proof}
		Combining both \textit{Congruence to the digit sum} and \textit{Congruence implies divisor equivalence}.
	\end{proof}
	
	
	\newpage
	
	
	\begin{remark}[A family of constant final digit sums]
		The final digit sum in base ten of three consecutive positive natural numbers of which the largest is divisible by three is six.\footnote{Factoid taken from Child, Lee: \textit{Der Anhalter}. München: Blanvalet, 2015; p. 73.}
	\end{remark}
	\begin{proof}
		Let $n\in\N^+$ be a positive natural number. One calculates
		\begin{align*}
			\fds_{10}\left(\sum_{j=0}^2 (3n-j)\right) &= \fds_{10}(3n-2+3n-1+3n) \\
			&= \fds_{10}(9n-3) \\
			&\overset\star\equiv 9n-3 \mod 9 \\
			&\equiv 6 \mod 9,
		\end{align*}
		whereby $\star$ follows from both \textit{Congruence to the digit sum} and \textit{Continuation of transitive relations}. Since $\mathrm{im}(\fds_{10})=\N_{<10}$, equality follows.
	\end{proof}
\end{document}