$\phi(n)$, n'in Euler fonksiyonu olsun. $1\leq a\leq n$ olmak üzere $(a,n)=1$ koşulunu sağlayan $a$ doğal sayılarının kümesine $M$ diyelim. $M$ kümesinin elemanları toplamı $\frac{n.\phi(n)}{2}$ dir.
Not:Sayılar teorisinde böyle bir teorem olduğunu hatırlamıyorum. Bir problemle uğraşırken geliştirdim.
İspat:
$n=p_1^{r_1}.p_2^{r_2}.p_3^{r_3}...p_k^{r_k}$ olsun. Burada $1\leq i\leq k$, her $r_i$ bir doğal sayı ve her $p_i$ bir asal sayıdır.
Ayrıca $p_1<p_2<p_3<...<p_k$ olduğunu düşünelim. $\phi(n)$ çarpımsal bir fonksiyon olduğundan,
$\phi(n)=\phi(p_1^{r_1}.p_2^{r_2}.p_3^{r_3}...p_k^{r_k})=\phi(p_1^{r_1}).\phi(p_2^{r_2}).\phi(p_3^{r_3})...\phi(p_k^{r_k})$ ve bunları da,
$\phi(n)=p_1^{r_1-1}(p_1-1).p_2^{r_2-1}(p_2-1).p_3^{r_3-1}(p_3-1)...p_k^{r_k-1}(p_k-1)$ olur. Burada $p_1=2$ olduğundan $p_1-1=1$ olup diğer $p_i-1$ ler birer çift sayıdır. O halde $n\geq3$ için $\phi(n)$ daima çift bir doğal sayıdır.
Şimdi $n>a$ olsun ve $OBEB(n,a)$ yerine $(n,a)$ 'yi kullanalım.
Önsav: Eğer $(n,a)=1 \Leftrightarrow (n,n-a)=1$ dir.
ispat:(gerek şart) :
$(n,a)=1 $ ise $ xn+ya=1$ olacak şekilde $x,y\in \mathbb{Z}$ tam sayıları vardır.
$ xn+ya+ax-ax=1\rightarrow (n-a)x+a(y+x)=1$ olur ve $x,(y+x)\in\mathbb{Z}$ olduğundan $(n-a,a)=1$ olacaktır. Benzer olarak $k,t\in Z$ için $k.(n-a)+ta=1\rightarrow (k-t)(n-a)+t.n=1 \Rightarrow (n-a,n)=1 $ yazılabilir.
(yeter koşul): $(n-a,n)=1$ olsun. Benzer olarak $(n-a).k+n.t=1$ koşulunu sağlayan en az iki $k,t\in\mathbb{Z}$ tam sayıları vardır. Buradan $nk-ak+nt=1\Rightarrow (k+t)n+(-k)a=1\Rightarrow (n,a)=1$ dir.
Şimdi $1\leq a\leq n$ ve $(n,a)=1$ olan $ a$ doğal sayılarının sayısının $\phi(n)$ kadar olduğunu ve $n\geq 3$ için $\phi(n)$'in daima çift olduğunu artık biliyoruz. Bu $a$ sayılarının kümesine $M$ diyelim. Biz $M$ nin elemanlarının toplamının $\frac{n.\phi(n)}{2}$ kadar olduğunu göstereceğiz.
$M$ kümesi $[1,n)$ aralığındaki $n$ ile aralarında asal olan bütün doğal sayıları içerdiğinden,
eğer $a\in M$ ise tanımdan dolayı $(n,a)=1$ dir.
Öte yandan $n-a<n$ ve $(n-a,n)=1$ olduğundan $(n-a)\in M$ demektir.
Yani her $a\in M$ için bir $n-a\in M$ vardır ki $(n,n-a)=1$ dir.
$\phi(n)$ 'in eleman sayı çift olduğundan bu $(a,n-a)$ ikililerinin sayısı $\frac{\phi(n)}{2}$ kadardır. Bu şekildeki herbir ikilinin toplamı $a+n-a=n$ olduğundan, $M$ 'nin elemanları toplamı $\frac{\phi(n)}{2}.n$ dir.