Liniowe równania diofantyczne, Kongruencja liniowa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
piotr39
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 5 cze 2014, o 04:03
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz

Liniowe równania diofantyczne, Kongruencja liniowa

Post autor: piotr39 »

Witam, czy ktoś mógłby mi łopatologicznie wytłumaczyć, jak rozwiązać te zadania krok po kroku?
Rozwiąż w liczbach całkowitych:
1. a) \(\displaystyle{ 126x+96y=12}\) b) \(\displaystyle{ 14x-60y=125}\)
2. a) \(\displaystyle{ 15x\equiv_{24} 7}\) b) \(\displaystyle{ 12x\equiv_{24} 144}\)
3. \(\displaystyle{ 3x ^{966} - 2x ^{2} + 2x - 3 \equiv_{5} 0}\) - zastosuj Małe Tw. Fermata albo Tw. Eulera
4. \(\displaystyle{ x\equiv_{18} 7 ^{3552}}\) - zastosuj Tw. Eulera a następnie algorytm szybkiego potęgowania modulo n

PS: Bardzo proszę moderatora o poprawienie, bo albo latex nie działa albo ja coś źle robię.
Ostatnio zmieniony 5 cze 2014, o 09:27 przez , łącznie zmieniany 1 raz.
Powód: Nie wyłączaj BBCode, bo wtedy nie działają klamry [latex]..[/latex]
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Liniowe równania diofantyczne, Kongruencja liniowa

Post autor: Premislav »

4. Ponieważ \(\displaystyle{ (7,18)=1}\), to z twierdzenia Eulera mamy \(\displaystyle{ 7 ^{\phi(18)}\equiv 1\pmod{18}}\). Policz \(\displaystyle{ \phi(18)}\), co jest łatwe, a następnie przedstaw ten poroniony wykładnik w postaci \(\displaystyle{ 7k+p}\), tak by \(\displaystyle{ p \in\left\{0,1,2,3,4,5,6\right\}}\),wykonując dzielenie przez \(\displaystyle{ 7}\) z resztą. Następnie skorzystaj z tego, że\(\displaystyle{ a^{b+c}=a^{b}\cdot a^{c}}\)
3. z MTF \(\displaystyle{ x ^{4}\equiv 1 \pmod{5}}\), chyba że \(\displaystyle{ 5|x}\), ale wówczas otrzymalibyśmy łatwo sprzeczność (bo lewa strona wówczas \(\displaystyle{ \equiv 2\pmod{5}}\), a prawa to duma i sława).
Przedstaw \(\displaystyle{ 966}\) jako \(\displaystyle{ 4k+p}\), gdzie \(\displaystyle{ p\in \left\{0,1,2,3\right\}}\). Oczywiście tutaj i w czwartym \(\displaystyle{ k}\) i \(\displaystyle{ p}\) mają być całkowite (ba, nawet naturalne).
1. i 2. może innym razem, bo materiał na kolokwium czeka.
EDIT: przepraszam, w czwartym oczywiście chodziło o \(\displaystyle{ \phi(18) \cdot k+p}\), tak, jak jest powyżej byłoby bez sensu.
specjal3
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 6 cze 2014, o 17:22
Płeć: Mężczyzna
Lokalizacja: Warszawa

Liniowe równania diofantyczne, Kongruencja liniowa

Post autor: specjal3 »

1.)Równanie diofantyczne
a)\(\displaystyle{ 126x + 96y=12}\)
a=126, b=96, c=12

1.1.Szukamy NWD(126,96) Algorytmem Euklidesa.
\(\displaystyle{ NWD(126,96)= 6}\)
\(\displaystyle{ d=6}\)

\(\displaystyle{ 126= 1 \cdot 96 \cdot +30}\)
\(\displaystyle{ 96= 3 \cdot 30+6}\)
\(\displaystyle{ 30= 5 \cdot 6+0}\)

1.2 Jeżeli NWD|c to:

\(\displaystyle{ 6=96 - 3 \cdot 30}\)
\(\displaystyle{ =96 - 3 \cdot (126-1 \cdot 96)}\)
\(\displaystyle{ =4 \cdot 96-3 \cdot 126}\)

i dalej.
\(\displaystyle{ 6=-3 \cdot 126+4 \cdot 96}\)
\(\displaystyle{ 6=-3 \cdot 126+4 \cdot 96 / \cdot 2}\)
\(\displaystyle{ 12= -6 \cdot 126+8 \cdot 96}\)

wyznaczyliśmy rozwiązania zerowe
\(\displaystyle{ x0=-6}\) i \(\displaystyle{ y0=8}\)

1.3 Teraz rozwiązanie w liczbach całkowitych
\(\displaystyle{ x=x0+ \frac{b}{d} \cdot t}\)
\(\displaystyle{ y=y0- \frac{a}{d} \cdot t}\)


\(\displaystyle{ x=-6+ \frac{96}{6} \cdot t}\)
\(\displaystyle{ x=-6+16 \cdot t}\)
\(\displaystyle{ y=8- \frac{126}{6} \cdot t}\)
\(\displaystyle{ y=8- 21 \cdot t}\)

Odp. x=-6+16*t i y=8- 21*t.


b)\(\displaystyle{ 14x-60y=125}\)
\(\displaystyle{ NWD(60,14)=2}\)
\(\displaystyle{ d=2}\)
\(\displaystyle{ d\nmid c}\)
Odp. brak rozwiązań

2.)
a)
\(\displaystyle{ 15x \equiv_{24} 7 \Leftrightarrow 15x+24y=7}\)
\(\displaystyle{ NWD(24,15)=3}\)
\(\displaystyle{ d=3}\)
\(\displaystyle{ d\nmid c}\)
Odp. brak rozwiązań
ODPOWIEDZ