Wykazanie podzielności

[stuuudentsss]

Cześć,
w jaki sposób mogę wykazać, że: \(\displaystyle{ 10|37^{100} - 37^{20}}\) ?

[Premislav]

Ponieważ \(\displaystyle{ 37=4\cdot 10-3}\), więc
\(\displaystyle{ 37^4\equiv (-3)^4\pmod{10}}\), czyli \(\displaystyle{ 37^4\equiv 1\pmod{10}}\).
Stąd też łatwo udowodnić, że dla dowolnego \(\displaystyle{ k\in \NN}\) jest
\(\displaystyle{ 37^{4k}\equiv 1\pmod{10}}\) (np. po prostu zapisując \(\displaystyle{ 37^{4k}=(37^4)^k}\)).
W szczególności \(\displaystyle{ 37^{100}\equiv 1\pmod{10}}\) oraz \(\displaystyle{ 37^{20}\equiv 1\pmod{10}}\).
Zatem oczywiście \(\displaystyle{ 37^{100}-37^{20}\equiv 0\pmod{10}}\).

[piasek101]

W liceum - ustalić jaką ostatnią cyfrę ma odjemna, a jaką odjemnik.

[Janusz Tracz]

Albo tak, z różnicy \(\displaystyle{ n}\) tych potęg:

\(\displaystyle{ 37^{100}-37^{20}=\left( 37^{5}\right)^{20}-37^{20}=\left( 37^5-37\right)\left( \left( 37^{5}\right)^{19}+\left( 37^{5}\right)^{18} \cdot 37+...\right)}\)

Wystarczy teraz pokazać że \(\displaystyle{ 10 \mid 37^5-37}\) a tak jest bo:

\(\displaystyle{ 37^5-37=37{\red{(37^2+1)}}(37^2-1)=37 \cdot {\red{1370}} \cdot (37^2-1)}\)

co kończy dowód.

[stuuudentsss]

Premislav, twój pomysł na rozwiązanie tego kongruencją o ile to kongruencja, wydaje się chyba najprostszy, mógłbyś mi wytłumaczyć krok po kroku jak to zrobiłeś?
Ogólnie to miałem już kongruencję, mógłbyś mi napisać, jakie ma ona własności i jakie działania możemy dzięki niej wykonywać, tylko tak po chłopsku Bo np. dzielenie to możemy tylko dzielić przez nwd?

piasek101, możesz bardziej rozszerzyć Twoją myśl?

Janusz Tracz, dużo kombinowania tutaj xd

[Premislav]

Skoro \(\displaystyle{ 37=4\cdot 10-3}\), to \(\displaystyle{ 37\equiv -3\pmod{10}}\). Kongruencje możemy potęgować stronami, stąd \(\displaystyle{ 37^4\equiv (-3)^4\pmod{10}}\). Kongruencje są przechodnie, tj.
\(\displaystyle{ (a\equiv b\pmod{c} \wedge b\equiv d\pmod{c}) \Rightarrow a\equiv d\pmod{c}}\),
no i mamy \(\displaystyle{ (-3)^4=81\equiv 1\pmod{10}}\) (bo po prostu \(\displaystyle{ 81=8\cdot 10+1}\)), stąd i z tej przechodniości
\(\displaystyle{ 37^4\equiv 1\pmod{10}}\).
Skoro kongruencje możemy potęgować stronami (wykładnikiem naturalnym oczywiście), to stąd \(\displaystyle{ 37^{4k}\equiv 1\pmod{10}}\) dla każdego \(\displaystyle{ k}\) naturalnego.
No i podstawowa sprawa, \(\displaystyle{ a\equiv b\pmod{c} \Leftrightarrow c \text{ dzieli } a-b}\).

Tak, a co do dzielenia kongruencji, to tylko możemy przez coś, co dzieli \(\displaystyle{ \NWD}\), tj. jeśli
\(\displaystyle{ a\equiv b\pmod{c}}\)
i liczba \(\displaystyle{ d}\) dzieli wszystkie liczby \(\displaystyle{ a,b,c}\), to
możemy wnioskować, że \(\displaystyle{ \frac{a}{d}\equiv \frac b d \pmod{ \frac c d }}\)
Natomiast mnożyć możemy bez problemu.-- 20 maja 2018, o 14:37 --A co do ostatniej cyfry, dowód takich obserwacji wymaga indukcji, kongruencji lub wzoru dwumianowego Newtona, bez tego jest to tylko spostrzeżenie, a nie uzasadnienie.

[stuuudentsss]

Premislav, czyli jak NWD wyjdzie 8 to nie możemy podzielić przez 4 tylko przez 8 i wieksze liczby ktore dzielą 8?
A można dzielić tylko liczby a i b?

[Premislav]

Oj nie nie nie, jeśli \(\displaystyle{ \NWD(a,b,c)=8}\), to możemy dzielić kongruencję \(\displaystyle{ a\equiv b\pmod{c}}\) tylko przez dzielniki tego \(\displaystyle{ \NWD}\), tj. tylko przez \(\displaystyle{ 2,4,8}\). Coś, co dzieli \(\displaystyle{ \NWD}\) to inaczej dzielnik \(\displaystyle{ \NWD}\), trochę niefortunne zdanie mi poprzednio wyszło.

[stuuudentsss]

Ok. A z tego co słyszałem, aby można było w ogóle użyć kongruencji to NWD(a,c) musi dzielić się przez b? tak?
A mogę dzielić tylko "a" i "b", a "c" pozostawić bez zmian? bo np przy mnożeniu tak można.
I czy przy mnożeniu "c" pozostawiam bez zmian?

[Premislav]

Nie przywiązuj się za bardzo do tych oznaczeń.
Tak, przy mnożeniu to, co oznaczyłem jako \(\displaystyle{ c}\) zostaje bez zmian.

A z tego co słyszałem, aby można było w ogóle użyć kongruencji to \(\displaystyle{ NWD(a,c)}\) musi dzielić się przez \(\displaystyle{ b}\)?

Po prostu kongruencja \(\displaystyle{ a\equiv b\pmod{c}}\) gdy \(\displaystyle{ \NWD(a,c)\nmid b}\) jest sprzeczna, bo oznacza istnienie takiego \(\displaystyle{ k}\) całkowitego, że \(\displaystyle{ a=c\cdot k+b}\), czyli \(\displaystyle{ b=a-c\cdot k}\), ale jeśli \(\displaystyle{ \NWD(a,c)}\) nie dzieli \(\displaystyle{ b}\), to prawa strona dzieli się przez \(\displaystyle{ \NWD(a,c)}\), a lewa nie, co prowadzi do sprzeczności.
Ale generalnie jakiś przeciętny głupek na forum matematycznym to kiepskie źródło informacji, jeśli chcesz się tego porządnie nauczyć, to zajrzyj np. do książki Sierpińskiego poświęconej teorii liczb lub np. spróbuj sobie wyszukać w necie „kongruencje pdf". No albo zerknij jaką masz podaną literaturę z wykładu, czasem się da w sieci wykopać.

[stuuudentsss]

A jeżeli mam np. taka kongruencje:
\(\displaystyle{ 7x\equiv 21\pmod{15}}\) to wtedy mogę podzielić przez \(\displaystyle{ 7}\)?

[Jan Kraszewski]

A jak myślisz?

JK

[stuuudentsss]

Ja myślę, że nie bo \(\displaystyle{ NWD(7,21,15)}\) liczb to \(\displaystyle{ 1}\) a \(\displaystyle{ 1}\) nie dzieli się przez \(\displaystyle{ 21}\), a po drugie \(\displaystyle{ 15}\) nie dzieli sie przez \(\displaystyle{ 7}\).

[Jan Kraszewski]

Oj, nie rozumiesz tych kongruencji...

Kongruencja \(\displaystyle{ 7x\equiv 21\pmod{15}}\) oznacza, że \(\displaystyle{ 15\mid (7x-21)}\), czyli \(\displaystyle{ 15\mid 7(x-3)}\). Teraz używasz jednego z podstawowych twierdzeń arytmetyki, które mówi, że jeśli \(\displaystyle{ a\mid bc}\) i \(\displaystyle{ NWD(a,b)=1}\), to \(\displaystyle{ a\mid c}\). Ponieważ \(\displaystyle{ NWD(7,15)=1}\), więc \(\displaystyle{ 15\mid (x-3)}\), czyli \(\displaystyle{ x\equiv 3\pmod{15}}\). Czyli można podzielić.

JK

[stuuudentsss]

Jan Kraszewski, mój błąd bo \(\displaystyle{ 1}\) dzieli \(\displaystyle{ 15}\). Czyli możemy sobie przez co bądź podzielić \(\displaystyle{ a}\) i \(\displaystyle{ b}\), w sensie przez dzielniki tylko tych liczb, ale nie ruszając \(\displaystyle{ c}\), ale możemy też podzielić \(\displaystyle{ a,b,c}\), z tym, że \(\displaystyle{ \NWD(a,b,c)=d}\), to możemy dzielić kongruencję \(\displaystyle{ a\equiv b\pmod{c}}\) tylko przez dzielniki tego \(\displaystyle{ d}\). Czy dalej źle rozumiem.-- 20 maja 2018, o 20:24 --czyli już \(\displaystyle{ 4x\equiv 6\pmod{7}}\) tutaj bym nie mógł podzielić przez [/latex]2[/latex] i w sumie by to sensu nie miało, bo tutaj lepiej pomnożyć przez \(\displaystyle{ 2}\)