Matematické Fórum

Andrejka3

Ahoj. Zabývám se příkladem:
Dokažte, že pro každé přirozené číslo $n$ , větší než 1 je $\mathbb{Z}^*_n$ grupa,
kde nosná množina je $\{k \in \mathbb{N} ; 1 \leq k \leq n-1 \wedge \mathrm{D}(k,n)=1 \}$ ,
(D(.,.) je nejvetsi spolecny delitel)
binární operace je násobení modulo $n$ ,
inverze je $a' = a^{(\varphi(n)-1)} \mod n$ , kde
$\varphi(n)$ je Eulerova fce definovaná:

Autor skryl část textu. Zobrazit/skrýt!

Spočti $10'$ v $\mathbb{Z}^*_{47}$ a $20'$ v $\mathbb{Z}^*_{97}$ .

Ověřila jsem, že to je skutečně grupa, že nabízená unární operace je opravdu inverzí. Problémem zůstává výpočet těch konkrétních inverzních prvků, tj.
$10^{45} \mod 47$ , $20^{95} \mod 97$ . Jde to nějak ne-numericky? Použít nějaké kouzlo?

Druhý problém se týká Eulerovy funkce:
Neumím dokázat, že
$\varphi(ab) = \varphi(a) \varphi(b)$ pro $a,b \in \mathbb{N}, \mathrm{D}(a,b)=1$ .
Ve Wikipedii píší něco o čínské větě o zbytcích ale pro mě je to španělská vesnice.

Mohl by mi, prosím, někdo poradit?
Edit: dala jsem to obojí dohromady, protože to možná souvisí (?)

vanok · 04. 01. 2012 20:39

Ahoj ↑ Andrejka3:,
Ja by som pouzil Bezout-ovu rovnost.
Nast inverzny prvok a' prvku a napriklad v $\mathbb{Z}^*_{47}$
v Z najdes u, v take:
a*u + 47*v=1 (cf. Euklidov algoritmus)
a tak mod 47
dostanes co hladas.

vanok · 04. 01. 2012 20:55 — Editoval vanok (04. 01. 2012 21:00)

Dalsia myslienka:
Inac sa da vyuzit aj mala Fermatova veta
http://cs.wikipedia.org/wiki/Mal%C3%A1_ … _v%C4%9Bta
$1 = a^{\varphi(n)} \mod n$ kde $D(n; a)=1$
(tu vetu co pises ako Euler-ovu som ovodil

Autor skryl část textu. Zobrazit/skrýt!

v nasledujecej uvahe)

Tak napriklad
$1= 10^{46} = 10*10^{45}, \mod 47$ ( 47 je prvocislo)
z toho
$10'=10^{45}, \mod 47$

Vidis to nie je kuzlo ani magika, ale male uvahy....

A STASTLIVY NOVY ROK 2012

Andrejka3 · 04. 01. 2012 20:58

↑ vanok:
Je to tedy návrh, abych použila Euklidův algoritmus pro zhruba 46 prvků té grupy a zjistila, který je ten hledaný?
Asi to je trochu jednodušší než druhý návrh...

vanok · 04. 01. 2012 21:04 — Editoval vanok (04. 01. 2012 21:07)

↑ Andrejka3:

Napriklad ak a=10 a 47,mame 10*33-7*47=1......
cize $10'=33= 10^{46} \mod 47$

Andrejka3 · 04. 01. 2012 21:05

↑ vanok:
.. druhý návrh - Malou Fermatovu větu považuji za důsledek vlastností grup $\mathbb{Z}^*_n$ , protože to je pak pohodlné dokázat. $10'=10^{45}, \mod 47$ toto mi je jasné, jen nevím, jak se dopočítat výsledku (23 třeba :)).
Ta Eulerova fce je v pořádku, její vlastnosti dokážu ověřit až na tu poslední - "multiplikativnost".

A STASTLIVY NOVY ROK 2012

Děkuji, tobě také všechno nejlepší v roce 2012!
Díky za odpověď.

Takže Tvá první rada mi to zjednoduší na asi 46, resp. 96 použití euklidova algoritmu pro malá čísla - fajn, to se mi líbí.
Pořád ale nevím, zda lze nějak explicitně dopočítat výsledku $10^{45}, \mod 47 = ??$ , Euklidův algoritmus bych možná dokázala zredukovat opět na asi 46 kroků... Je to ale přece jen dost velké číslo...
No a též, kdokoliv by měl nápad, jak dokázat zmíněnou vlastnost Eulerovy fce, budu ráda, když napíše.
A.

Andrejka3 · 04. 01. 2012 21:07

↑ vanok:
Takže 33. Jak jsi to tak rychle spočítal? :)

vanok · 04. 01. 2012 21:08

↑ Andrejka3:,
no Bezout

vanok · 04. 01. 2012 21:29

↑ Andrejka3:,
tu mas aj po CZ nieco
http://cs.wikipedia.org/wiki/Roz%C5%A1% … algoritmus

Andrejka3 · 04. 01. 2012 21:35

Díky moc!!!!
10u mod 47 = 1
10 u - 47 v = 1
u = (47 v + 1)/10
chci aby to vyšlo celé, tak mě napadne, v = 7, aby 47*7 končilo devítkou
u = 330/10 = 33.
Skvělé :D
Moc se v takovéhle matice nevyznám.

FailED · 04. 01. 2012 21:36 — Editoval FailED (04. 01. 2012 21:38)

↑ Andrejka3:

Euklidův algoritmus použiješ jen pro ten prvek, který invertuješ, když au+47v=1 (mod 47), tak a'=u.

ad vlastnost Eulerovy funkce:

Pro důkaz s ČVZ viz třeba tohle.

Bez toho se dá uvažovat třeba takhle:

Vezměme číslo k, nesoudělné s a, potom čísla k, k+a, k+2a,...,k+(b-1)a jsou taky nesoudělná s a. Navíc, díky nesoudělnosti a,b, budou tato čísla nabývat všech hodnot 1,2,...,b-1 (mod b), proto mezi nimi bude právě phi(b) čísel nesoudělných s b. Proto $\varphi(ab) = \varphi(a) \varphi(b)$ .

Andrejka3 · 04. 01. 2012 21:38

↑ FailED:
Moc vám oběma děkuju, hned je mi veseleji :)

vanok · 04. 01. 2012 21:39

↑ Andrejka3:,
No mozes aj tak ako robis, sice je to pomalsie ale prides k vysledku....
Ten CZ algoritmus je uz lepsi .... a rychlejsi.

Nevyznas sa mozno v mod 47, ale mod 12 pouzivas kazdy den.

Matematické Fórum

#1 04. 01. 2012 19:00 — Editoval Andrejka3 (11. 04. 2012 16:21)

Vlastnosti Eulerovy funkce, výpočet "a mod b"

#2 04. 01. 2012 20:39

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#3 04. 01. 2012 20:55 — Editoval vanok (04. 01. 2012 21:00)

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#4 04. 01. 2012 20:58

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#5 04. 01. 2012 21:04 — Editoval vanok (04. 01. 2012 21:07)

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#6 04. 01. 2012 21:05

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#7 04. 01. 2012 21:07

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#8 04. 01. 2012 21:08

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#9 04. 01. 2012 21:29

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#10 04. 01. 2012 21:35

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#11 04. 01. 2012 21:36 — Editoval FailED (04. 01. 2012 21:38)

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#12 04. 01. 2012 21:38

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

#13 04. 01. 2012 21:39

Re: Vlastnosti Eulerovy funkce, výpočet "a mod b"

Zápatí