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ę.
Liniowe równania diofantyczne, Kongruencja liniowa
-
- 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
Ostatnio zmieniony 5 cze 2014, o 09:27 przez Qń, łącznie zmieniany 1 raz.
Powód: Nie wyłączaj BBCode, bo wtedy nie działają klamry[latex]..[/latex]
Powód: Nie wyłączaj BBCode, bo wtedy nie działają klamry
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Liniowe równania diofantyczne, Kongruencja liniowa
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.
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.
Liniowe równania diofantyczne, Kongruencja liniowa
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ń
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ń