mutual Primeの関数
積の法則
１．素数から始めよう
＜互いに素＞
このワークシートはMath by Codeの一部です。
「素数」に似ているけど、便利な言葉「互いに素」は大切です。
最大公約数を求めるすだれ算をするとき、もう１以外の共通の約数がなくなるまで割り算しました。
これって、もう共通の約数、公約数という共通点が１しかなくなる状態にするということです。
共通な約数が１しかないことを、「互いに素」というのでした。
互いに素は、「最大公約数が１」だと言い換えることもできるね。
最大公約数を求めるたびに、互いに素のお世話になります。
しかし、互いに素はそれ以外に大切な使い道があります。
＜オイラーのφ関数＞
互いに素な数の個数です。
たとえば、分母が１０の分数で１以下の分数の分子を並べてみます。
１，２，３，４，５，６，７，８，９，１０の１０個あります。
このうち、約分できるものを取り除いてみよう。
１，３，７，９の４個
この４個が１０と１しか公約数がない疎遠な数、
１０とは互いに素な数です。
１０に対して、１から１０までの数のうち互いに素な整数の個数４を答える関数が
オイラーのφ関数です。
だから、この場合は、φ(10)=4ですね。
＜φは割合から＞
φ関数のしくみの基本は２つあります。
１つめは「素数ｐのφはp-1だ。つまり、φ(p)＝p-1ということです。」
たとえば、
１から２までの2数{1,2}のうち、2と互いに素な数は2以外の{1}の１個。φ(2)=1。
１から３までの3数{1,2,3}のうち、3と互いに素な数は3以外の{1,2}の２個。φ(3)=2。
１から５までの5数{1,2,3,4,5}のうち、5と互いに素な数は5以外の{1,2,3,4}の４個。φ(5)=4。
１から素数pまでのp個数{1,2,...,p-1.p}のうち、pと互いに素な数はp以外の{1,2,...,p-1}のp-1個。
つまり、φ(p)=p-1だね。
これを割合でイメージすると、あとにつながります。
ｐ個中のｐの倍数は１個です。
ｐの倍数の割合は です。
ｐの倍数でない割合は です。
素数ｐのｎ乗でもｐの倍数の割合はなので、ｐの倍数でない割合は ですね。
１から２2までの4数{1,2,3,4}のうち、22と互いに素な数は2と素な{1,3}の2個。
φ(22)=4(1-1/2)=2。
１から２3までの8数{1,2,3,4,5,6,7,8}のうち、23と互いに素な数は2と素な{1,3,5,7}の4個。
φ(23)=8(1-1/2)=4。
１から32までの9数{1,2,3,4,5,6,7,8,9}のうち、32と互いに素な数は3と素な{1,2,4,5,7,8}の6個。
φ(32)=9(1-1/3)=6。
１から33までの27数{1,2,3,..., 25,26,27}のうち、33と互いに素な数は3と素な{1,2,...,25,26}の18個。
φ(23)=27(1-1/3)=18。
だからφ(pn)=pn()=となるね。
＜互いに素なら割合効果は分離できる＞
φ関数のしくみの基本は２つあります。
２つめは「２素数p,qの積pqのφは、p,qのφの積だ。つまり、φ(pq)=φ(p)φ(q)です。
１から6までの6数{1,2,3,4,5,6}のうち、２と素な数のうち３と素な数。
{1,3,5}のうち３と素な２個。φ(2･3)=6(1-1/2)(1-1/3)=2。
言い換えると、φ(2･3)=2(1-1/2)･3(1-1/3)=(2-1)(3-1)=φ(2)φ(3)。
１から10までの10数{1,2,3,4,5,6,7,8,9,10}のうち、2と素な数のうち５と素な数。
{1,3,5,7,9}のうち5と素な4個。φ(2･5)=10(1-1/2)(1-1/5)=4。
言い換えると、φ(2･5)=2(1-1/2)･5(1-1/5)=(2-1)(5-1)=φ(2)φ(5)。
１からpqまでのpq数{1,2,..,p-1,p,p+1,.....,pq-1,pq}のうち、pと素な数のうちqと素な数。
{1,2,...p-1,p+1,....,pq-1}のうちqと素な(p-1)(q-1)個。
φ(p･q)=pq(1-1/p)(1-1/q)=(p-1)(q-1)。
言い換えると、φ(p･q)=p(1-1/p)･q(1-1/q)=(p-1)(q-1)=φ(p)φ(q)。
だから、φ(pq)=φ(p)φ(q)
＜オイラー関数の一般形＞
整数の素因数分解をｎ＝apbqcr.....とすると、
φ(n)=φ(ap)φ(bq)φ(cr)......
=(ap)(1-1/a)(bq)(1-1/b)(cr)(1-1/c)........
=(ap)(bq)(cr)...(1-1/a)(1-1/b)(1-1/c)....
= n (1-1/a)(1-1/b)(1-1/c)....
質問：geogebraでオイラー関数を作るにはどうしたらよいですか。
＜geogebraで作るオイラー関数＞
ps=Unique(PrimeFactors(n)) #素因数分解してユニークな素因数リストを作る
zs=Zip(1-1/a,a,ps) #素因数の倍数を除く割合のリストを作る
rs=Product(zs) #除く割合をかける
eu = n rs #ｎに除く割合の積をかければ、オイラー関数
geogebraでもφ関数
２．juliaでオイラー関数
#[IN]julia
#==========================================================
function isPrime(n)
lim = Int(round(n^0.5))
if n<2
return false
end
for num in 2:lim
if n % num ==0
return false
end
end
return true
end
function eu(n)
divs=filter( m -> n % m==0,1:n) #nの約数リスト
ps= filter(p -> isPrime(p),divs) #nの素因数リスト
zs= [1-1/x for x in ps] #素数の倍数を除く割合リスト
return Int(n *prod(zs))
end
eu(124)
#==========================================================
#[OUT]
60