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. 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. sayıları sayısının asal çarpanları olmak üzere 'den küçük ve asal çarpanların tam katı olan elemanların oluşturduğu kümeleri sırasıyla:
.
.
.
şeklinde tanımlayalım. Aradığımız sayılar, kümesiyle tanımladığımız kümelerinin birleşiminin fark kümesinde bulunurlar.
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:
.
.
.
eşitliklerde geçen toplam ifadelerinin yerlerine bunların açılmış hallerini yazıp toplanırsa:
ifadesi elde edilir. Aradığımız sayı,
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