Strona 1 z 1
Reszta z dzielenia w Z
: 16 cze 2015, o 13:55
autor: Moower
Witam. Niestety ominąłem kilka zajęć i nie potrafię zrozumieć jednego zapisu.
Np.:
Wyznacz \(\displaystyle{ 15^{-1}}\) w \(\displaystyle{ Z^*_{43}}\) z mnożeniem.
Co oznacza dokładnie to Z, co oznacza Z* oraz jak rozwiązywać tego typu zadania (nie chodzi mi o rozwiązanie tego konkretnie, chociaż byłoby miło, ale o sam sposób).
Pozdrawiam
Reszta z dzielenia w Z
: 16 cze 2015, o 14:17
autor: MadJack
\(\displaystyle{ \mathbb{Z}_{43}^*}\) z mnożeniem, to grupa składająca się z elementów \(\displaystyle{ \{1,...,42\}}\). czyli w porównaniu do elementów tego bez gwiazdki ma wyrzucone zero (inaczej z mnożeniem nie dawałoby to grupy). \(\displaystyle{ 43}\) jest liczbą pierwszą, więc każdy element tej grupy ma element odwrotny.
Wskazówka do rozwiązania samego zadanie: rozszerzony algorytm Euklidesa. Jakby coś było niejasne, to pisz.
Reszta z dzielenia w Z
: 16 cze 2015, o 14:52
autor: Moower
Ok, to z Z już rozumiem, niestety jak samo zadanie rozwiązać nadal nie wiem
Mógłbym prosić o rozwiązanie np tego przykładu:
Wyznacz największą wartość
\(\displaystyle{ A \in Z_{32}}\) gdy
\(\displaystyle{ x^{66} + 2*x^{33} +4x\neg_{32} A}\)
a x jest jednocyfrową liczbą nieparzystą.
Póki co próbowałem je zrobić na własną rękę jednak nie za bardzo mi to idzie:
\(\displaystyle{ (x^2)^{33} + 2*x^{33} +4x\neg_{32}A}\)
\(\displaystyle{ x^{2}*(x^2)^{32} + 2x*x^{32} +4x\neg_{32}A}\)
i na dobrą sprawę nie wiem co dalej
Myślałem czy nie można skrócić tej potęgi 32 ale nie jestem pewien.
Wtedy wyszłoby
\(\displaystyle{ x^{2} +5x \neg_{32}A}\)
i wystarczyłoby podstawiać kolejne cyfry 1,3,5,7,9. Ale nie wiem czy można tak skrócić to...
użyłem
\(\displaystyle{ \neg}\) zamiast ~, bo nie wiem jak ją wprowadzić w LaTeX'ie
Reszta z dzielenia w Z
: 16 cze 2015, o 16:19
autor: MadJack
Żeby zmniejszyć potęgi, skorzystaj z
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29
. Co ma w Twoim zapisie znaczyć
\(\displaystyle{ \sim}\)?
Natomiast co do wyznaczenia elementu odwrotnego:
Zauważ, że
\(\displaystyle{ NWD(15,43) = 1}\), a to znaczy, że równanie
\(\displaystyle{ 15x + 43y = 1}\), a stąd
\(\displaystyle{ 15x - 1 = -43y}\), więc
\(\displaystyle{ 43 \mid 15x-1}\), stąd
\(\displaystyle{ 15x \equiv 1 \pmod{43}}\), a zatem
\(\displaystyle{ x}\) jest elementem odwrotnym
\(\displaystyle{ 15}\). Zatem żeby rozwiązać poprzednie zadanie, rozwiąż korzystając z rozszerzonego algorytmu Euklidesa
\(\displaystyle{ 15x + 43y = 1}\), wtedy
\(\displaystyle{ x}\) będzie szukaną przez Ciebie wartością.