Rozwiąż następujące kongruencje

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Rozwiąż następujące kongruencje

Post autor: Kanodelo »

Rozwiąż następujące kongruencje:

\(\displaystyle{ 3x+2=1\;(\text{mod } 5) \\ 25x=12\;(\text{mod } 7) \\ 3x=1\;(\text{mod } 6) \\ 37x=23\;(\text{mod } 73)}\)
Ostatnio zmieniony 8 kwie 2011, o 12:37 przez Anonymous, łącznie zmieniany 2 razy.
Powód: Proszę niepotrzebnie nie używać kolorów. Poprawa tytułu i treści. Konkurencje mamy w sporcie. Tu są kongruencje.
szw1710

Rozwiąż następujące kongruencje

Post autor: szw1710 »

\(\displaystyle{ 3x+2=1\;(\text{mod } 5)}\)

Dodajemy obustronnie \(\displaystyle{ 3}\) (działanie modulo \(\displaystyle{ 5}\))

\(\displaystyle{ 3x=4\;(\text{mod } 5)}\)

Badamy \(\displaystyle{ x\in\{0,1,2,3,4\}}\) (reszty z dzielenia przez \(\displaystyle{ 5}\)). Stwierdzamy, że jedynie \(\displaystyle{ x=3}\) spełnia to równanie. Zatem ogólnie

\(\displaystyle{ x=3+5n}\), gdzie \(\displaystyle{ n}\) jest liczbą całkowitą.

Pozostałe zadania robimy podobnie.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Rozwiąż następujące kongruencje

Post autor: Kanodelo »

Co tam, napisałem konKurencje zamiast konGurencje jedna literka tylko, a nie robi wielkiej różnicy:)
A ten sposób to rozumiem, ale jak mam naprzykład ten czwarty przykład to mam badać wszystkie reszty z dzielenia przez 73? Bo chyba jest jakiś prostszy sposób niż wstawiać do tego 73 liczby i czekać czy może za 73. razem wyjdzie. Bo na prawde nie wiem jak inaczej.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Rozwiąż następujące kongruencje

Post autor: norwimaj »

Możesz też algorytmem Euklidesa znaleźć element odwrotny do \(\displaystyle{ 37}\) modulo \(\displaystyle{ 73}\) i pomnożyć przezeń równanie stronami.
szw1710

Rozwiąż następujące kongruencje

Post autor: szw1710 »

Dodam, że wielu prób tu nie trzeba Ta odwrotność jest wręcz trywialna do zgadnięcia. Trzeba tylko popatrzeć jak się mają do siebie liczby 37 i 73 i nie chodzi i przestawienie cyfr
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Rozwiąż następujące kongruencje

Post autor: norwimaj »

Masz rację szw1710. Sprawdzanie kolejnych wartości daje tu bardzo szybko wynik. Nie wiem czemu tego od razu nie zauważyłem.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Rozwiąż następujące kongruencje

Post autor: Kanodelo »

No dobrze z tym algorytmem euklidesa to umiem znaleźć element odwrotny jakby było \(\displaystyle{ 37x=1(mod73)}\), to wtedy bym to rozpisał \(\displaystyle{ 1=37-1 \cdot 36=37-1 \cdot (73-1 \cdot 37)=2 \cdot 37-1 \cdot 73}\)
Ale nie moge sobie poradzić jak tam jest 23, to wtedy robimy tak samo czy jakoś inaczej?

A już wole tym algorytmem zrobić, bo nie umiem se tak trywialnie zgadnąć jak moderator wyżej.
szw1710

Rozwiąż następujące kongruencje

Post autor: szw1710 »

Kanodelo

To zgadywanie to tylko kwestia doświadczenia i jakiegoś opatrzenia Zacząłem sobie rozpisywać algorytm Euklidesa i jakoś dostrzegłem, że przecież \(\displaystyle{ 2\cdot 37=74}\) więc modulo \(\displaystyle{ 73}\) mamy \(\displaystyle{ 1}\) i w sumie bez algorytmu Euklidesa da się łatwo ustalić, że elementem odwrotnym do \(\displaystyle{ 37}\) modulo \(\displaystyle{ 73}\) jest \(\displaystyle{ 2}\). Wystarczy więc wymnożyć równanie przez \(\displaystyle{ 2}\).
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Rozwiąż następujące kongruencje

Post autor: Kanodelo »

Czyli po pomnożeniu przez 2
\(\displaystyle{ 74=46(mod 73)}\)
i teraz jak dojść do tego, żeby wyszło 2, bo już na prawdę nic z tego nie kumam
szw1710

Rozwiąż następujące kongruencje

Post autor: szw1710 »

Stary post Działania modulo 74 - nie piszę tego Mamy \(\displaystyle{ 2\cdot 37=1}\)

\(\displaystyle{ 37x=23\\ 2\cdot 37x=46\\ x=46.}\)

I już.
ODPOWIEDZ