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.

  • 1
    $\begingroup$ Hint: induction on $s$. $\endgroup$ – Erick Wong Jan 14 '14 at 23:27
  • 2
    $\begingroup$ Do you want to show that this is true for every integer $s\ge0$? $\endgroup$ – user84413 Jan 14 '14 at 23:33
  • $\begingroup$ I've tried induction on s, I'll investigate more. Yes for all s >= 0 $\endgroup$ – 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}}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.