Euler φ(fi) Fonksiyonunun Kombinatorik Kanıtı
İsviçreli büyük matematikçi Leonhard Euler'e ait, φ(phi) fonksiyonu için yapılmış farklı kanıtlar vardır. Bu yazıda diğer kanıtlarına göre daha "anlaşılır" olan kombinatorik yöntemle kanıtını göstereceğiz. Önce fonksiyonumuzun tanımını yapalım.
Teorem: 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 adedine eşittir. Matematiksel biçimde ifade edilmesi gerekirse;
{ 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. Aradığımız sayı kümesinin eleman sayısıyla, tanımladığımız kümelerinin birleşiminin eleman sayısının farkına eşit olur.
kümelerin eleman sayıları sırasıyla,
, , ... ,
olur. Bu kümelerin kesişim kümelerinin eleman sayıları ise,
,..., , ... ,
şeklindedir. Buradan kümelerin birleşiminin eleman sayısı içindelik dışındalık prensibinden;
eşitliğiyle hesaplanır. Toplam ifadelerini listeleyelim:
.
.
.
Formülde geçen toplam ifadelerini yerlerine yazalım bu du durumda genel toplam:
ifadesine eşit olur. Aradığımız sonuç
olduğundan,
biçiminde yazılır. Eşitliğin sağ tarafını parantezine alarak derleyelim.
şimdi parantezlerin içinde bulunan kesirli toplam sonuçlarını uygun şekilde yazalım.
son olarak sayısını:
şeklinde yazalım. Bu adımdan sonra ortak paydada yazılan ifadeleri toplayalım.
kesirli ifadenin pay kısmı dikkate alınarak
çarpımına odaklanalım! Bu çarpımın sonucu
pay kısmında bulunan ifadeye eşit olur. Burada kesirli ifadenin pay kısmına eşitliğin sol tarafındaki çarpanlara ayrılmış hali yazılırsa:
olur. Çarpım durumundaki pay ve payda aşağıdaki gibi parçalara ayrılır:
son olarak parantez içleri teoremdeki haliyle yazılırsa
sonucuna ulaşılır. Böylece kanıt tamamlanmıştır.
Bu yazının konusu Ali Nesin'in "Sayma" isimli kitabında bulunan okuyucuya yöneltilen problemlerden alınmıştır. (Syf. 103, Problem 19)
Bilal DEMİR Matematik Öğretmeni