Hesaplanıyor $\phi(100)$ nerede $\phi$ sağlam işlev
Soru:
Hesaplamak $\phi(100)$
Girişimim:
Totient fonksiyonunu 100 değerinde hesaplamaya çalıştım, yani:
$$\phi(100)$$
Bunu yapmak için totient fonksiyonunun çarpım kuralını kullandım:
$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$
Yani $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$
= $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$
= 4 $\times$ 4 $\times$ 1 $\times$ 1
= 16.
Karışıklık (eğer yapacaksan)
Bununla birlikte, internette 100'ün sağlam işlevini araştırdığımda, sürekli olarak 40 ile geldi. Bu bana daha uygun bir cevap gibi görünüyor, ancak denememde nerede yanlış yaptığımı tam olarak bilmiyorum. Lütfen bana nerede yanlış yaptığımı söyler misin?
Teşekkürler!
Yanıtlar
Peki, @Arthur bunu yorumlarda benim için açıklığa kavuşturdu, bu yüzden kendi sorumu cevaplayacağım:
$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$, yalnızca a ve b eş-üssü ise .
Öyleyse $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$ çünkü 25 ve 4 eş asallardır, $\phi(100)$ = $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$bu doğru değildir çünkü 2'ler eş asal değildir ve 5'ler de eş asal değildir.
Yani, $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$.
$\phi(25)$ = 20 (Bunu şu formülle değerlendirebiliriz $\phi(p^n) = p^{n-1}(p-1)$yani $ \ phi (5 ^ 2) = 5 ^ {1} (4) = 5 \ times 4 = 20.
$ \ phi (4) $ = 2.
$ \ ima eder$$\phi(100)$ = $20 \times 2$ = 40.
Bunu açıkladığı için @Arthur ve @DreiCleaner'a ve bu yanıtı daha iyi hale getirmek için bazı yollar önerdiği için @JWTanner'a teşekkürler!
Yorumlarda belirtildiği gibi, $5$ ve $5$coprime değildir, bu nedenle burada ürün kuralını kullanamazsınız. Aynısı$2$ ve $2$. İçerdiği rakamlar oldukça küçük olduğu için doğrudan saymayı öneririm.
Bununla birlikte, aynı zamanda basit bir kural vardır. $\phi(a^n)$ ya o aşamada kullanabilirsiniz $\phi(4)$ ve $\phi(25)$veya hemen için $100=10^2$. Bu kuralı görmediyseniz, işte başlamanız için küçük bir işaretçi:
0'dan 10'a kadar kaç tane sayı 10'a eşittir? 10'dan 20'ye ne dersiniz? Peki ya 20'den 30'a? Peki ya [ve diğerleri ...]
Son olarak, coprime ile 10 ve coprime ile 100 arasında bir fark var mı?
Tamam ... kural 1:
Eğer $p$ asal $\phi(p) = p-1$. Bu kadar net olmalı$1$ -e $p-1$ hepsi nispeten asal $p$.
Kural 2:
Eğer $n = p^k$ sonra $\phi(p) = p^{k-1}(p-1)$.
Başlangıçta çok açık değil ama aradaki tüm sayılardan daha fazla düşünürseniz $1$ ve $p^k-1$ formda $q*p + r; 0\le r < p$ -den $p*p + r$ görece asal $r\ne 0$ ve böylece sayılar $q*p + 1, q*p+2, ....q*p+(n-1)$ nispeten asalken $q*p + 0$değil. Her biri için$q$ var $p-1$ bunların $q*p + r; r\ne 0$ ve soru kaç tane kalır $q$var mı? İyi,$q$ kadar küçük olabilir $0$ için $n=1,...., p-1$ ve kadar büyük $p^{k-2}$ için $p^{k-1} +1=p*p^{k-1}+1,.., $ -e $p^k-1 = p*p{k-1} + (p-1)$. yani orada$p^{k-1}$ mümkün $q$ve böylece var $(p-1)\times p^{k-1}$ veya $p^{k-1}(p-1)$ sayılar nispeten asal $p^k$.
Son kural
kural 3: Eğer $\gcd(a,b)=1$ sonra $\phi(ab) = \phi(a)\phi(b)$. Bu diğer kurallarla belirleyebilir$\phi(n)$ tüm pozitif tamsayılar için $n$ asal çarpanlara ayırmayı dikkate alarak $n$. Eğer$n = \prod p_i^{k_i}$ sonra $\phi (n) = \prod \phi(p_i^{k_i}) = \prod( (p-1)p_i^{k_i-1})$.
Yani $\phi (100) = \phi (4)\phi (25)=\phi(2^2) \phi(5^2) = (2-1)2^{2-1}(5-1)25^{2-1} = 2*20 = 40$.
Şimdi kural 3'ün nedeni: kurallara göre ikiye benzer, ancak türetilmesi biraz daha fazla baş ağrısı. Ama yapılabilir.
İşte kaba argüman:
Her şeyden $a$ sayılar $\phi(a)$ bunlardan görece asal olacak $a$ ve $(a-\phi(a))$ onlardan olmayacak.
Yani dışarı $ab$ sayılar $b\phi(a)$ görece asal olacak $a$ ve $(ab - b\phi(a)$ olmayacak.
Her şeyden $b$ sayılar $\phi(b)$ bunlardan görece asal olacak $b$ ve $(b-\phi(b))$ onlardan olmayacak.
Yani dışarı $ab$ sayılar $a\phi(b)$ görece asal olacak $a$ ve $(ab - a\phi(b))$ olmayacak.
Ve dışında $ab$ sayılar $(b-\phi(b))(a-\phi(a))$ikisine de görece asal olmayacak $a$ ne de $b$.
Dahil etme / hariç tutma kullanma
$\phi(ab) =$ görece asal sayıların sayısı $ab$ daha az $ab=$
her ikisi için de göreceli olarak asal olan sayıların sayısı $a$ ve $b=$
Toplam sayı sayısı $ab$ eksi görece asal olmayan sayılar $a$ eksi görece asal olmayan sayı $b$ artı (iki kez saymayı önlemek için) her ikisine de görece asal olmayan sayılar $=$
$ab - (a-\phi(a))b - (b-\phi(b))a + (a-\phi(a))(b-\phi(b) =$
$ab - ab +b\phi(a) -ab +a\phi(b) +ab - b\phi(a) -a\phi(b) + \phi(a)\phi(b) =$
$\phi(a)\phi(b)$
Ta-da.