Prosta kongruencja z algorytmem euqlidesa

[AppzAddict23]

Witam:)

Mamw wielką prośbę, za godzinkę mam zaliczenie z takiego typu zadań:

Mimo, że wczoraj siedziałem do 4, sprawdziłem wszystkie tematy związane z kongruencją
ale nadal nie wiem skąd co się bierze, proszę nie odsyłajcie mnie do google.

Proszę o dokładne, krok po kroku wyjaśnienie, jak liczyć takie zadania:

1) Sprawdz czy istnieją odwrotności a^{-1}

a przystaje 5 (mod 32)

2) Rozwiąż nastepujące kongruencje liniowe:

a) 4x przystaje 1 (mod 7)
b) 4x przystaje 3 (mod 7)

Z góry dzięki

[MagdaW]

2.

Kongruencja to reszta z dzielenia.

a)4*7a+1=28a+1
b)4*7b+3=28b+3

O to chodzi?

[frej]

2.
raczej
\(\displaystyle{ a) \qquad x \equiv 2 ( mod 7)}\)
\(\displaystyle{ b) \qquad x \equiv 6 ( mod 7 )}\)

bo co to za sztuka mnożyć przez \(\displaystyle{ 0}\)

rozpatrz wszystkie przypadki przystawania iksa modulo 7. Najpierw iks przystaje do 1, nie dziala. Potem sprawdzasz czy dziala dla 2. Jesli tak, to masz odpowiedz. Jesli nie to idziesz dalej etc.

[kuch2r]

Skoro \(\displaystyle{ a\equiv 5 \mod{32}}\)
Szukamy zatem, takiego \(\displaystyle{ x\in Z^{*}_{32}}\) ze:
\(\displaystyle{ 5\cdot x\equiv 1\mod{32}}\)
Stad:
\(\displaystyle{ x=13}\)

[AppzAddict23]

nic nierozumiem, prosiłbym od podstaw! skad to się bierze???

[RyHoO16]

ZAD.2.:
a)
\(\displaystyle{ 4x \equiv 1(mod \ 7)\\
x \equiv 1 4^{-1} (mod \ 7) \\
x \equiv 1 2 (mod \ 7) \\
x \equiv 2 (mod \ 7)\\
x=7k+2}\)
dla \(\displaystyle{ k Z}\)

[AppzAddict23]

tak ale skąd takie wyniki się biorą, jak to czytać?
dlaczego 4^-1 i potem 1x2 nastepnie sama 2, i x=7k+2, co to za zapis
i czy Z to zbiór liczb pierwszych?

Sporo czytałem ale nie wiem co z czym wiązać, proszę od podstaw..

tak już po zaliczeniu jestem, dała podobne zadania, ale proszę o wyjaśnienie..

Z góry dziękuję:)

[MagdaW]

Z to zbiór liczb całkowitych.

[AppzAddict23]

ZAD.2.:
a)
\(\displaystyle{ 4x \equiv 1(mod \ 7)\\
x \equiv 1 \cdot 4^{-1} (mod \ 7) \\
x \equiv 1 \cdot 2 (mod \ 7) \\
x \equiv 2 (mod \ 7)\\
x=7k+2}\)
dla \(\displaystyle{ k \in Z}\)

Już nieco jaśniej, ale skąd wzięła się ta []tex2[/latex] dlaczego \(\displaystyle{ 4^{-1}=2 ?}\)
Czy to wynika z tabelki mnożenia \(\displaystyle{ mod 7}\) {0,1,2,3,4,5,6} ?
faktycznie wg tej tabelki \(\displaystyle{ 2x4=1}\) a więc \(\displaystyle{ 4^{-1}=2}\), ale dlaczego?
albo \(\displaystyle{ 3x5=1 => 3^{-1}=5}\) nie rozumiem

[natkoza]

to moze ja wyjaśnie ten przykład najdokładniej jak potrafie
masz do rozwiązania kongrencję
\(\displaystyle{ 4x\eqiv 1(mod 7)}\)
masz z tego wyznaczyć wszystkie \(\displaystyle{ x\in Z}\) spełniajace ten warunek
zatem dzielimy obustronnie przez 4 w \(\displaystyle{ Z_7}\) (czyli mnożymy obie stroby przez \(\displaystyle{ 4^_{-1}}\) w \(\displaystyle{ Z_7}\))
\(\displaystyle{ x=1\cdot 4^{-1}(mod 7)}\) i teraz wyznaczamy \(\displaystyle{ 4^{-1}}\) np rozszerzonym algorytmem euklidesa (w tak małych ciałach jak \(\displaystyle{ Z_7}\) mozna to też zrobić w pamięci)
\(\displaystyle{ 7=1\cdot 4+3\\
4=1\cdot 3+1\\
\\
1=4-1\cdot 3=4-1\cdot (7-1\cdot 4)=4-1\cdot 7+1\cdot 4=2\cdot 4-1\cdot 7}\)
elementem \(\displaystyle{ 4^{-1}}\) jest liczba stojąca przy 4(mod 7) tj 2
zatem nasza kongruencja wygląda tak:
\(\displaystyle{ x\equiv 1\cdot 2(mod 7)\\
x\equiv 2(mod 7)}\)
czyli tą kongruencję spełniaja wszystkie liczby które przy dzieleniu przez 7 daja resztę 2 tj liczby postaci \(\displaystyle{ x=7k+2}\) dla każdego \(\displaystyle{ k\in Z}\)

[AppzAddict23]

Dziękuję Serdecznie, a teraz sprawdzenie czy zrozumiałem

Mamy taki przykład:

\(\displaystyle{ 22x5mod7/22^{-1}}\)
\(\displaystyle{ x 5x22^{-1}mod7}\)

\(\displaystyle{ 7=1x4+3}\)
\(\displaystyle{ 22=1x20+2= ..}\)

rozbijam \(\displaystyle{ 1=4-1x3=4-1x(7-1x4)=4-1x7+1x4= 2x4-1x7}\) //dlaczego 2? chodzi o to że są dwie 4 i tak można to zapisać.. Czy dalej czy to samo robię z 22 też rozbijam?

dalej mi wychodzi bez rozbicia 22

\(\displaystyle{ x=5x2mod7/22^{-1}}\)
\(\displaystyle{ x=5*2mod7}\)
\(\displaystyle{ x=10mod7}\)

zastem x=7k+10 sprawdziłem sobie w głowie, np x=66 czyli 7x8+10 => 56+10 = 66 reszta zostaje 10.. czy 7x3+10 x=31

czyli odwrotniością \(\displaystyle{ 22x5mod7}\) jest \(\displaystyle{ x=66}\)
dobrze to zrobiłęm?

[natkoza]

\(\displaystyle{ 22\equiv 1(mod 7)!!}\)
w ciele \(\displaystyle{ Z_7}\) elementami są jedynie \(\displaystyle{ 0,1,2,3,4,5,6}\)
\(\displaystyle{ x\equiv 5(mod 7)\\
x=7k+5}\)

[AppzAddict23]

tak ale przykład mam taki \(\displaystyle{ 22x5mod7}\)

rozpisuje zawsze moduł, a co zrobić z tym 22?

[natkoza]

zauważ, że liczba 22 w ciele \(\displaystyle{ Z_7}\) to jest tak naprawde 1
chodzi ci o przykład \(\displaystyle{ 22x\equiv 5(mod)7}\)
czy
\(\displaystyle{ 22\cdot 5=?(mod 7)}\)

[AppzAddict23]

zauważ, że liczba 22 w ciele \(\displaystyle{ Z_7}\) to jest tak naprawde 1
chodzi ci o przykład \(\displaystyle{ 22x\equiv 5(mod)7}\)
czy
\(\displaystyle{ 22\cdot 5=?(mod 7)}\)

tak tak, ten przykład \(\displaystyle{ 22x\equiv 5(mod)7}\) dlaczego 1?