Monday, 23 June 2014

Help with a proof in modular arithmetic




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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...