WisFaq!

Chinese reststelling

Als ggd(m, n) = 1, dan geldt φ(m)× φ (n) = φ (m. n).

De vraag is:

• Geef hiervan een bewijs, waarbij je de Chinese reststelling gebruikt en de definitie van φ (n) als het aantal elementen tussen 0 en n relatief priem met n.

Heeft iemand hier een idee hoe deze vraag wordt aangepakt en bewijzen? Er staat iets van Chinese reststelling en de definitie van phi en de samenhang,... , maar hoe zal ik het bewijzen. Dat zie ik niet.

M
27-4-2020

Antwoord

We starten met de verzamelingen die bij de $\varphi$-functie horen:

• Laat $A$ de verzameling zijn van positieve getallen relatief priem met $m$ en kleiner dan $m$.
  
• Laat $B$ de verzameling zijn van positieve getallen relatief priem met $n$ en kleiner dan $n$.
  
• Laat tenslotte $C$ de verzameling zijn van positieve getallen relatief priem met $m\cdot n$ en kleiner dan $m\cdot n$.
  

Neem een $a \in A$ en $b \in B$. Vanuit de Chinese reststelling weten we dat er $c$ zijn zodat $c \equiv a\:(\mathrm{mod}\:m)$ en $c \equiv b \:(\mathrm{mod}\:n)$ en ook dat $c$ in een unieke restklasse valt modulo $m \cdot n$, die een representant $c'$ heeft met $0$<$c'$<$m\cdot n$. Verder is $c$ relatief priem met $n\cdot m$. Dat betekent dus dat bij elk paar $(a,b) \in A \times B$ een element $c' \in C$ hoort.

Andersom Nemen we $c \in C$. Er geldt dat $c$ relatief priem is met $m$ zowel als $n$. Dus er zijn $a \in A$ en $b \in B$ met $a \equiv c\:(\mathrm{mod}\:m)$ en $b \equiv c\:(\mathrm{mod}\:n)$. Dus bij elke $c \in C$ hoort een paar $(a,b) \in A \times B$.

We hebben dus een bijectie tussen $A \times B$ en $C$. Deze verzamelingen hebben dus evenveel elementen en dat bewijst je stelling dat $\varphi$ multiplicatief is.

Met vriendelijke groet,

FvL
27-4-2020