Friday, June 24, 2016

Help with a proof in modular arithmetic




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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...