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: ( a€A | 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 sleutel 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$.

Zie Wikipedia: Indicator

kphart
dinsdag 2 juni 2020

©2001-2024 WisFaq