szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Kobieta Offline
 Tytuł: Funkcja Eulera
PostNapisane: 11 paź 2015, o 14:24 
Użytkownik
Avatar użytkownika

Posty: 2780
Szukam ciekawych artykułów na temat funkcji Eulera. Chodzi o tę, która każdej liczbie naturalnej przyporządkowuje ilość liczb naturalnych względnie pierwszych z nią nie większych od niej.

Interesowałby mnie chociażby dowód własności \forall_{m,n \in \NN}: \phi (m  \cdot n)= \phi (m)  \cdot \phi (n). Ponadto dowód wzoru ogólnego tej funkcji, którym jest \phi (n)= n  \cdot \left( 1-\frac{1}{p_{1}}\right)  \cdot \left( 1-\frac{1}{p_{2}}\right)  \cdot ... \cdot \left( 1-\frac{1}{p_{k}}\right), gdzie p_{1},...,p_{k} to czynniki pierwsze liczby n.

Poza tym nigdzie nie mogę doszukać się zastosowań tej funkcji. No oprócz badania podzielności liczb.
Góra
Kobieta Offline
 Tytuł: Funkcja Eulera
PostNapisane: 11 paź 2015, o 15:27 
Użytkownik
Avatar użytkownika

Posty: 2505
Pokaż najpierw, że \varphi(p^k) = p^k - p^{k-1}.

Potem skorzystaj z faktu, że jeśli (a,b) = 1, to (a, x) = (b, y) = 1 \iff (ax + by, ab) = 1.

Jeśli (a,b) = 1, x przebiega \varphi(a) liczb względnie pierwszych z a, zaś y - \varphi(b) liczb względnie pierwszych z b, to ax+by przyjmuje \varphi(ab) wartości, przy czym wszystkie są względnie pierwsze z ab. Zatem \varphi(ab) = \varphi(a) \varphi(b).

Zastosowanie: kryptografia (RSA) dzięki twierdzeniu Eulera: jeśli (a, n) = 1, to n \mid (a^{\varphi (n)} - 1).
Góra
Kobieta Offline
 Tytuł: Funkcja Eulera
PostNapisane: 11 paź 2015, o 21:12 
Użytkownik
Avatar użytkownika

Posty: 2780
\varphi(p^k) = p^k - p^{k-1} - ta własność dotyczy tylko liczb pierwszych. WYnika bezpośrednio ze wzoru: p^{k}-p^{k-1}=p^{k}\left( 1-\frac{1}{p}\right)

-- 11 paź 2015, o 21:36 --

Znalazłam jeszcze taką definicję: \phi (n)=\left| \left\{ k \in [n]: (k,n)=1\right\} \right|
Nie rozumiem tego zapisu. Co oznacza [n]?
Góra
Mężczyzna Offline
 Tytuł: Funkcja Eulera
PostNapisane: 11 paź 2015, o 22:14 
Użytkownik
Avatar użytkownika

Posty: 504
Lokalizacja: Chełm
Poszukujaca napisał(a):
Znalazłam jeszcze taką definicję: \phi (n)=\left| \left\{ k \in [n]: (k,n)=1\right\} \right|
Nie rozumiem tego zapisu. Co oznacza [n]?

[n]=\{1,2,\ldots, n\}
Góra
Kobieta Offline
 Tytuł: Funkcja Eulera
PostNapisane: 12 paź 2015, o 15:41 
Użytkownik
Avatar użytkownika

Posty: 2505
Własność, którą napisałam, wcale nie wynika ze wzoru Eulera, bo pojawia się w jego dowodzie (w połączeniu z multiplikatywnością daje wzór, żeby być dokładniejszą).
Góra
Kobieta Offline
 Tytuł: Funkcja Eulera
PostNapisane: 16 paź 2015, o 20:41 
Użytkownik
Avatar użytkownika

Posty: 2780
Medea 2, czyli napierw należy dowieść multiplikatywność, a potem wzór ogólny funkcji?

-- 17 paź 2015, o 08:38 --

Medea 2 napisał(a):
Pokaż najpierw, że \varphi(p^k) = p^k - p^{k-1}.


Z tym już sobie poradziłam. Po prostu wynika to z tego, że w przedziale [1,p^{k}] jest dokładnie p^{k-1} wielokrotności liczby p i tylko one nie są z nią względnie pierwsze.

Medea 2 napisał(a):
Potem skorzystaj z faktu, że jeśli (a,b) = 1, to (a, x) = (b, y) = 1 \iff (ax + by, ab) = 1.


Nie rozumiem z czego wynika ta implikacja, a potem równoważność. Mozesz wyjaśnić?
Góra
Kobieta Offline
 Tytuł: Funkcja Eulera
PostNapisane: 18 paź 2015, o 18:59 
Użytkownik
Avatar użytkownika

Posty: 2505
To jest takie fałszywe... a = y = 9, b = x = 8 :cry:
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Funkcja Eulera - zadanie 4  killeraty  7
 funkcja eulera  xxxxxx  7
 Funkcja Eulera - zadanie 2  Jovo  1
 Funkcja Eulera - zadanie 3  flake  1
 funkcja Eulera - zadanie 5  matkar1  2
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl