Witam pomoże ktoś z zadaniem:
Podpowiedź jaką dostałem:
\(\displaystyle{ 93x+k \cdot n=1}\)
\(\displaystyle{ a \cdot x=1}\)
algorytm euklidesa II
-
arti88
- Użytkownik
- Posty: 51
- Rejestracja: 18 lis 2012, o 13:58
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 22 razy
- Pomógł: 1 raz
algorytm euklidesa II
Na początku musisz sprawdzić czy liczby 93 i 1223 są względnie pierwsze(czyli największy wspólny dzielnik tych liczb wynosi 1) korzystając z algorytmu Euklidesa. Odwracając algorytm otrzymasz współczynniki A i B przy liczbach 93 i 1223.Współczynnik przy liczbie 93 będzie elementem odwrotnym w tym ciele.
Podpowiedź którą otrzymałeś przydaje się gdy A<0
Ogólniej
\(\displaystyle{ A\cdot k +B \cdot n =1}\)
\(\displaystyle{ A \cdot k + B \cdot n + k \cdot n -k \cdot n =1}\)
\(\displaystyle{ k ^{-1}=A+n >0}\)
Podpowiedź którą otrzymałeś przydaje się gdy A<0
Ogólniej
\(\displaystyle{ A\cdot k +B \cdot n =1}\)
\(\displaystyle{ A \cdot k + B \cdot n + k \cdot n -k \cdot n =1}\)
\(\displaystyle{ k ^{-1}=A+n >0}\)
-
nowik1991
- Użytkownik
- Posty: 268
- Rejestracja: 12 lis 2011, o 23:19
- Płeć: Mężczyzna
- Lokalizacja: o-o
- Podziękował: 23 razy
algorytm euklidesa II
Ok wylicze
\(\displaystyle{ NWD(93,1223)}\)
\(\displaystyle{ 1223 = 13*93 + 14}\) \(\displaystyle{ r=14}\)
\(\displaystyle{ 93 = 6*14 + 9}\) \(\displaystyle{ r=9}\)
\(\displaystyle{ 14 = 1*9+5}\) \(\displaystyle{ r = 5}\)
\(\displaystyle{ 9 = 1*5+4}\) \(\displaystyle{ r = 4}\)
\(\displaystyle{ 5 = 1*4+1}\) \(\displaystyle{ r=1}\)
\(\displaystyle{ 4 = 1*4 + 0}\)
Współczynnik \(\displaystyle{ a = -263}\) natomiast \(\displaystyle{ b = 20}\) i co dalej?
\(\displaystyle{ NWD(93,1223)}\)
\(\displaystyle{ 1223 = 13*93 + 14}\) \(\displaystyle{ r=14}\)
\(\displaystyle{ 93 = 6*14 + 9}\) \(\displaystyle{ r=9}\)
\(\displaystyle{ 14 = 1*9+5}\) \(\displaystyle{ r = 5}\)
\(\displaystyle{ 9 = 1*5+4}\) \(\displaystyle{ r = 4}\)
\(\displaystyle{ 5 = 1*4+1}\) \(\displaystyle{ r=1}\)
\(\displaystyle{ 4 = 1*4 + 0}\)
Współczynnik \(\displaystyle{ a = -263}\) natomiast \(\displaystyle{ b = 20}\) i co dalej?
-
arti88
- Użytkownik
- Posty: 51
- Rejestracja: 18 lis 2012, o 13:58
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 22 razy
- Pomógł: 1 raz
algorytm euklidesa II
I to dalej podstawiasz do tego wzoru który napisałem gdzie A= - 263, B=20 , k= 93 i n= 1223. Do tego co napisałem można dodać jeszcze jedno przekształcenie
\(\displaystyle{ (A+n) \cdot k +(B-k) \cdot n =1}\)
\(\displaystyle{ (A+n) \cdot k +(B-k) \cdot n =1}\)
-
nowik1991
- Użytkownik
- Posty: 268
- Rejestracja: 12 lis 2011, o 23:19
- Płeć: Mężczyzna
- Lokalizacja: o-o
- Podziękował: 23 razy
algorytm euklidesa II
\(\displaystyle{ (A+n) \cdot k +(B-k) \cdot n =1}\)
No ok to teraz:
\(\displaystyle{ (-263+1223)*93+(20-93)*1223 = 1}\)
\(\displaystyle{ 960*93 -73*1223 = 1}\)
\(\displaystyle{ 89280 - 89279 = 1}\)
\(\displaystyle{ 1 = 1}\)
Ok i co dalej?
No ok to teraz:
\(\displaystyle{ (-263+1223)*93+(20-93)*1223 = 1}\)
\(\displaystyle{ 960*93 -73*1223 = 1}\)
\(\displaystyle{ 89280 - 89279 = 1}\)
\(\displaystyle{ 1 = 1}\)
Ok i co dalej?
-
arti88
- Użytkownik
- Posty: 51
- Rejestracja: 18 lis 2012, o 13:58
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 22 razy
- Pomógł: 1 raz
algorytm euklidesa II
\(\displaystyle{ k ^{-1}=A+n >0}\)arti88 pisze:Na początku musisz sprawdzić czy liczby 93 i 1223 są względnie pierwsze(czyli największy wspólny dzielnik tych liczb wynosi 1) korzystając z algorytmu Euklidesa. Odwracając algorytm otrzymasz współczynniki A i B przy liczbach 93 i 1223.Współczynnik przy liczbie 93 będzie elementem odwrotnym w tym ciele.
Podpowiedź którą otrzymałeś przydaje się gdy A<0
Ogólniej
\(\displaystyle{ A\cdot k +B \cdot n =1}\)
\(\displaystyle{ A \cdot k + B \cdot n + k \cdot n -k \cdot n =1}\)
\(\displaystyle{ k ^{-1}=A+n >0}\)
\(\displaystyle{ k ^{-1}= - 263+1223=960}\)
Zatem elementem odwrotnym do 93 w tym ciele jest liczba 960