Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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á:


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í (?)


What does a drowning number theorist say?
'log log log log ...'

Offline

  • (téma jako vyřešené označil(a) Andrejka3)

#2 04. 01. 2012 20:39

vanok
Příspěvky: 13664
Reputace:   734 
 

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

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.


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Online

 

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

vanok
Příspěvky: 13664
Reputace:   734 
 

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

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 

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


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Online

 

#4 04. 01. 2012 20:58

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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...


What does a drowning number theorist say?
'log log log log ...'

Offline

 

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

vanok
Příspěvky: 13664
Reputace:   734 
 

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

↑ Andrejka3:

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


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Online

 

#6 04. 01. 2012 21:05

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#7 04. 01. 2012 21:07

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#8 04. 01. 2012 21:08

vanok
Příspěvky: 13664
Reputace:   734 
 

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

↑ Andrejka3:,
no Bezout


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Online

 

#9 04. 01. 2012 21:29

vanok
Příspěvky: 13664
Reputace:   734 
 

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


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Online

 

#10 04. 01. 2012 21:35

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

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

FailED
Příspěvky: 1255
Reputace:   42 
 

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

↑ 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)$.

Offline

 

#12 04. 01. 2012 21:38

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#13 04. 01. 2012 21:39

vanok
Příspěvky: 13664
Reputace:   734 
 

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

↑ 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.


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Online

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson