Why can a positive integer be written "in base p"?

Question

I've come across a statement in Gouvea's "p-adic Numbers" that I'm confused about. Suppose $m$ is a positive integer and $p$ is prime. Why is it true that we can write $m=a_0+a_1p+a_2p^2+\cdots + a_np^n$ with $a_i\in\mathbb{Z}, 0\leq a_i\leq p-1$?

Answer 1

It has nothing to do with $p$ but any integer greater than $1$ (such as $10$) can do that. That is simply digital notation.

All numbers can be written as $m=a_0+a_1p+a_2p^2+\cdots + a_np^n$ for the EXACTLY same reason all numbers can be written as $m = m=a_0+a_1*10+a_2*100+\cdots + a_n10^n$ where $a_i = 0......9$, which is how we have been counting numbers all our lives.

$1456 = 6 + 5*10 + 4*10^2 + 1*10^3$ for example.

We've been doing this all our lives!

...

Okay, why can we write all numbers in decimal notation? (Just because we've done it since we learned to count and never questioned it doesn't answer why we can do it.)

---

To begin with $a_0$ is found by taking the remainder of $m$ when divided by $10$... or $p$. All numbers will have a remainder when divided by $p$. That is the division theorem[1]. For all integers $m$ and all positive integer $p$ there is a unique $b$ and $r$ so that $m = r + bp; 0\le r < p$.

So let $a_0 = r$. And $m = a_0 + bp$.

Now take the $b$ and do the same thing. There are unique $c$ and $s$ so that $b = s + cp; 0\le s < p-1$. Let $a_1 = s$ and we have

$m = a_0 + bp = a_0 + (a_1 + cp)p = a_0 + a_1*p + cp^2$.

Now just repeat for $c$. $c = t + dp; 0\le t < p-1$ so $a_2 = t$ and

$m = a_0 + bp = a_0 + (a_1 + cp)p = a_0 + a_1*p + cp^2$

$= a_0 + a_1*p + (t+ dp)p^2 = a_0 + a_1*p + a_2p^2 + dp^3$

.... and keep going.

As $m$ is finite and the sum we are creating involves higher and higher powers of $p$ we'll have to eventually reach a highest power of $p$. So this must end sometime.

There's nothing magical about the number $10$ and we could use any number. So we could use a prime $p$.

This is called putting numbers in base $p$ and it is often basic education in grade school.

For example to convert $1235$ into base $7$ we find the remainder of $1235$ when divided by $7$.

$1235 = 3 + 7*176$. So $a_0 = 3$

Then we find the remainder of $176$. $176 = 1 + 25*7$ so $a_1 = 1$

Then we find the remainder of $25$. $25 = 4 + 3*7$ so $a_2 = 4$

Then we find the remainder of $3$. $3 = 3$ so $a_3 = 3$ and we are done.

So $1235 = 3413_7$ in base seven where

$3413_ 7 = 3 + 1*7 + 4*7^2 + 3*7^3$

$= 3 + 7(1 + 7(4 + 7(3))$

$= 3 + 7(1 + 7(25))$

$=3 + 7(176)$

$1235$

====

[1] Actually proving the division theorem--- that for all integers $m$ and positive integer $p$ there is are unique integers $b, r; 0 \le r < p-1$ so that $m = bp + r$--- is not trivial.

But I assume that is not the level of depth that was intended by the question.

Answer 2

In doubt, try induction.

For $m=1$, we can take $n=0$, $a_0=0$.

Assume $m=a_0+a_1p+a_2p^2+\ldots +a_np^n$. Wlog $a_n<p-1$ (or else append a summand $0\cdot p^{n+1}$ and increase $n$). Let $k=\min\{\,j\ge 0\mid a_j<p-1\,\}$ and then $$b_j=\begin{cases}0,&j<k\\ a_j+1,&j=k\\a_j,&j>k\end{cases} $$ Then the $0\le b_j\le p-1$ for all $j$ and one checks that $b_0+b_1p+\ldots +b_np^n=m+1$. Indeed, $$(b_0+b_0p+\ldots+b_np^n)-(a_0+a_0p+\ldots+a_np^n)\\=-(p-1)(1+p+\ldots+p^{k-1})+p^k=-(p^k-1)-p^k=1$$

Remark: nowhere did we use that $p$ is prime. Any integer $p\ge 2$ would do.