De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Functie van Euler

In verband met een bewijs van het RSA algoritme, was ik op zoek naar een bewijs voor de functie van Euler, toegepast op RSA. Weet iemand hoe ik het volgende kan bewijzen:

f(pq) = f(p) x f(q) ??
met p en q beide priemgetallen.
f(p) = p-1 en q(q) = q-1
en voor RSA heb ik nodig dat f(pq) = (p-1)(q-1)
Vandaar bovengestelde vergelijking.

Een andere weg waarvan ik het opstapje wel heb, maar eigenlijk nog geen volledig bewijs is:
Een getal n met n = pq (p en q weer priemgetallen)
Uit een aantal voorbeelden blijkt dan te gelden:
f(n) = pq-p-q+1 = f(pq) = (p-1)(q-1)
Maar ook hier heb ik moeite met het formuleren van een kloppend bewijs.. ??

Thnx!

Jop
Leerling bovenbouw havo-vwo - zaterdag 18 december 2010

Antwoord

Probeer het eens met de definitie en tel het aantal getallen in {0,1,...pq-1} die een ggd van 1 met pq hebben; dat zijn in dit geval precies de getallen die geen veelvoud van p of q zijn.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 19 december 2010
 Re: Functie van Euler 



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3