15 svar
110 visningar
mrlill_ludde 1057
Postad: 10 aug 2019 Redigerad: 10 aug 2019

Eulers fi funktion, en gång för alla!

I denna tråd https://www.pluggakuten.se/trad/euler-fi-funktion/ så sa man att man kan utnyttja fi(2m) = 2*fi(m) . Men inte för fi(3m) = 3*fi(m) Men i den här https://www.pluggakuten.se/trad/order-i-grupper-men-u-z_m/ skriva man att det inte är sant. 


Enl den här viden https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function så skriver en man:

 

"That is a consequence of the fact that the totient function is multiplicative. If p is a sufficiently large prime, for instance,
φ(2p) = φ(2) + φ(p) = 1 + (p-1) = p
φ(3p) = φ(3) + φ(p) = 2 + (p-1) = p + 1
φ(5p) = φ(5) + φ(p) = 4 + (p-1) = p + 3
So those lines that you see have slopes of 1/2, 1/3, 1/5, 1/7, 1/11, and so on."

 


Så jag måste veta.. haha. Hur står det till egentligen?

 

Vi tar ett exempel. fi(100) .

det kan man ju göra på kanske dessa alternativ:

  1. fi(100) = 2*fi(50) = 2*fi(25) sen räkna alla som är koprima (eller heter det så?) alltså 2*20 = 40
  2. φ(5p) = φ(5) + φ(p) = 4 + (p-1) = p + 3 blir då för mig: p=20 (eftersom 5*20=100), alltså 23? eller?

2. φ(5p) = φ(5) + φ(p) = 4 + (p-1) = p + 3 blir då för mig: p=20 (eftersom 5*20=100), alltså 23? eller?

Vad har du för värde på p här?

Micimacko 460
Postad: 10 aug 2019 Redigerad: 10 aug 2019

Är inte helt säker på vad du frågar, men jag räknar ut det såhär. Hoppas du ser mönstret, fick inte ihop det i ord 😅. Tänk på att en multiplikativ funktion bara behöver vara det för tal som saknar genemsamma primfaktorer, annars kan lite vad som helst hända.

mrlill_ludde 1057
Postad: 10 aug 2019
Smaragdalena skrev:

2. φ(5p) = φ(5) + φ(p) = 4 + (p-1) = p + 3 blir då för mig: p=20 (eftersom 5*20=100), alltså 23? eller?

Vad har du för värde på p här?

jag antar p=20, eftersom 5p=100?

Micimacko 460
Postad: 10 aug 2019

Står inte p för primtal? Isf är 20 ett dåligt val.

Laguna 6039
Postad: 10 aug 2019

Du skulle kunna titta på den engelska eller svenska wikipedia-sidan också. 

Smaragdalena Online 29168 – Moderator
Postad: 10 aug 2019 Redigerad: 10 aug 2019
mrlill_ludde skrev:
Smaragdalena skrev:

2. φ(5p) = φ(5) + φ(p) = 4 + (p-1) = p + 3 blir då för mig: p=20 (eftersom 5*20=100), alltså 23? eller?

Vad har du för värde på p här?

jag antar p=20, eftersom 5p=100?

Det står i förutsättningarna i satsen att OM p är ett tillräckligt stort primtal, så... Är 20 ett primtal? Kan man alltså använda satsen så som du har gjort?

Albiki 4228
Postad: 10 aug 2019 Redigerad: 10 aug 2019

Om nn är ett positivt heltal så betecknar ϕ(n)\phi(n) antalet positiva heltal (mindre än nn) som är relativt prima med nn; exempelvis är ϕ(10)=4\phi(10) = 4 eftersom talen 1, 3, 7, 9 saknar gemensam delare med 10 (är relativt prima med 10).

Om pp är ett primtal så är alla positiva heltal (mindre än pp) relativt prima med pp, så för ett primtal är ϕ(p)=p-1\phi(p) = p-1.

Albiki 4228
Postad: 10 aug 2019 Redigerad: 10 aug 2019

För varje positivt heltal nn gäller det att

    k·nloglogn<ϕ(n)n-1k\cdot \frac{n}{\log\log n} < \phi(n) \leq n-1

och det finns heltal där den övre gränsen antas (primtalen!) men det finns inte heltal där den nedre gränsen antas (eftersom den nedre gränsen är aldrig ett heltal), där kk är en viss positiv konstant.

mrlill_ludde 1057
Postad: 10 aug 2019 Redigerad: 10 aug 2019
Micimacko skrev:

Står inte p för primtal? Isf är 20 ett dåligt val.

Nvm

Albiki 4228
Postad: 10 aug 2019 Redigerad: 10 aug 2019

Om mm och nn är två positiva heltal så gäller det att

    ϕ(m·n)=ϕ(m)·ϕ(n)·dϕ(d)\phi(m\cdot n)=\phi(m)\cdot\phi(n)\cdot\frac{d}{\phi(d)}

där dd betecknar den största gemensamma delaren till mm och nn; om mm och nn är relativt prima är d=1d = 1 och ϕ(1)=1\phi(1) = 1 varför funktionen ϕ\phi är multiplikativ då den appliceras på heltal som är relativt prima.

Exempelvis är ϕ(2·5)=ϕ(2)·ϕ(5)·dϕ(d)\phi(2\cdot 5) = \phi(2)\cdot \phi(5) \cdot \frac{d}{\phi(d)} men talen 22 och 55 är primtal och saknar därför gemensam delare, utom talet 11 förstås vilket då blir den största gemensamma delaren till 22 och 55, vilket ger ϕ(2·5)=ϕ(2)·ϕ(5).\phi(2\cdot 5) = \phi(2)\cdot \phi(5).22 och 55 är primtal gäller det att ϕ(2)=2-1\phi(2) = 2-1 och ϕ(5)=5-1\phi(5) = 5-1 vilket ger resultatet ϕ(10)=4.\phi(10) = 4.

Albiki 4228
Postad: 10 aug 2019

Det är känt att mängden MM är en tät delmängd av det öppna intervallet (0,1)(0,1). Vad säger detta om funktionen ϕ\phi?

    M={ϕ(n)n:n=1,2,3,}.M = \{\frac{\phi(n)}{n}\,:\, n = 1,2,3,\ldots\}.

Albiki 4228
Postad: 10 aug 2019

Det beräknades att ϕ(10)=4\phi(10) = 4. Finns det något annat positivt heltal med samma ϕ\phi-värde som 1010

mrlill_ludde 1057
Postad: 12 aug 2019
Micimacko skrev:

Är inte helt säker på vad du frågar, men jag räknar ut det såhär. Hoppas du ser mönstret, fick inte ihop det i ord 😅. Tänk på att en multiplikativ funktion bara behöver vara det för tal som saknar genemsamma primfaktorer, annars kan lite vad som helst hända.

Så man primtalsfaktoriserar?

den e jag inte med på, vad e det för formel?

mrlill_ludde 1057
Postad: 12 aug 2019
Albiki skrev:

Det beräknades att ϕ(10)=4\phi(10) = 4. Finns det något annat positivt heltal med samma ϕ\phi-värde som 1010

kan det va alla multiplar?

Albiki 4228
Postad: 12 aug 2019 Redigerad: 12 aug 2019
mrlill_ludde skrev:
Albiki skrev:

Det beräknades att ϕ(10)=4\phi(10) = 4. Finns det något annat positivt heltal med samma ϕ\phi-värde som 1010

kan det va alla multiplar?

Undersök själv. Är ϕ(10·2)=4\phi(10\cdot 2) = 4? För beräkningen kan du utnyttja 10·2=4·510\cdot 2=4\cdot 5; anledningen är att 44 och 55 är relativt prima, men 22 och 1010 är det inte.

Svara Avbryt
Close