tallteori

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

Svar
Gjestebruker

bevis at [tex]\phi(n)=n\prod_{p|n}(1-\frac{1}{p})[/tex]
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Lemma: Hvis $\gcd(m,n)=1$ er $\varphi(mn)=\varphi(m)\varphi(n)$.
Bevis. Siden $\gcd(m,n)=1$ er $\mathbb{Z}_{mn}$ og $\mathbb{Z}_{m}\times \mathbb{Z}_n$ isomorfe som ringer. Dermed har de like mange enheter. Enheter av en ring $R$ danner en multiplikativ gruppe $U(R)$, og i tilfellet $\mathbb{Z}_{\ell}$ blir dette $U(\mathbb{Z}_{\ell})=\{x \in \mathbb{Z}_{\ell} : \exists y \in \mathbb{Z}_{\ell} \text{ slik at } xy \equiv 1 \pmod{\ell}\} = \{x \in \mathbb{Z}_{\ell} : \gcd(y,x)=1\}$. Observer at dette nettopp er alle tall som er relativt primisk til $x$. Dermed er ordenen til denne gruppen nettopp $\varphi(\ell)$. Det følger at $\varphi(mn)=|U(\mathbb{Z}_{mn})|=|U(\mathbb{Z}_m \times \mathbb{Z}_n )|=|U(\mathbb{Z}_m)| |U(\mathbb{Z}_n)| = \varphi(m)\varphi(n)$.

Nå beviser vi formelen. La $n=\prod_{i=1}^t p_i^{r_i}$. Ved gjentatt bruk av lemmaet over får vi $$\varphi(n)=\varphi \left( \prod_{i=1}^t p_i^{r_i} \right) = \prod_{i=1}^t \varphi \left(p_i^{r_i} \right)=\prod_{i=1}^t p_i^{r_i-1}(p_i-1) = \prod_{i=1}^t p_i^{r_i} \prod_{i=1}^t \frac{p_i-1}{p_i} = n \prod_{i=1}^t \left(1-\frac{1}{p_i} \right) = n\prod_{p\mid n} \left( 1- \frac1p \right)$$
Gjestebruker

veldig pent utført
se om du tar den andre oppgaven og
Svar