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}

Chinese reststelling

Te bewijzen: Als GGD (m,n) = 1, dan geldt F(m) X F(n) = F(mn)

Ik kon een soortgelijke uitwerking vinden maar kwam helaas niet verder. Ik weet dat om multiplicatie aan te tonen ik moet aantonen dat bovenstaande bijectief is. Ik bekijk twee verzamelingen een verzameling A en een verzameling B.

Verzameling A: ( aA | 1$\le$a$\le$mn ^ GGD (a,mn) = 1 )
Verzameling B: ( b,c B | 1$\le$b$\le$m ^ 1$\le$c$\le$n ^ GGD (b,m) = 1 ^ GGD(c,n) = 1 )

Hieruit volgt dan toch dat: a = n(mod m) & a = m(mod n)
Waarbij de resten elementen zijn van verzameling B.


Als ik dit verder uit werk krijg ik: a = b (mod n) & a = c(mod m), nu is GGD (m,n) = 1 en heb ik dat gegeven bewezen wat bewezen moest worden.

Het vetgedrukt is de stap waarvan ik niet begrijp dat het niet klopt, ik ben niet opzoek naar een antwoord maar graag een uitleg.

Albert
Student universiteit - dinsdag 2 juni 2020

Antwoord

Als ik het goed begrijp gaat het over de totient-functie van Euler. Je schrijft niet echt duidelijk: in het `bovenstaande' zie ik geen afbeelding die bijectief zou kunnen zijn; de definities van $A$ en $B$ verdienen niet de schoonheidsprijs. En in je vetgedrukte regels staat een ongespecificeerde $a$, vermoedelijk uit $A$, maar dan hoeft die echt niet gelijk te zijn aan $n\pmod m$ en $m\pmod n$ tegelijk.
En waar komen die $b$ en die $c$ vandaan? Je hebt nog helemaal niets bewezen.

Maar goed:
de titel van je vraag is de selutel tot de oplossing.
De Chinese Reststelling impliceert dat $a\mapsto\bigl(a\bmod m,a\bmod n\bigr)$ een bijectie is tussen $\{i:0\le i < mn\}$ en de productverzameling $\{j:0\le j < m\}\times\{k:0\le k < n\}$.

Nu moet je verifieren: als $\mathrm{ggd}(i,mn)=1$ dan ook $\mathrm{ggd}(j,m)=\mathrm{ggd}(k,n)=1$, waarbij $j=i\bmod m$ en $k=i\bmod n$.

En omgekeerd: als $\mathrm{ggd}(j,m)=\mathrm{ggd}(k,n)=1$, waarbij $j=i\bmod m$ en $k=i\bmod n$ dan ook $\mathrm{ggd}(i,mn)=1$

Dan heb je een bijectie tussen de correcte versies van jouw verzamelingen $A$ en $B$.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 2 juni 2020



klein |  normaal |  groot

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

©2001-2020 WisFaq - versie IIb