Let a,b,n∈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