Euler φ(fi) Fonksiyonunun Kombinatorik Kanıtı

İsviçreli büyük Matematikçi Leonhard Euler(1707-1783) tarafından ortaya konulan, sayılar teorisinde büyük öneme sahip olan, meşhur φ fonksiyonu için yapılmış farklı kanıtlar vardır. Bu yazıda anlaşılması görece diğer kanıtlara göre daha kolay olan kombinatorik yöntemle kanıtını göstereceğiz. Önce fonksiyonumuzun tanımını yapalım. Tanım: bir doğal sayı olsun. asal sayıları birbirinden farklı ve n'yi bölen tüm asal sayılar olmak üzere; sayısı n'den küçük ve n ile aralarında asal olan doğal sayıların sayısına eşittir. Daha matematiksel şekilde ifade edecek olursak; { ve ve aralarında asal } kümesinin eleman sayısına eşittir. Kanıt: 1'den n'ye kadar doğal sayılar kümesi olarak yazalım. Öncelikle, . . . Kümelerini tanımlayalım. İstediğimiz sayıyı bulmak için kümesinin eleman sayısından tanımladığımız kümelerinin birleşiminin eleman sayısını çıkarmalıyız. Temel sayma bilgilerimizden tanımladığımız kümelerin eleman sayıları sırasıyla, , , ... , olur. Bu kümelerin kesişim kümelerinin eleman sayıları ise, ,..., , ... , bulunur. Bu kümelerin birleşiminin eleman sayısı içindelik dışındalık prensibinden; ile hesaplanır. Toplam ifadelerini listeleyelim: . . . Formülümüzde geçen toplam ifadelerini yerlerine yazarsak genel toplamımız şeklinde olur. Bulmak istediğimiz sayı olduğundan, olur. Elde ettiğimiz toplamı biraz işlem ve düzenleme yaparak daha anlaşılır bir biçime dönüştürmeye çalışalım. Önce tüm ifadelerde ortak olarak bulunduğu için parantezine alalım. Şimdi parantezlerde bulunan kesirli toplam işlemlerini düzenleyelim. . . . Son olarak sayısını, olarak yazalım. Şimdi ortak bir paydada yazdığımız ifadeleri toplayalım. İfademizin payına dikkat ederek. çarpımına odaklanalım! Bu çarpımın sonucu tahmin edileceği üzere; İfademizin payına eşittir. Öyle ise daha derli toplu olan çarpımları paya yazalım. Bu ifadeyi, Şeklinde yazabiliriz. Son olarak bu ifadede parantezler içindeki işlemleri yapacak olursak , olarak bulunur. Kanıt tamamlanmıştır.