Matematyka.pl

Dzień dobry wszystkim;) Muszę udowodnić pewien lemat poprzez indukcję, jednak szczerze mówiąc nie wiem jak się za niego zabrać. Może ma ktoś pomysł jak to zrobić?

Niech \(\displaystyle{ a,b,m,n}\) będą dodatnimi liczbami całkowitymi. Jeżeli \(\displaystyle{ a \equiv b \pmod{m^{n}}}\), to

\(\displaystyle{ a^{m^k}\equiv b^{m^k} \pmod{ m^{k+n}}}\)

Jedyna rzecz jaką do tej pory mam to:

\(\displaystyle{ a^{m^{k+1}}- b^{m^{k+1}}=(a^{m^k}-b^{m^k})[(a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}]}\)

Z góry dziękuję za wszelką pomoc

No, jeszcze tam baza indukcji, ale to akurat proste.

Z założenia indukcyjnego wiesz, że
\(\displaystyle{ a^{m^{k}}-b^{m^{k}}\equiv 0\pmod{m^{k+n}}}\)
Ponadto \(\displaystyle{ a\equiv b\pmod{m^n}}\), zatem
dla dowolnej stałej całkowitej dodatniej \(\displaystyle{ l}\) jest
\(\displaystyle{ a^l\equiv b^l\pmod{m^n}}\)
(potęgowanie kongruencji, to też można wykazać indukcyjnie, ale to raczej znane), stąd
\(\displaystyle{ (a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}\equiv mb^{m^k(m-1)}\pmod{m^n}}\),
w szczególności więc
\(\displaystyle{ (a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}\equiv 0\pmod{m}}\).
W związku z tym liczba
\(\displaystyle{ a^{m^{k+1}}- b^{m^{k+1}}=(a^{m^k}-b^{m^k})[(a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}]}\)
jest podzielna przez \(\displaystyle{ m^{k+n}\cdot m=m^{k+1+n}}\).

Dziękuję ślicznie!

Premislav pisze:No, jeszcze tam baza indukcji, ale to akurat proste.

Z założenia indukcyjnego wiesz, że
\(\displaystyle{ a^{m^{k}}-b^{m^{k}}\equiv 0\pmod{m^{k+n}}}\)
Ponadto \(\displaystyle{ a\equiv b\pmod{m^n}}\), zatem
dla dowolnej stałej całkowitej dodatniej \(\displaystyle{ l}\) jest
\(\displaystyle{ a^l\equiv b^l\pmod{m^n}}\)
(potęgowanie kongruencji, to też można wykazać indukcyjnie, ale to raczej znane), stąd
\(\displaystyle{ (a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}\equiv mb^{m^k(m-1)}\pmod{m^n}}\),
w szczególności więc
\(\displaystyle{ (a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}\equiv 0\pmod{m}}\).
W związku z tym liczba
\(\displaystyle{ a^{m^{k+1}}- b^{m^{k+1}}=(a^{m^k}-b^{m^k})[(a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}]}\)
jest podzielna przez \(\displaystyle{ m^{k+n}\cdot m=m^{k+1+n}}\).

-- 20 sie 2018, o 14:24 --

Może ktoś wie jak do tego doszło? Wcześniej nia miałam czasu posiedzieć nad tym dowodem i dopiero wczoraj znalazłam czas i mam jeszcze pewne problemy.

\(\displaystyle{ (a^{m^k})^{m-1} + (a^{m^k} )^{m-2}(b^{m^k})+\ldots + (b^{m^k}) ^{m-1}\equiv mb^{m^k(m-1)}\pmod{m^n}}\),-- 21 sie 2018, o 15:43 --

moniska281 pisze:Dziękuję ślicznie!