Matematyka.pl

Jeżeli liczba przy podziale na \(\displaystyle{ 7}\) daje resztę \(\displaystyle{ 2}\), a przy podziale na \(\displaystyle{ 3}\) daje resztę \(\displaystyle{ 1,}\) to ile daje przy podziale na \(\displaystyle{ 21}\)? Wyszło mi że \(\displaystyle{ 16}\). Ale próbuję to algebraicznie wykazać i nie wychodzi. Proszę o podpowiedź.

Oznaczmy tę liczbę przez \(\displaystyle{ x}\). Masz \(\displaystyle{ x\equiv 2\pmod{7} \wedge x\equiv 1\pmod{3}}\), zatem po pierwsze istnieje takie \(\displaystyle{ k}\) całkowite, że \(\displaystyle{ x=7k+2}\), a po drugie istnieje takie \(\displaystyle{ p}\) całkowite, że \(\displaystyle{ x=3p+1}\). Czyli ma być dla pewnych \(\displaystyle{ p, k}\) całkowitych
\(\displaystyle{ 7k+2=3p+1}\), tj. \(\displaystyle{ p= \frac{7k+1}{3}}\), a więc (bo \(\displaystyle{ p}\) ma być całkowite) \(\displaystyle{ 7k\equiv 2\pmod{3}}\), mnożąc tę kongruencję stronami przez \(\displaystyle{ 2}\) i redukując wielokrotności trójki, mamy \(\displaystyle{ 2k\equiv 1\pmod{3}}\), skąd płynie wniosek, że \(\displaystyle{ k\equiv 2\pmod{3}}\). Czyli z kolei istnieje takie \(\displaystyle{ n \in \ZZ}\), że \(\displaystyle{ k=3n+2}\), a więc
\(\displaystyle{ x=7k+2=...}\)
W ten sposób znajdujesz rozwiązanie, a jako że \(\displaystyle{ \NWD(3,7)=1}\), to z chińskiego twierdzenia o resztach jest to jedyne rozwiązanie tego układu modulo \(\displaystyle{ 21}\).

\(\displaystyle{ x=7n+2 \\
x=3n+1}\)

\(\displaystyle{ 3x=21n+6 \\
7x=21n+7}\)

\(\displaystyle{ 15x=105n+30 \\
14x=42x+14}\)

odejmuję stronami

\(\displaystyle{ x=63n+16}\)

Nie rozumiem od " mnożąc tę kongruencję... " Napiszesz jak wyglądały obliczenia? - bo najwyraźniej nie rozumiem jak się wykonuje działania na funkcji modulo.

Dzięki Ania221 o to mi chodziło - nie zauważyłem tej opcji.

Premislav nie zauważyłem braku znaku zapytania - przepraszam jeśli zostałem żle odebrany.

Twoje zdanie nie jest w formie pytania (zresztą nie ma znaku zapytania), więc brzmi jak stwierdzenie/polecenie, a to trochę niegrzecznie.

Dochodzimy do \(\displaystyle{ 7k\equiv 2\pmod{3}}\). Mnożymy to stronami przez \(\displaystyle{ 2}\) i mamy \(\displaystyle{ 14k\equiv 4\pmod{3}}\) (jak nie rozumiesz, czemu tak można, to spójrz na to tak: liczba \(\displaystyle{ 7k}\) daje się zapisać jako \(\displaystyle{ 3l+2}\) dla pewnego \(\displaystyle{ l}\) całkowitego, a zatem
liczba \(\displaystyle{ 2\cdot 7k}\) może być zapisana jako \(\displaystyle{ 6l+4}\), co daje taką samą resztę, jak \(\displaystyle{ 4}\) z dzielenia przez trzy). no i teraz zauważamy, że \(\displaystyle{ 14k=12k+2k}\) oraz \(\displaystyle{ 3|12k}\) (bo \(\displaystyle{ k}\) z założenia było całkowite). no to liczby różniące się o wielokrotność \(\displaystyle{ 3}\) dają taką samą resztę z dzielenia przez \(\displaystyle{ 3}\), więc \(\displaystyle{ 2k\equiv 4\pmod{3}}\), czyli \(\displaystyle{ 2k=3j+4}\) dla pewnego \(\displaystyle{ j}\) całkowitego, a wszak \(\displaystyle{ 3j+4=3(j+1)+1}\), co daje resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 3}\). Dochodzimy do momentu \(\displaystyle{ 2k\equiv 1\pmod{3}}\), no i znowu mnożymy stronami przez dwa i redukujemy (zauważ, że można było od razu pomnożyć kongruencję \(\displaystyle{ 7k\equiv 2\pmod{3}}\) stronami przez \(\displaystyle{ 4}\) i zredukować, byłoby krócej i szybciej, ale ja jestem idiotą i tego nie zauważyłem).
no i już pozostałe wnioski powinny być jasne.

Teraz jasne- to przejście od 14k do 2k nie widziałem jak zrobiłeś - teraz już rozumiem- dzięki.