element odwrotny andrzej: Element odwrotny Oblicz element odwrotny 23⁻¹ mod 26 Robię to w standardowy sposób, czyli: 26 = 23 * 1 + 3 23 = 3 * 7 + 2 7 = 2 * 3 + 1 3 = 3 * 1 + 0 1 = 7 − 2 * 3 = 7 − 3 * (23 − 3 * 7) = 7 − 3 * 23 + 9 * 7 = −3 * 23 + 10 * 7 = = −23 * (26 − 23 * 1) + 10 * 7 i dalej nie wiem jak to odtworzyć

andrzej: ?

utem: 26=1*23+3 23=7*3+2 3=1*2+1 1=3−1*2=3−1*(23−7*3)=3−1*23+7*3=8*3−1*23= =8*(26−23*1)−1*23=8*26−8*23−1*23=8*26−9*23 −9+26=17 17 to odwrotna do 23 w Z₂₆ spr. 17*23=391=15*26+1 17*23=1( mod26)

andrzej: fakt, błąd ludzki a jak rozwiązać 2x = 4 (w ℤ₈) ?

utem: w pamięci : {0,1,2,3,4,5,6,7} x=2 x=6 x=2+4n

andrzej: możesz nieco bardziej wyjaśnić ?

utem: Podstawiam do równania wszystkie po kolei liczby z podanego zbioru i badam resztę. To jest proste równanie, chyba tu można podzielić przez 2 ( ale nie polegaj na mnie w tym zakresie) 2x=4(mod8) x=2 (mod4) Saizou spojrzyj tutaj.

Saizou : kongruencje można dzielić stronami pod pewnymi warunkami 2x=4 mod8 /:2 teraz sprawdzamy sobie NWD(2,8)=2 , zatem

2x		4		8
	=		mod
2		2		NWD(2,8)=2

x=2 mod4

andrzej: a jakbyśmy nie chcieli dzielić stronami, to możemy rozwiązać to jakoś inaczej ?

utem: Tak, właśnie myślałam. Dzięki Saizou, nie chciałabym kogoś w błąd wprowadzić

andrzej: a czy moglibyście bardziej mi wyjaśnić ten zapis ?

Saizou : 2x≡4 mod8 2x−4≡0 mod8 stąd istnieje jakaś liczba całkowita k także 2x−4=8k (to już jest normalne równanie) x−2=4k przechodząc na przystawanie x≡2 mod4

andrzej: a takie równanie, 3x + 4 = 1 w ℤ₁₁ ?

utem: Np. Odwrotna do 3 w Z₁₁ Licz w pamięci.

andrzej: nie ma jakiegoś schematu na rozwiązywanie tego ?

Saizou : 3x+4=1 3x+3=0 mod11 3x=−3 mod11 /:3 NWD(3,11)=1 x=−1 mod11 x=10 mod11 x=10+11k gdzie k przebiega zbiór liczb całkowitych

utem: 3x+4=1 (mod11) /−4 3x=−3(mod11) 3⁻¹ możesz za pomocą algorytmu, ale tu jest proste do odgadnięcia 3*4=12=1(mod11) 3x=−3(mod11) /*4 12x=−12(mod(11)⇔ 11x+1x=−12(mod11) 1x=10(mod11) [−12+11+11=10]

andrzej: a można 3x + 4 = 1 mod 11 / + 7 3x = 8 mod 11 ... ?

Saizou : można bo dalej np. 3x≡8≡−3 mod11

andrzej: (3, 11) 11 = 3 * 3 + 2 3 = 2 * 1 + 1 2 = 2 * 1 + 0 1 = 3 * 1 − 2 * 1 = 3 * 1 − 1 * (11 − 3 * 3) = 3 * 1 − 11 * 1 + 3 * 3 = 4 * 3 − 1 * 11 3⁻¹ = 4 4 * 3x = 32 mod 11 12x = 32 mod 11 x = 32 mod 11 x = 10 mod 11 jest ok ?

andrzej: jeżeli jest ok, to moje ostatnie zadanie na dziś, jak obliczyć

2		4
	+		w ℤ11 ?
3		5

Saizou : Odpowiedz sobie na te pytania co jest elementem odwrotnym do 3 w Z₁₁ ? co jest elementem odwrotnym do 5 w Z₁₁?

	1
+ skorzystaj z tego że		=3−1
	3

andrzej: element odwrotny do 3 w ℤ₁₁ to 4 element odwrotny do 5 w ℤ₁₁ to 2 i jak z tego skorzystać ?

Saizou : od kiedy do 5 elementem odwrotnym jest 2 ? 5*2=10 a nie 1 mod 11

2
	=2*3−1=2*4=8
3

andrzej: to jak obliczyć ten element odwrotny używając notacji 11 = 5 * 2 + 1 2 = 2 * 1 + 0

utem: 5*9=45=4*11+1

andrzej: a nie da się obliczyć tego za pomocą algorytmu euklidesa, tak jak do tej pory to pisałem ?

andrzej: 1/5 = 5⁻¹ 2 * 3⁻¹ = 2 * 4 = 8 4 * 5⁻¹ = 4 * 9 = 36 8 + 36 = 44 mod 11 = 0 mod 11 ?

utem: 1=1*1=1*(11−5*2)=1*11−2*5 −2+11=9 Ja bym najpierw sprowadziła do wspólnego mianownika

10+12		22
	=
15		15

22=0(mod11) 15=4(mod11) Wynik: 0

andrzej: A jak wyznacza się element odwrotny w ℤ^*₁₃ ? (liczby względnie pierwsze z 13 z działaniem modulo). Przykładowo element odwrotny 8 w ℤ^*₁₃

andrzej: podbijam

andrzej: ?

Mila: Element odwrotny w Z₁₃ ?

andrzej: Element odwrotny 8 w ℤ₁₃ to 13 = 1 * 8 + 5 8 = 1 * 5 + 3 5 = 1 * 3 + 2 3 = 1 * 2 + 1 2 = 2 * 1 + 0 1 = 3 − 1 * 2 = 3 − 1 * (5 − 1 * 3) = 1 * 3 − 5 + 1 * 3 = 2 * 3 − 1 * 5 = = 2 * (8 − 1 * 5) − 1 * 5 = 2 * 8 − 2 * 5 − 1 * 5 = 2 * 8 − 3 * 5 = = 2 * 8 − 3 * (13 − 1 * 8) = 2 * 8 − 3 * 13 + 3 * 8 = 5 * 8 − 3 * 13 czyli 5, ale tam mamy z tym oznaczeniem, więc jak to traktować ?

Mila: Musisz popatrzeć na notatki, albo do podręcznika, co tam pisze na temat tej gwiazdki. Poczekaj na Saizou.

andrzej: napisałem w nawiasie, co tam ta "gwiazdka" oznacza − są to liczby względnie pierwsze z 13, tylko nie wiem jak tutaj zastosować 

Mila: 8 i13 są względnie pierwsze. NWD(8,13)=1 Nie będzie elementu odwrotnego np. do 26 NWD(26,13)=13

andrzej: Jaka jest odwrotna liczba dla 1⁻¹ mod 3 ? bo wychodzi mi 3 = 3 * 1 + 0, i nie wiem co dalej 0 ?

andrzej: Czy jest jakaś metoda na sprawdzenie, czy dany przedział ma element odwrotny ?

andrzej: 1⁻¹ mod 3 = 1 ? czy jak

andrzej: I jak ostatecznie ma być to działanie z "gwiazdką" ? Jak je rozumieć ?

utem: Liczba całkowita a jest odwracalna modulo m wtedy i tylko wtedy, gdy NWD(a, m) = 1.

andrzej: w takim razie 1⁻¹ mod 3 = 1 ?

utem: Tak. Ta gwiazdka, to może chodzić o pierścień? Miałeś coś takiego na wykładzie? Elementami odwracalnymi pierścienia Z_n są te liczby ze zbioru: {0, 1, ...., n−1}, które są względnie pierwsze z n: Z_n^* = {[a]: NWD(a, n) = 1}.

andrzej: odnośnie gwiazdki, to napisałem obok to co miałem w zadaniu: ℤ₁₃ (liczby względnie pierwsze z 13 z działaniem modulo). tylko jakoś tego nie rozumiem

andrzej: ?

utem: Definicja Symbol Z*_n oznacza zbiór wszystkich elementów Z_n, dla których można wyznaczyć liczby odwrotne; czyli zbiór takich liczb a należących do Z_n, że a oraz n są względnie pierwsze. przykładowo dla : 1) liczby pierwszej 13: Z₁₃^*={1,2,3,4,5,6,7,8,9,10,11,12} dla każdej możesz wyznaczyć odwrotną. 2) Dla liczby 4: Z₄={0,1,2,3} 0 nie ma odwrotnej odwrotna do 1 to 1 2x=1(mod4), NWD(2,4)=2 nie ma odwrotnej 3x=1(mod4), NWD(3,4)=1 4=3*1+1 1=4−1*3 −1 to odwrotna do 3. sprawdzamy równanie: 3*(−1)=−3≡(−3+4)(mod4)=1(mod4) Z₄*={1,3}

andrzej: Czyli jak mam: odwrotność 8 w Z^*₁₃ to: 8x = 1 (mod 13) NWD(8, 13) = 1 x = 5 (mod 13)

utem: To dawno miałeś ustalone. 5*8=40=3*13+1 5*8≡1(mod13)

andrzej: a wiesz coś może o grupach cyklicznych ?

utem: Nie pamiętam, napisz problem, może razem cokolwiek rozwikłamy. Może Saizou tu spojrzy, on jest na bieżąco z materiałem, ale nie wiadomo, czy już to przerabiał.

andrzej: Rozpatrzmy grupę Φ(12) (czyli liczby względnie pierwsze z 12 i z mnożeniem mod 12). a) czy jest to grupa cykliczna b) podaj rzędy elementów tej grupy

utem: Tu masz przykłady. http://aragorn.pb.bialystok.pl/~aborowska/MPK/Krypt2011_PS12.pdf

andrzej: a jak szuka się tych generatorów ?

andrzej: Φ(12) = {1, 5, 7, 11} To są chyba kandydaci ? 1 odpada <5> = { 5¹ = 5, 5² = 1, 5³ = 5, 5⁴ = 1} (ale brakuje 7 i 11, więc nie jest generatorem?) <7> = {7¹ = 7, 7² = 1, 7³ = 7, ... } (brakuje 5 i 11) <11> = {11¹ = 11, 11² = 1, 11³ = 11, ... } Nie ma w ogóle generatorów ?

andrzej: źle, moment

andrzej: 5¹ = 5, 5⁵ = 5, 5⁷ = 5, 5¹¹ = 5, czyli nie jest generatorem ?

Kacper: Najpierw zastanów się co to generator grupy.

andrzej: jak dla mnie generator grupy to ten element, który potęgując otrzymujemy wszystkie inne, w danym ciele ?

andrzej: ?

andrzej: ?

andrzej: może ktoś wyjaśnić mi te generatory ?

utem: Z₁₂={0,1,2,3,4,5,6,7,8,9,10,11} Z_*{12}={1,5,7,11} dla każdego a∊Z₁₂ jest spełniony warunek:NWD(a,12)=1 Rząd grupy : Φ(12)=4 Rząd (1) =1 ponieważ <1>={1} Rząd (5)=2 ponieważ <5>={1,5} 5¹=5∊Z₁₂, 5²=25=1(mod12) Rząd (7)=2 ponieważ <7>={1,7} 7¹=7, 7²=49=1(mod12) Rząd (11)=2 ponieważ <11>={1,11} 11¹=11,11²=121=1(mod12) To nie jest grupa cykliczna, Przykład grupy cyklicznej: Z_*5={1,2,3,4,} Φ(5)=4 Rząd (1)=1 ponieważ <1>={1} rząd (2)= 4 ponieważ <2>={1,2,3,4} ( masz tu wszystkie elementy grupy Z^*₅ 2¹=2, 2²=4, 2³=8=3(mod5), 2⁴=16=1(mod5) rząd (3)=4 3¹=3,3²=9=4(mod5),3³=27=2(mod5), 3⁴=81=1(mod5) Rząd (4)=2 ponieważ <4>={1,4} 4¹=4, 4²=16=1(mod5) =================== Grupa ma dwa generatory: <2>, <3>

andrzej: możemy po kolei ? (1) Dlaczego rząd grupy wynosi 4? Bo ma 4 elementy? (Gdyby była np.: grupa Z₁₂ to byłby rząd 12?) (2) Na jakiej podstawie stwierdziłeś, że nie jest to grupa cykliczna? Bo podobnie sobie rozpisywałem, ale mi nie wyszło.

utem: Z*₁₂ rząd tej grupy to jej liczebność . Nie ma generatora rzędu 4.

andrzej: "Nie ma generatora rzędu 4." − w jakim sensie nie ma generatora rzędu 4? Z tego co rozumiem: − {5¹, 5⁵, 5⁷, 5¹¹} będzie dawało zawsze albo {1, 5} − więc dlatego rząd 2 ? − podobnie inne liczby Dlatego, aby grupa była cykliczna, podnoszenie do potęgi (liczbami z danego zbioru) musi zwracać właśnie te liczby, aby rząd grupy się zgadzał, tak? Jeżeli to co wyżej napisałem jest prawdą, to wczoraj tak samo myślałem, dlatego napisałem "w ogóle nie ma generatorów".

andrzej: Podobne zadanie: " jaki jest rząd 17, w Z₃₉^*" Z₃₉^* = {1 2 4 5 7 8 10 11 14 16 17 19 20 22 23 25 28 29 31 32 34 35 37 38} i teraz, aby wyznaczyć rząd 17, to muszę sprawdzać po kolei: 17¹ = 17 17² = 16 17⁴ = 22 ... Czy można jakoś szybciej? Bo nie wiem np.: jak obliczyć elementy, które nie mieszczą się na kalkulatorze.

Mila: Jest sposób, ale może tak: 17¹≡17(mod39) 17²≡16(mod39) 17³=17*16=272≡38(mod39)≡−1(mod39) 17³≡−1(mod39) 17⁴=17*(−1)=−17(mod39)=22(mod39) 17⁵=17²*17³=16*(−1)=−16≡23(mod39) 17⁶=17³*17³=(−1)*(−1)≡1(mod39) dalej będzie powtarzalność <7>={1, 16,17,22,23,38} I tak kombinuj. sprawdzaj w wolframie http://www.wolframalpha.com/input/?i=17^6%3Dx%28mod39%29 Tak zapisuj: 17⁶=x(mod(39)

andrzej: a czy moja intuicja w tym temacie (21:31 i 21:40) jest ok? tak należy to rozumieć ?

andrzej: czy może jest jakiś szybszy sposób na sprawdzenie jaki masz rząd element {17} w ℤ₃₉^*?

Mila: 22:14 tak. Gdzieś coś widziałam, ale na pewno nie dostaniesz zadania, aby trzeba było sprawdzać dużo elementów, tę powtarzalność dość szybko dostałeś. Wykorzystuj arytmetykę modulo, jak pokazałam. Czytaj dokładnie definicje pojęć. Tam o godzinie 21:02 niedokładnie napisałam drugą linijkę: Ma być tak: Z*₁₂={1,5,7,11} dla każdego a∊Z*₁₂ jest spełniony warunek: NWD(a,12)=1

andrzej: OK, tamte rzeczy chyba rozumiem, teraz mam takie zadanie: "Dane jest G = {A ∊ R^2x2 : det(A) ≠ 0} oraz H = { A ∊ R^2x2 : det(A) = 1}" i) Pokaż, że G jest grupą ii) Udowodnij, że H < G. Najpierw (i): (1) Działanie jest łączne ( [ a b ] * [ e f ] ) * [ i j ] = [ a b ] * ( [ e f ] * [ i j ] ) ( [ c d ] [ g h ] ) [ k l ] [ c d ] ( [ g h ] [ k l ] ) Po prostu to wymnożyć i sprawdzić, czy po lewej i prawej stronie są takie same? Czy jakiś inny sposób? (2) Grupa ma element neutralny − skoro wyznacznik macierzy jest niezerowy, to z podstaw algebry liniowej wiemy, że mamy macierz jednostkową, która jest elementem neutralnym, której detA = 1. Może tak być ? (3) Każdy element z grupy ma element odwrotny −> powołuje się na twierdzenie, że skoro wyznacznik jest niezerowy, to wtedy macierz ma macierz odwrotną.

andrzej: Najbardziej mi zależy jak należy pokazać, że działanie jest łączne w tym wypadku?

andrzej: ?

andrzej: ?

andrzej: ktokolwiek ?

andrzej: ?

andrzej: ?

andrzej:

andrzej:

andrzej:

andrzej: