# Canonical P-adic Expansion of Rational is Eventually Periodic/Lemma 1

## Theorem

Let $p$ be a prime number.

Let $b \in \Z_{>0}$ such that $b$ and $p$ are coprime.

Let $a \in \Z$.

Then:

$\forall n \in \N: \exists r_n \in \Z : \dfrac a b - \paren{p^{n + 1} \dfrac {r_n} b} \in \set{0, 1, \ldots, p^{n + 1} - 1}$

## Proof

Let $n \in \N$.

$b, p^{n + 1}$ are coprime
$\exists c_n, d_n \in \Z : c_n b + d_n p^{n + 1} = 1$

Multiplying both sides by $a$:

$a = a c_n b + a d_n p^{n + 1}$

Let $A_n$ be the least positive residue of $a c_n \pmod {p^{n + 1} }$.

By definition of least positive residue:

$0 \le A_n \le p^{n + 1} - 1$
$p^{n + 1} \divides \paren{a c_n - A_n}$

By definition of divisor:

$\exists x_n \in \Z : x_n p^{n + 1} = a c_n - A_n$

Re-arranging terms:

$a c_n = x_n p^{n + 1} + A_n$

We have:

 $\ds a$ $=$ $\ds \paren {x_n p^{n + 1} + A_n} b + a d_n p^{n + 1}$ $\ds$ $=$ $\ds A_n b + \paren {b x_n + a d_n} p^{n + 1}$ Rearranging terms

Let $r_n = b x_n + a d_n$.

Then:

 $\ds a$ $=$ $\ds A_n b + r_n p^{n + 1}$ $\ds \leadsto \ \$ $\ds \dfrac a b$ $=$ $\ds A_n + p^{n + 1} \dfrac {r_n} b$ dividing both sides by $b$ $\ds \leadsto \ \$ $\ds A_n$ $=$ $\ds \dfrac a b - \paren{p^{n + 1} \dfrac {r_n} b}$ rearranging terms

By definition of least positive residue:

$A_n \in \set{0, 1, \ldots, p^{n + 1} - 1}$

The result follows.

$\blacksquare$