Tuesday, 9 July 2013

Help with a proof in modular arithmetic





Let a,b,nZ with n>0 and abmodn. Also, let c0,c1,,ckZ. Show that :



c0+c1a++ckakc0+c1b++ckbk(modn).



For the proof I tried :



a=b+ny for some yZ.



If I multiply from both side c1++ck I obtain :




c1a+c2a++cka=(c1b+c2b++ck)(b+ny).



However I can't prove that is true when I multiply by both side a1+a2++ak.


Answer



1) Prove that kakb(modn) for any integer k.



2) Show that by induction that means akbk(modn) for any natural k.



3) Show that if ab(modn) and ab(modn) that a+ab+b(modn).




4) Show your result follows by induction and combinition



....



Or. Note that akbk=(ab)(ak1+ak2b+....+abk2+bk1).



And that (c0+c1a+...+ckak)(c0+c1b+...+ckbk)=



c1(ab)+c2(a2b2)+......ck(akbk)=




.... And therefore......


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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