# Congruence Modulo Power of p as Linear Combination of Congruences Modulo p

## Theorem

Let $p$ be a prime number.

Let $S = \set {a_1, a_2, \ldots, a_p}$ be a complete residue system modulo $p$.

Then for all integers $n \in \Z$ and non-negative integer $s \in \Z_{\ge 0}$, there exists a congruence of the form:

$n \equiv \displaystyle \sum_{j \mathop = 0}^s b_j p^j \pmod {p^{s + 1} }$

where $b_j \in S$.

## Proof

Proof by induction on $s$:

### Basis for the Induction

For $s = 0$, we apply the definition of a complete residue system modulo $p$:

$\forall n \in \Z: \exists a_i \in S: n \equiv a_i \pmod p$

This is our base case.

### Induction Hypothesis

This is our induction hypothesis:

For some $k \in \Z_{\ge 0}$, for all integers $n \in \Z$, there exists a congruence of the form:
$n \equiv \displaystyle \sum_{j \mathop = 0}^k b_j p^j \pmod {p^{k + 1} }$

It is to be demonstrated that:

For all integers $n \in \Z$, there exists a congruence of the form:
$n \equiv \displaystyle \sum_{j \mathop = 0}^{k + 1} b_j p^j \pmod {p^{k + 2} }$

### Induction Step

This is our induction step:

From $n \equiv \displaystyle \sum_{j \mathop = 0}^k b_j p^j \pmod {p^{k + 1} }$ we have:

$\exists q \in \Z: n = \displaystyle \sum_{j \mathop = 0}^k b_j p^j + q p^{k + 1}$

From the definition of a complete residue system modulo $p$:

$\exists a_i \in S: q \equiv a_i \pmod p$

This gives:

$\exists r \in \Z: q = a_i + r p$

Substituting this to the original equation we have:

 $\displaystyle n$ $=$ $\displaystyle \sum_{j \mathop = 0}^k b_j p^j + \paren {a_i + r p} p^{k + 1}$ $\displaystyle$ $=$ $\displaystyle a_i p^{k + 1} + \sum_{j \mathop = 0}^k b_j p^j + r p^{k + 2}$ $\displaystyle$ $\equiv$ $\displaystyle a_i p^{k + 1} + \sum_{j \mathop = 0}^k b_j p^j$ $\displaystyle \pmod {p^{k + 2} }$

This shows that $n$ can be expressed as the form:

$n \equiv \displaystyle \sum_{j \mathop = 0}^{k + 1} b_j p^j \pmod {p^{k + 2} }$

By the Principle of Mathematical Induction, the theorem is true for any $s$.

Note that in the proof above, we did not use the fact that $p$ is a prime number.

$\blacksquare$