Matematyka.pl

Witam

Chodzę sobie do szkoły i akurat nam gdzieś tam przewija się podzielność liczb.
Okazało się że nie pamiętam kiedy liczba jest podzielna przez daną liczbę.
Po krótkim filozofowaniu pomyślałem sobie że jest napisane kiedy liczba jest podzielna przez co najwyzęj \(\displaystyle{ 11}\) i fajnie byłoby wiedzieć skąd to się wzieło bo może da się wyprowadzić cechy podzielności dla dowolnej liczby większej niż \(\displaystyle{ 11}\).

W trakcie wędrówki po bezłączach sieci onalazłem taką stronę:


Cieszyłem się krótką chwilę a potem zobaczyłem coś o nazwie KONGURENCJA - niestety tego w książce z matmy się nie zobaczy więc nie pozostaje nic innego jak zakasać rękawy i samemu się dowiedzieć óż to znaczy.
Próbowałem to ogarnąć bez zagłębiania się w kongurencje ale nie pstrykło.

Oto wyniki moich poszukiwań i kilka pytań - potrzebuję żebyście mnie upewnili czy dobrze to rozumiem.
==================================
Kongurencja to taka operacja czy działanie którym badamy czy dwie liczby \(\displaystyle{ a}\) i \(\displaystyle{ b}\) podzielone przez podzielone prz liczbe trzecią \(\displaystyle{ m}\) dadzą taką samą resztę z dzielenia.
Jeżeli tak się dzieje mówimy o liczbach że przystają do siebie.
NP Liczba \(\displaystyle{ 100}\) przystaje do \(\displaystyle{ 1000 \pmod{10}}\) bo \(\displaystyle{ 100 : 10}\) daje resztę z dzielenia \(\displaystyle{ 0}\) i \(\displaystyle{ 1000 : 10}\) daje resztę z dzielenia \(\displaystyle{ 0}\).
Myślę że tu błędu nie popełniłem.


Teraz własności (serio są tylko trzy?) opisane na tej stornie.

"- zwrotność - dla dowolnej liczby całkowitej \(\displaystyle{ a}\) zachodzi \(\displaystyle{ a\equiv a\pmod{m}}\)."
Jak rozumiem - każda liczba przystaje do siebie samej. Dobrze rozumiem zapis?

"- symetryczność - kongruencja \(\displaystyle{ a\equiv b\pmod{m}}\) pociąga za sobą kongruencję \(\displaystyle{ b\equiv a\pmod{m}}\)."
Jeżeli \(\displaystyle{ 100}\) przystaje do \(\displaystyle{ 1000}\) to \(\displaystyle{ 1000}\) przystaje do \(\displaystyle{ 100}\)?

"- przechodniość - z kongruencji \(\displaystyle{ a\equiv b\pmod{m}}\) i \(\displaystyle{ b\equiv c\pmod{m}}\) wynika zawsze kongruencja \(\displaystyle{ a\equiv c\pmod{m}}\)."
Rozumiem to tak: \(\displaystyle{ 10\equiv 100\pmod{10}}\) i \(\displaystyle{ 100\equiv 1000\pmod{10}}\) więc \(\displaystyle{ 10\equiv 1000\pmod{10}}\) - czy dobrze?

Teraz ta trudna dla mnie część - wzory
Dodawanie i odejmowanie i mnożenie jestem w stanie tymczasowo przyjąć na wiarę lecz ubolewam nad brakiem dowodu.

Potem jest napisane:
"Można także przenosić wyrazy z jednej strony kongruencji na drugą, zmieniając ich znaki. Obie strony kongruencji można podnosić do tej samej potęgi o wykładniku naturalnym, tzn. z kongruencji \(\displaystyle{ a\equiv b\pmod{m}}\) wynika kongruencja \(\displaystyle{ a^n\equiv b^n\pmod{m}}\). W kongruencji mamy prawo zastąpić dany składnik lub czynnik przez inny przystający modulo \(\displaystyle{ m}\). Ostatnia własność jest często wykorzystywana do dowodzenia twierdzeń lub bardzo pomocna przy rozwiązywaniu zadań. "
Nic nie rozumiem czy może ktoś napisac po jednym przykładzie tej operacji - byłbym wdzięczny:)

Pozdrawiam

Najpierw wprowadźmy sobie podzielność liczb (nie mylić z dzieleniem). Dwie liczby całkowite \(\displaystyle{ a, b}\) są podzielne, gdy istnieje taka liczba całkowita \(\displaystyle{ k}\), że \(\displaystyle{ a = k \cdot b}\).

Przykład:
Czy \(\displaystyle{ 25}\) jest podzielne przez \(\displaystyle{ 5}\)?

\(\displaystyle{ 25 = 5k}\)

Liczymy \(\displaystyle{ k}\), jeżeli jest liczbą całkowitą, to znaczy, że te dwie liczby są podzielne.

\(\displaystyle{ k = \frac{25}{5} = 5}\). Czyli te dwie liczby są podzielne.

Podzielność określa nam, że pewna liczb "mieści się" w drugiej ileś razy. W ogólności \(\displaystyle{ b}\) "mieści się" w \(\displaystyle{ a}\), \(\displaystyle{ k}\) razy. W naszym przypadku: \(\displaystyle{ 5}\) mieści się w \(\displaystyle{ 25}\) dokładnie \(\displaystyle{ 5}\) razy.
Możemy powiedzieć, że \(\displaystyle{ 5}\) dzieli \(\displaystyle{ 25}\).


Kongruencja!

Z definicji wynika, że:
\(\displaystyle{ a\equiv b\pmod m}\) jeśli \(\displaystyle{ m}\) dzieli \(\displaystyle{ a - b}\).

Przykład:

\(\displaystyle{ 15\equiv 1\pmod 2}\) czyli \(\displaystyle{ 2}\) dzieli \(\displaystyle{ 15-1}\). Faktycznie: \(\displaystyle{ 14 = 2k}\), dla \(\displaystyle{ k = 7 \in \ZZ}\).
Więc kongruencja zachodzi.
Mówimy, że liczba \(\displaystyle{ 15}\) przystaje modulo \(\displaystyle{ 2}\) do liczby \(\displaystyle{ 1}\).

Przystawanie jest pewną relacją, nie zagłębiając się w to czym jest relacja, ma ono pewne własności. Pytasz się czy tylko trzy? Znajdziemy inne własności, ale te trzy mówią nam, że relacja ta jest relacją równoważności, co niesie za sobą wiele konsekwencji. No, ale ja może wyjaśnię po prostu co to znaczy, że ta relacja jest:

a) Zwrotna:
To znaczy tyle, że liczba jest w relacji z samą sobą. Na przykład:
\(\displaystyle{ 4\equiv 4\pmod x}\) cztery przystaje modulo \(\displaystyle{ x}\) do \(\displaystyle{ 4}\) i faktycznie \(\displaystyle{ x}\) dzieli \(\displaystyle{ 4-4 = 0}\), bo \(\displaystyle{ 0 = kx}\), dla \(\displaystyle{ k = 0 \in \ZZ}\).

b) Symetryczna:
Jeżeli \(\displaystyle{ a\equiv b\pmod c}\), to \(\displaystyle{ b\equiv a\pmod c}\)
Czyli jeśli \(\displaystyle{ c}\) dzieli \(\displaystyle{ a-b}\), to \(\displaystyle{ c}\) dzieli \(\displaystyle{ b-a}\)
Na przykład:
Jeżeli \(\displaystyle{ 12\equiv 4 \pmod 2}\), to \(\displaystyle{ 4\equiv 12\pmod 2}\)
czyli sprawdzamy, czy pierwszy warunek jest spełniony: \(\displaystyle{ 2}\) dzieli \(\displaystyle{ 12 - 4}\)? Tak, \(\displaystyle{ 2}\) dzieli \(\displaystyle{ 8}\), więc wiemy, że \(\displaystyle{ 2}\) dzieli \(\displaystyle{ 4 - 12}\).
Faktycznie tak jest, bo \(\displaystyle{ 2}\) dzieli \(\displaystyle{ -8}\), bo \(\displaystyle{ -8 = 2k}\), dla \(\displaystyle{ k = -4 \in \ZZ}\)

c) Przechodnia:
Jeżeli \(\displaystyle{ a\equiv b\pmod c}\) i równocześnie \(\displaystyle{ b\equiv d\pmod c}\), to \(\displaystyle{ a\equiv d\pmod c}\).

Żeby lepiej zrozumieć o co tu chodzi oderwijmy się na chwilę od relacji przystawania modulo i zajmijmy się relacją równości. Znasz ją doskonale liczby są w relacji równości jeżeli są równe, relacje zapisujemy tak: \(\displaystyle{ =}\)
Na przykład: \(\displaystyle{ 5 = 5}\), więc \(\displaystyle{ 5}\) jest w relacji równości z \(\displaystyle{ 5}\). Tak się składa, że ta relacja też jest przechodnia.
czyli jeżeli \(\displaystyle{ a = b}\) i \(\displaystyle{ b = c}\), to \(\displaystyle{ a = c}\)
\(\displaystyle{ \frac{1}{2} = \frac{2}{4}}\) i \(\displaystyle{ \frac{2}{4} = \frac{3}{6}}\), to \(\displaystyle{ \frac{1}{2} = \frac{3}{6}}\)

Podobnie jest z relacją mniejszości \(\displaystyle{ <}\)
jeżeli \(\displaystyle{ a < b}\) i \(\displaystyle{ b < c}\), to \(\displaystyle{ a < c}\)
\(\displaystyle{ 2 < 4}\) i \(\displaystyle{ 4 < 5}\), to \(\displaystyle{ 2 < 5}\)

Wróćmy do naszej relacji \(\displaystyle{ \equiv}\) ona też jest przechodnia.

Jeżeli \(\displaystyle{ a\equiv b\pmod c}\) i równocześnie \(\displaystyle{ b\equiv d\pmod c}\), to \(\displaystyle{ a\equiv d\pmod c}\).

Podstaw sobie liczby i sprawdź, że działa również dla nich.



Cechy podzielności!

Jeżeli chcesz zrozumieć dowody, to musisz dobrze zrozumieć jak działa system dziesiątkowy. Czego tam się o nim doczytałeś?

"Jeżeli chcesz zrozumieć dowody, to musisz dobrze zrozumieć jak działa system dziesiątkowy. Czego tam się o nim doczytałeś?"

Umiem przeliczać te systemy miedzy sobą (dwójkowy <-> ósemkowy <-> dziesiętny <-> szesnatkowy)
Przeliczam liczby schematem pokazanym na lekcji (I klasa techniikum) ale to tylko odtwarzanie schematu.

My ludzi korzystamy z dziesiętnego a komputery z dwójkowego.
Wiem że każdą kazðą liczbę w systemie dziesiętnym można zapisac w postaci wielomianu(<- wielomianu prawda?)
w sensie można zapisać jako cyfrę pomnożoną przez 10 do n-tej potęgi gdzie n to pozycja tej cyfry w "liczbie".



PS: Chodzi ci o wszelkie dowody czy tylko te dotyczące podzielności?:)

MrSilnia pisze: My ludzi korzystamy z dziesiętnego a komputery z dwójkowego.

Teraz zwykle tak jest, jednak historia zna przypadki gdzie różne plemiona korzystały czy to z systemu dwójkowego, czy to dwudziestkowego.
Dwójkowy został w komputerach, bo to ułatwia nam życie. No, ale nie o tym...

MrSilnia pisze: My ludzi korzystamy z dziesiętnego a komputery z dwójkowego.
Wiem że każdą kazðą liczbę w systemie dziesiętnym można zapisac w postaci wielomianu(<- wielomianu prawda?)
w sensie można zapisać jako cyfrę pomnożoną przez 10 do n-tej potęgi gdzie n to pozycja tej cyfry w "liczbie".

Tak, to prawda.

W systemie dziesiętnym mamy dziesięć (a jakże) cyfr: \(\displaystyle{ \left\{ 0,1,2,3,4,5,6,7,8,9\right\}}\) i one składają się na liczy w taki właśnie sposób.

Najmniejszą liczbą, którą możemy przedstawić w postaci wielomianu jest \(\displaystyle{ 10}\).
\(\displaystyle{ 10 = 1 \cdot 10^1 + 0 \cdot 10^0}\)
Po co to robić tak trudno, dziwnie jakoś? (wyjaśni się później, ale na razie...)

Dajmy na to liczbę: \(\displaystyle{ 6547928 = 6 \cdot 10^6 + 5 \cdot 10^5 + 4 \cdot 10^4 + 7 \cdot 10^3 + 9 \cdot 10^2 + 2 \cdot 10^1 + 8 \cdot 10^0}\)

UWAGA!
Przypominam, że \(\displaystyle{ 10^0 = 1}\).

No i to jest właśnie wielomian. Pytanie do Ciebie: jak możemy to zapisać w ogólności? (widziałeś na pewno ten zapis jak czytałeś o podzielności i systemach liczbowych).-- 14 lut 2018, o 04:34 --

MrSilnia pisze: Teraz ta trudna dla mnie część - wzory
Dodawanie i odejmowanie i mnożenie jestem w stanie tymczasowo przyjąć na wiarę lecz ubolewam nad brakiem dowodu.

Te działania, ale na czym? Możesz sb odjąć od każdej strony, dodać liczby o ile masz to samo modulo, to kongruencja będzie dalej zachodziła, bo skoro \(\displaystyle{ a\equiv b\pmod m}\)
czyli \(\displaystyle{ m}\) dzieli \(\displaystyle{ a-b}\), to tak samo \(\displaystyle{ m}\) dzieli \(\displaystyle{ (a-1) - (b-1) = a-1 - b + 1 = a-b}\).
Oczywiste, nie?
Z dodawaniem masz analogicznie.

Mnożenie:
jeżeli \(\displaystyle{ m}\) dzieli \(\displaystyle{ a - b}\), to \(\displaystyle{ m}\) dzieli \(\displaystyle{ 2a - 2b = 2(a-b)}\), czyli jest OK, ale będziemy mieli dwa razy większą liczbę.
Z dzieleniem jest analogicznie, TYLKO TRZEBA UWAŻAĆ, bo nie zawsze jak podzielimy liczby całkowite, to nadal nam wyjdzie liczba całkowita.

Tylko nie wiem czy o to Ci chodziło?

Liczba zapisana w dziesiętnym układzie pozycyjnym ma taką postać ogólną.

\(\displaystyle{ x = a_s\cdot10^s + a_{s-1}\cdot10^{s-1} +...+ a_2\cdot100 + a_1\cdot10 + a_0}\)

Taki zapis mi się skojarzył. Jest on z resztą na stronie z pierwszego odnośnika.

PS: Ciężki tydzień, temat dla mnie ważny ale może stać się tak że najszybciej odpiszę w niedzielę.

======
Co do edycji, dowodami zajmę się potem – jak coś o tym poczytam – dowiem się w końcu, co to ta indukcja matematyczna itp...

Rozbitek pisze: Najmniejszą liczbą, którą możemy przedstawić w postaci wielomianu jest \(\displaystyle{ 10}\).
\(\displaystyle{ 10 = 1 \cdot 10^1 + 0 \cdot 10^0}\)

Biedna piątka, ona już nie może być w postaci wielomianu przedstawiona?
To trochę straszne że piszesz coś takiego a już parę linijek później przypominasz że \(\displaystyle{ 10^0 = 1}\)

A co z ułamkami, przez tyle lat okłamywano mnie, że liczba \(\displaystyle{ 0,5}\) jest zapisana w systemie dziesiętnym a tu nic z tego?

Edit:
Dla autora: tu masz naprawdę przystępnym językiem wspomniane o kongruencjach:


A tutaj seminarium olimpijskie dawnego OMG, artykuł piąty(choć polecam wszystkie, są b.ciekawe), znajdziesz tam kilka szkiców zadań rozwiązanych, kilkanaście do zrobienia i na końcu są do tego wyczerpujące odpowiedzi.

... atyki.html

Nie zniechęcaj się jeśli po przeczytaniu któregoś akapitu zdasz sobie sprawę że nic z tego nie rozumiesz, przeczytaj 2,3 może 5 raz, zdaję sobie sprawę że to są rzeczy "nowe", sam się dokładnie w ten sam sposób tego uczyłem i jest to spokojnie do ogarnięcia.

Rafsaf, zapoznałem się z pierwszym linkiem który umieściłeś w poście.

Przeczytałem całe ale idąc slajd po slajdzie i próbując przyswoić zawartą tam wiedzę natrafiłem na wiele przeszkód - jest jednak jedna której pokonać nie mogę. Szybko mnie rozwaliło swoją drogą.

Dowód twierdzenia że:

Warunkiem koniecznym i wystarczającym aby \(\displaystyle{ a \equiv b\pmod{n}}\) jest aby reszty z dzielenia \(\displaystyle{ a}\) i \(\displaystyle{ b}\) przez n były równe
Dowód jest następujący:
[ciach]
===============
Mam problem bo ... nic nie rozumiem (tego w szkole nie było albo jestem [ciach] głupi), gdzieś po drodze gubię się i po prostu ten dowód dla mnie nic nie znaczy, coś mi umyka, czy pomożecie mi znaleźć co to takiego?
Widocznie autor robi jakieś założenia o wiedzy czytelnika których ja nie spełniam i mamy to co mamy.

No to ok, spokojnie i bez paniki.
\(\displaystyle{ a \equiv b\pmod{n}}\) daje
\(\displaystyle{ a-b = kn}\) po przeniesieniu \(\displaystyle{ b}\) na drugą stronę
\(\displaystyle{ a = b+kn}\)
I teraz po tych 3 linijkach się gubię bo nie ma pojęcia jak on podzielił tą linijke wyżej przez \(\displaystyle{ b}\) i otrzymał równość....
\(\displaystyle{ (qn+r) + kn}\)

Nie rozumiem czym jest to \(\displaystyle{ q}\) ani jak on dokonał tego dzielenia, jak u siebie dziele całośc przez \(\displaystyle{ b}\) to nie chce mi wyjść ani tym bardziej pojawić się magiczne \(\displaystyle{ q}\).
Każda wskazówka mile widziana:)

PS:Zapewniam że piszę na forum bo męczę to już chyba 3 dni (nie mówię że 24 h na dobę) i nie moge sobie poradzić a nie dlatego że jestem leniwy i chce gotowca.

Po kolei:
1. \(\displaystyle{ a = b+kn}\) To z \(\displaystyle{ a \equiv b \pmod{n}}\)
Teraz tak:
2. Autor założył że \(\displaystyle{ b}\) daje przy dzieleniu przez liczbę \(\displaystyle{ n}\) resztę \(\displaystyle{ r}\).
3. Zatem z pewnością liczba \(\displaystyle{ b}\) da się przedstawić w postaci \(\displaystyle{ b=qn+r}\) gdzie \(\displaystyle{ q}\) i \(\displaystyle{ r}\) są pewnymi liczbami całkowitymi
(Na liczbach całkowitych zawsze tak się da, przecież \(\displaystyle{ 43}\) można przedstawić jako \(\displaystyle{ 43=7 \cdot 6+1}\), chyba dostrzegasz analogię.)

4. Teraz wracamy do 1.
\(\displaystyle{ a = b+kn}\) i podstawiamy za \(\displaystyle{ b}\) to co otrzymaliśmy w 3.

\(\displaystyle{ a = b+kn=qn+r+kn=n(q+k)+r}\)

Ogólnie to twierdzenie jest bardzo intuicyjne możesz sobie sprawdzić jego działanie "na palcach" na małych liczbach.