kongruencja

[SirMisiek]

Czy mógłby mi to ktoś łopatologicznie wytłumaczyć? Przeglądałem forum w tym kierunku, ale nie bardzo to mogę zaczaić. Bo przykłady typu \(\displaystyle{ 4x\equiv5mod7}\) to sobie potrafię na piechotę policzyć robiąc to tak:

\(\displaystyle{ NWD(4,7)=1}\)
\(\displaystyle{ 4x-5= 7k}\) gdzie \(\displaystyle{ k \mathbb{Z}}\)

wiemy, że działamy w ciele \(\displaystyle{ \mathbb{Z}_{7}}\) więc podstawiam po kolei za x od 0-6 i wychodzi mi co tam się dzieli bez reszty. Czyli w przypadku powyżej rozwiązaniem jest\(\displaystyle{ x=3+7k}\) gdzie \(\displaystyle{ k \mathbb{Z}}\) i jest wszystko pięknie, ale w przypadku gdy operujemy na dużo większych liczbach, stosowanie tego sposobu na kolokwium to strzał w stopę z broni dużego kalibru

A przykłady zdarzają się takie \(\displaystyle{ 27x\equiv72mod900}\), co wprawdzie można sprowadzić do \(\displaystyle{ 3x\equiv8mod100}\) ale i tak operować w ciele \(\displaystyle{ \mathbb{Z}_{100}}\) i podstawiać mi się nie widzi

[frej]

KLIK
Zajrzyj też do tego linka, który podałem w treści mojego posta.

Mam nadzieję, że to choć trochę Ci rozjaśni

[mol_ksiazkowy]

A przykłady zdarzają się takie \(\displaystyle{ 27x\equiv72mod900}\), co wprawdzie można sprowadzić do \(\displaystyle{ 3x\equiv8mod100}\) ale i tak operować w ciele \(\displaystyle{ \mathbb{Z}_{100}}\) i podstawiać mi się nie widzi

[/quote]
w tej ostatniej kongruencji widziesz od razu ze liczba x musi miec oststnia cyfre "6":
x=10y+6 po wstawieniu
\(\displaystyle{ 3y+1 \equiv \ 0 \ mod 10}\)
co jest latwe

[SirMisiek]

no dobra do przykładu \(\displaystyle{ 3x\equiv 8 mod 100}\)

Szukam elementu odwrotnego w ciele \(\displaystyle{ \mathbb{Z}_{100}}\) czyli:

\(\displaystyle{ 3p\equiv1 mod 100}\)
\(\displaystyle{ 3p+100q=1}\)
\(\displaystyle{ 100= 30\cdot3 + 10}\)
\(\displaystyle{ 3= jakasliczba 10 + ( - jakasliczba)}\) no i tu się zatrzymałem, mam normalnie robić + (- jakaśliczba)?

[frej]

No normalnie musisz zrobić to algorytmem Euklidesa. Poczytaj o tym sobie
Co do przykładu, to:
\(\displaystyle{ 100=3\cdot 33+1}\),
czyli \(\displaystyle{ 1=100-33\cdot 3}\),
czyli elementem odwrotnym do \(\displaystyle{ 3}\) jest \(\displaystyle{ -33}\), czyli \(\displaystyle{ 67}\) w ciele \(\displaystyle{ \mathbb{Z}_{100}}\).

[SirMisiek]

Jeszcze mam pytanie. Jak pokazać, że \(\displaystyle{ -33}\) to \(\displaystyle{ 67}\) w ciele \(\displaystyle{ \mathbb{Z}_{100}}\)

[frej]

Zauważ, że \(\displaystyle{ 100}\) jest elementem neutralnym w ciele \(\displaystyle{ \mathbb{Z}_{100}}\), czyli \(\displaystyle{ a+100 \equiv a (mod 100)}\). Zachodzi więc
\(\displaystyle{ -33\equiv -33+100 \equiv 67 (mod 100)}\).

[dyda_7]

czy moze mi ktos wytlumaczyc jak obliczyc 13^7 mod677 ?