[b][size=150]＜互いに素＞[br][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][/size][/b][br]「[b]素数[/b]」に似ているけど、便利な言葉「[b]互いに素[/b]」は大切です。[br]最大公約数を求めるすだれ算をするとき、もう１以外の共通の約数がなくなるまで割り算しました。[br]これって、もう共通の約数、公約数という共通点が１しかなくなる状態にするということです。[br]共通な約数が１しかないことを、「[b][color=#0000ff]互いに素[/color][/b]」というのでした。[br]互いに素は、[color=#0000ff][b]「最大公約数が１」[/b][/color]だと言い換えることもできるね。[br]最大公約数を求めるたびに、互いに素のお世話になります。[br]しかし、互いに素はそれ以外に大切な使い道があります。[br][br][b][size=150]＜オイラーのφ関数＞[/size][/b][br]互いに素な数の個数です。[br]たとえば、分母が１０の分数で１以下の分数の分子を並べてみます。[br]１，２，３，４，５，６，７，８，９，１０の１０個あります。[br]このうち、約分できるものを取り除いてみよう。[br]１，３，７，９の４個[br]この４個が１０と１しか公約数がない疎遠な数、[br]１０とは互いに素な数です。[br]１０に対して、１から１０までの数のうち互いに素な整数の個数４を答える関数が[br]オイラーのφ関数です。[br]だから、この場合は、φ(10)=4ですね。[br][br][b][size=150]＜φは割合から＞[br][/size][/b]φ関数のしくみの基本は２つあります。[br]１つめは「[color=#0000ff][b][size=150]素数ｐのφはp-1だ。つまり、φ(p)＝p-1[/size][/b][/color]ということです。」[br]たとえば、[br]１から２までの2数{1,2}のうち、2と互いに素な数は2以外の{1}の１個。φ(2)=1。[br]１から３までの3数{1,2,3}のうち、3と互いに素な数は3以外の{1,2}の２個。φ(3)=2。[br]１から５までの5数{1,2,3,4,5}のうち、5と互いに素な数は5以外の{1,2,3,4}の４個。φ(5)=4。[br]１から素数pまでのp個数{1,2,...,p-1.p}のうち、pと互いに素な数はp以外の{1,2,...,p-1}のp-1個。[br][color=#0000ff][b][size=200]つまり、φ(p)=p-1だね。[/size][/b][/color][br][br]これを割合でイメージすると、あとにつながります。[br]ｐ個中のｐの倍数は１個です。[br]ｐの倍数の割合は[math]\frac{1}{p}[/math]　です。[br]ｐの倍数でない割合は[math]1-\frac{1}{p}[/math] です。[br]素数ｐのｎ乗でもｐの倍数の割合は[math]\frac{1}{p}[/math]なので、ｐの倍数でない割合は[math]1-\frac{1}{p}[/math] ですね。[br]１から２[sup]2[/sup]までの4数{1,2,3,4}のうち、2[sup]2[/sup]と互いに素な数は2と素な{1,3}の2個。[br]φ(2[sup]2[/sup])=4(1-1/2)=2。[br]１から２[sup]3[/sup]までの8数{1,2,3,4,5,6,7,8}のうち、2[sup]3[/sup]と互いに素な数は2と素な{1,3,5,7}の4個。[br]φ(2[sup]3[/sup])=8(1-1/2)=4。[br]１から3[sup]2[/sup]までの9数{1,2,3,4,5,6,7,8,9}のうち、3[sup]2[/sup]と互いに素な数は3と素な{1,2,4,5,7,8}の6個。[br]φ(3[sup]2[/sup])=9(1-1/3)=6。[br]１から3[sup]3[/sup]までの27数{1,2,3,..., 25,26,27}のうち、3[sup]3[/sup]と互いに素な数は3と素な{1,2,...,25,26}の18個。[br]φ(2[sup]3[/sup])=27(1-1/3)=18。[br][br][size=150][b][color=#0000ff]だからφ(p[sup]n[/sup])=p[sup]n[/sup]([/color][/b][math]1-\frac{1}{p}[/math][b][color=#0000ff])=[/color][/b][math]p^n-p^{n-1}[/math][/size]となるね。[br][br][size=150][b]＜互いに素なら割合効果は分離できる＞[br][/b][size=100]φ関数のしくみの基本は２つあります。[/size][/size][br]２つめは「[color=#0000ff][b]２素数p,qの積pqのφは、p,qのφの積だ。つまり、φ(pq)=φ(p)φ(q)[/b][/color]です。[br]１から6までの6数{1,2,3,4,5,6}のうち、２と素な数のうち３と素な数。[br]{1,3,5}のうち３と素な２個。φ(2･3)=6(1-1/2)(1-1/3)=2。[br]言い換えると、φ(2･3)=2(1-1/2)･3(1-1/3)=(2-1)(3-1)=φ(2)φ(3)。[br]１から10までの10数{1,2,3,4,5,6,7,8,9,10}のうち、2と素な数のうち５と素な数。[br]{1,3,5,7,9}のうち5と素な4個。φ(2･5)=10(1-1/2)(1-1/5)=4。[br]言い換えると、φ(2･5)=2(1-1/2)･5(1-1/5)=(2-1)(5-1)=φ(2)φ(5)。[br]１からpqまでのpq数{1,2,..,p-1,p,p+1,.....,pq-1,pq}のうち、pと素な数のうちqと素な数。[br]{1,2,...p-1,p+1,....,pq-1}のうちqと素な(p-1)(q-1)個。[br]φ(p･q)=pq(1-1/p)(1-1/q)=(p-1)(q-1)。[br]言い換えると、φ(p･q)=p(1-1/p)･q(1-1/q)=(p-1)(q-1)=φ(p)φ(q)。[br][b][color=#0000ff][size=150][size=200]だから、φ(pq)=φ(p)φ(q)[br][/size][/size][/color][/b][br][b][size=150]＜オイラー関数の一般形＞[br][/size][/b]整数の素因数分解をｎ＝a[sup]p[/sup]b[sup]q[/sup]c[sup]r[/sup].....とすると、[br][b][size=200][color=#0000ff]φ(n)=φ(a[/color][sup]p[/sup][color=#0000ff])φ(b[/color][sup]q[/sup][color=#0000ff])φ(c[/color][sup]r[/sup][color=#0000ff]).....[b][size=200][color=#0000ff].[/color][/size][/b][br][b][size=200][color=#0000ff] =(a[/color][sup]p[/sup][color=#0000ff])(1-1/a)(b[/color][sup]q[/sup][color=#0000ff])(1-1/b)(c[/color][sup]r[/sup][color=#0000ff])(1-1/c).....[b][size=200][color=#0000ff]...[/color][/size][/b][/color][/size][/b][br][b][size=200][color=#0000ff][b][size=200][color=#0000ff] =(a[/color][sup]p[/sup][color=#0000ff])(b[/color][sup]q[/sup][color=#0000ff])[b][size=200][color=#0000ff][b][size=200][color=#0000ff][b][size=200][color=#0000ff](c[/color][sup]r[/sup][color=#0000ff])[b][size=200][color=#0000ff]...[/color][/size][/b][/color][/size][/b][/color][/size][/b][/color][/size][/b][b][size=200][color=#0000ff](1-1/a)[/color][/size][/b](1-1/b)[/color][color=#0000ff](1-1/c)....[/color][/size][/b][br][/color][/size][/b] = n [b][size=200][color=#0000ff][b][size=200][color=#0000ff][b][size=200][color=#0000ff][b][size=200][color=#0000ff](1-1/a)[/color][/size][/b](1-1/b)[/color][color=#0000ff](1-1/c)....[/color][/size][/b][/color][/size][/b][/color][/size][/b][/color][size=150][br][color=#0000ff][u]質問：geogebraでオイラー関数を作るにはどうしたらよいですか。[br][/u][/color]＜geogebraで作るオイラー関数＞[br][/size][color=#0000ff][size=100][size=150]ps=Unique(PrimeFactors(n)) #素因数分解してユニークな素因数リストを作る[br]zs=Zip(1-1/a,a,ps) #素因数の倍数を除く割合のリストを作る[br]rs=Product(zs) #除く割合をかける[br]eu = n rs #ｎに除く割合の積をかければ、オイラー関数[/size][/size][/color][/size][/b]

[color=#0000ff]#[IN]julia[br]#==========================================================[br]function isPrime(n)[br] lim = Int(round(n^0.5))[br] if n<2[br] return false[br] end[br] for num in 2:lim[br] if n % num ==0 [br] return false[br] end [br] end[br] return true[br]end[br]function eu(n)[br] divs=filter( m -> n % m==0,1:n) #nの約数リスト[br] ps= filter(p -> isPrime(p),divs) #nの素因数リスト[br] zs= [1-1/x for x in ps] #素数の倍数を除く割合リスト[br] return Int(n *prod(zs))[br]end[br]eu(124)[br][/color][color=#0000ff]#==========================================================[br]#[OUT][br][/color]60