Let $a,b,n \in Z$ with $n > 0$ and $a \equiv b \mod n$. Also, let $c_0,c_1,\ldots,c_k \in Z$. Show that :
$c_0 + c_1a + \ldots + c_ka^k \equiv c_0 + c_1b + \ldots + c_kb^k \pmod n$.
For the proof I tried :
$a = b + ny$ for some $y \in Z$.
If I multiply from both side $c_1 + \ldots + c_k$ I obtain :
$c_1a + c_2a + \ldots + c_ka = (c_1b + c_2b + \ldots + c_k) (b + ny)$.
However I can't prove that is true when I multiply by both side $a^1 + a^2 + \ldots + a^k$.
Answer
1) Prove that $k*a \equiv k*b \pmod n$ for any integer $k$.
2) Show that by induction that means $a^k \equiv b^k \pmod n$ for any natural $k$.
3) Show that if $a\equiv b\pmod n$ and $a' \equiv b'\pmod n$ that $a+a'\equiv b +b' \pmod n$.
4) Show your result follows by induction and combinition
....
Or. Note that $a^k - b^k = (a-b)(a^{k-1}+a^{k-2}b + .... +ab^{k-2} + b^{k-1})$.
And that $(c_0 + c_1a + ... + c_ka^k) - (c_0 + c_1b + ... + c_kb^k)=$
$c_1(a-b) + c_2(a^2 - b^2) + ...... c_k(a^k - b^k) =$
.... And therefore......
No comments:
Post a Comment