Matematyka.pl

stuuudentsss pisze: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}\),

No skąd! Podzielić \(\displaystyle{ a}\) i \(\displaystyle{ b}\) możesz tylko przez liczbę względnie pierwszą z \(\displaystyle{ c}\). Przecież \(\displaystyle{ 2\equiv 8\pmod{6}}\), ale gdybyś podzielił przez \(\displaystyle{ 2}\), to dostaniesz \(\displaystyle{ 1\equiv 4\pmod{6}}\), co zdecydowanie nie jest prawdą.

stuuudentsss pisze: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}\).

To jest prawdą. Ale w tej sytuacji (różnej od tej powyżej) musisz podzielić wszystkie trzy liczby \(\displaystyle{ a,b,c}\), żeby dostać poprawną kongruencję.

JK

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

Spostrzeżenie - uważam, że w liceum tak można.
Ostatnia cyfra z mnożenia 37 jest taka jak z mnożenia 7 :
\(\displaystyle{ 7^1=\red 7}\)
\(\displaystyle{ 7^2=4\red 9}\)
\(\displaystyle{ 7^3=34\red 3}\)
\(\displaystyle{ 7^4=...\red 1}\)
\(\displaystyle{ 7^5=...\red 7}\)
\(\displaystyle{ 7^6=...\red 9}\)[edit]piszę z tv. i na studiach \(\displaystyle{ (37^4)^{25}-(37^4)^5=}\)

Jan Kraszewski pisze: No skąd! Podzielić \(\displaystyle{ a}\) i \(\displaystyle{ b}\) możesz tylko przez liczbę względnie pierwszą z \(\displaystyle{ c}\). Przecież \(\displaystyle{ 2\equiv 8\pmod{6}}\), ale gdybyś podzielił przez \(\displaystyle{ 2}\), to dostaniesz \(\displaystyle{ 1\equiv 4\pmod{6}}\), co zdecydowanie nie jest prawdą.

Czyli liczba względnie pierwsza z \(\displaystyle{ 6}\) to np. \(\displaystyle{ 1}\) albo \(\displaystyle{ 15}\) z tym, że przez \(\displaystyle{ 15}\) to nie ma sensu, więc mogę podzielić przez \(\displaystyle{ 1}\) ale to nie ma też sensu bo nic to nie zmieni.
A przez \(\displaystyle{ 2}\) mogę podzielić \(\displaystyle{ a,b}\) i \(\displaystyle{ c}\) bo \(\displaystyle{ NWD(2,8,6)}\) to \(\displaystyle{ 2}\)-- 20 maja 2018, o 20:53 --Czy teraz dobrze rozumiem? i na tym to polega?

stuuudentsss pisze:Czyli liczba względnie pierwsza z \(\displaystyle{ 6}\) to np. \(\displaystyle{ 1}\) albo \(\displaystyle{ 15}\)

No skąd, \(\displaystyle{ NWD(6,15)=3}\).

stuuudentsss pisze:A przez \(\displaystyle{ 2}\) mogę podzielić \(\displaystyle{ a,b}\) i \(\displaystyle{ c}\) bo \(\displaystyle{ NWD(2,8,6)}\) to \(\displaystyle{ 2}\)

Tak i dostaniesz prawdziwą kongruencję \(\displaystyle{ 1\equiv 4\pmod{3}}\).

stuuudentsss pisze:Czy teraz dobrze rozumiem? i na tym to polega?

Moim zdaniem zamiast zapamiętywać różne takie reguły warto zrozumieć metody ich dowodzenia - wtedy można samemu sprawdzić, czy dana reguła jest prawdziwa.

JK

Jan Kraszewski, tak, masz rację mój błąd. No to np \(\displaystyle{ 13}\) jest względnie pierwsza z \(\displaystyle{ 6}\), ale podzielić ją przez \(\displaystyle{ a}\) i \(\displaystyle{ b}\) to się nie da, bo wyjdą ułamki, a ułamków nie można chyba, tak?

Nie można. Tu wszystko dzieje się w liczbach całkowitych, więc możesz dzielić \(\displaystyle{ a}\) i \(\displaystyle{ b}\) przez ich dowolny wspólny dzielnik, który jest względnie pierwszy z \(\displaystyle{ c}\).

JK

A czy wszystkie zadania z wykazaniem podzielności da się rozwiązać za pomocą kongruencji?
Np. czy takie zadanie się da: \(\displaystyle{ 19|3^{18} - 2^{18}}\). Jak tak to w jaki sposób, bo tutaj mamy różne podstawy.

To zadanie to klasyczne zadanie na różnicę potęg:

\(\displaystyle{ 3^{18} - 2^{18}=\left( 3^3\right) ^{6} - \left( 2^3\right) ^{6}=\left( 3^3-2^3\right)\cdot\mbox{coś tam}=...}\)

JK

Tak, wiem ale czy można rozwiązać to właśnie kongrunecją i czy są jakieś wymagania co do przykładu aby można było go rozwiązać kongruencją.
Również słyszałem o metodzie z wykorzystaniem małego twierdzenia Fermata.

Możesz go rozwiązać kongruencją, ale to jest dokładnie to samo rozwiązanie, co z różnicą potęg, tylko zapisane w innym języku:

\(\displaystyle{ 3^3\equiv 2^3\pmod{19}\\
\left( 3^3\right)^6 \equiv \left( 2^3\right)^6 \pmod{19}\\
3^{18}\equiv 2^{18}\pmod{19}\\
3^{18}- 2^{18}\equiv 0\pmod{19}}\)

JK

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

rozwijając trochę Twoje pytanie - tak możesz podzielić, a raczej pomnożyć przez element odwrotny \(\displaystyle{ 7}\) z pierścienia reszt \(\displaystyle{ \mathbb{Z}_{15}}\)

edit: Ale nie w taki sposób jaki został pokazany byłoby tak: oznaczam element odwrotny jako \(\displaystyle{ 7^{-1}}\) (to nie jest \(\displaystyle{ \frac{1}{7}}\)) i mnożę :
\(\displaystyle{ 7\cdot7^{-1}x\equiv 21\cdot 7^{-1}\pmod{15} \Rightarrow x\equiv 21\cdot 7^{-1}\pmod{15}}\)

\(\displaystyle{ 7^{-1}}\) to w naszym przypadku 13

rubiccube, jedyny problem z tym wytłumaczeniem jest taki, że napis \(\displaystyle{ 21\cdot 7^{-1}}\) jest mocno nieszczęśliwy - \(\displaystyle{ 7^{-1}}\) jest w \(\displaystyle{ \mathbb{Z}_{15}}\), podczas gdy \(\displaystyle{ 21\notin \mathbb{Z}_{15}}\)...

JK

Jan Kraszewski pisze:rubiccube, jedyny problem z tym wytłumaczeniem jest taki, że napis \(\displaystyle{ 21\cdot 7^{-1}}\) jest mocno nieszczęśliwy - \(\displaystyle{ 7^{-1}}\) jest w \(\displaystyle{ \mathbb{Z}_{15}}\), podczas gdy \(\displaystyle{ 21\notin \mathbb{Z}_{15}}\)...

JK

no tak, mea culpa.
\(\displaystyle{ 21\pmod{15} \equiv 6\pmod{15}}\)