# Complete System Residue problem

I have to proof that given a complete system residue modulo $k$ ( $k$ is prime ) { $a_1, a_2, a_3, \ldots a_k$ } that, for every integer $n$ there exists s such that: $n \equiv \sum\limits_{i=0}^s b_ik^i \pmod{k^{s+1}}$

Where $b_i$ is one of the $a_i$.

I need a hint from where to start.

• Hint: induction on $s$. – Erick Wong Jan 14 '14 at 23:27
• Do you want to show that this is true for every integer $s\ge0$? – user84413 Jan 14 '14 at 23:33
• I've tried induction on s, I'll investigate more. Yes for all s >= 0 – user2232305 Jan 15 '14 at 11:58

Actually there definitely exists such $s$: let $s=0, b_i=a_i$, then according to the definition of complete system residue, any integer $n$ satisfies at least one of the $k$: $$n \equiv b_i \pmod k$$

You may try to expand this by assuming your statement is true when $s=s_0$, and consider $s=s_0+1$

I think I have proved it, here's my proof:

For $s = 0$. we have $n \equiv a_i \pmod{k}$, since the set ${ a_1, a_2,..., a_k}$ is a complete residue system modulo k.

We assume that the congruence holds for $s = s_0$.

For $s = s_0 + 1$. For every $n$ ( n in an integer ) we have: $n \equiv \sum\limits_{i=0}^s b_ik^i \pmod{k^{s+1}}$
So, $n + a_jk^{s+1} \equiv \sum\limits_{i=0}^s b_ik^i + a_jk^{s+1}\pmod{k^{s+1}}$
And, $a_jk^{s+1} \equiv 0 \pmod{k^{s+1}}$

Thus, $n \equiv \sum\limits_{i=0}^{s+1} b_ik^i \pmod{k^{s+1}}$
With, $k^{s+1} < k^{s+2}$ we can say that:
$n \equiv \sum\limits_{i=0}^{s+1} b_ik^i \pmod{k^{s+2}}$