# Leigh.Samphier/Sandbox/Canonical P-adic Expansion of Rational is Eventually Periodic/Lemma 1

Jump to navigation Jump to search

## Theorem

Let $p$ be a prime number.

Let $b \in \Z_{> 0}$:

$b, p$ are coprime

Let $a \in \Z$.

Then:

$\forall n \in \N: \exists A_n, r_n \in \Z$ :
$(1) \quad \dfrac a b = A_n + p^{n+1} \dfrac {r_n} b$
$(2) \quad 0 \le A_n \le p^{n+1} - 1$
$(3) \quad \dfrac {a - \paren{p^{n+1} - 1} b } {p^{n+1}} \le r_n \le \dfrac a {p^{n+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$

Let $x_n$ be the multiple of $p^n$:

$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 r_n$ $=$ $\ds \dfrac {a - A_n b} {p^{n+1} }$ Rearranging terms

We have:

 $\ds$  $\ds 0 \le A_n \le p^{n+1} - 1$ $\ds$ $\leadsto$ $\ds - \paren{p^{n+1} - 1} \le - A_n \le 0$ $\ds$ $\leadsto$ $\ds - \paren{p^{n+1} - 1} b \le - A_n b \le 0$ $\ds$ $\leadsto$ $\ds a - \paren{p^{n+1} - 1} b \le a - A_n b \le a$ $\ds$ $\leadsto$ $\ds \dfrac {a - \paren{p^{n+1} - 1} b} {p^{n+1} } \le \dfrac {a - A_n b} {p^{n+1} } \le \dfrac a {p^n}$ $\ds$ $\leadsto$ $\ds \dfrac {a - \paren{p^{n+1} - 1} b} {p^{n+1} } \le r_n \le \dfrac a {p^{n+1} }$

The result follows.

$\blacksquare$