![[PukiWiki]](image/kame.png "[PukiWiki]")
#author("2019-09-25T16:03:45+09:00","","") [[FrontPage]] *オイラーの $\phi$ 関数 [#w0588885] -ｎを正整数とするとき，１からｎまでの整数で，ｎと互いに素となるものの個数をφ（ｎ）と表す．~ 整数ｎとａとが互いに素とは，それらの最大公約数が１となることでもある．~ -m，nが互いに素であるとき~ $\phi(mn)=\phi(m)\phi(n)$ -$n=p^aq^b\ \cdots\ r^c$ (p，q，…，rは素数a，b，… ，cは自然数) のとき~ $\phi(n)=n \left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\cdots\left(1-\frac{1}{r}\right) $ -''オイラーの定理'' ｎを正整数，ａをｎと互いに素な整数とする．このとき~ $a^{\phi(n)} \equiv 1 \pmod n$~ //$ａ^{\phi(n)} \equiv 1 \mod(n)$~ が成立する． --n=p(素数のとき)，φ（ｐ）＝ｐ−１であるから~ $a^{p-1} \equiv 1 \pmod p$~ が成立する．これは''フェルマーの小定理''とよばれている． *参考 [#d709be9a] [[オイラー関数(kamelink):https://kamelink.com/public/others/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E9%96%A2%E6%95%B0.pdf]] / [[wikipedia:http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0]] / //[[takeuchi:http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler.html]] / [[青空学園:http://aozoragakuen.sakura.ne.jp/suuron/node26.html]] / [[オイラー関数とオイラーの定理:http://www.tcp-ip.or.jp/~n01/math/euler.pdf]] / [[kyの書架:http://kynoshoka.com/eulerfunc.pdf]] *入試問題 [#jb32b96e] 問題文を''クリック''すると解答をみることができます． //1.7-19大阪市大・後理(数)6.tex [[&ref(https://kamelink.com/public/2019/1.7-19%E5%A4%A7%E9%98%AA%E5%B8%82%E5%A4%A7%E3%83%BB%E5%BE%8C%E7%90%86(%E6%95%B0)6problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/2019/1.7-19%E5%A4%A7%E9%98%AA%E5%B8%82%E5%A4%A7%E3%83%BB%E5%BE%8C%E7%90%86(%E6%95%B0)6.pdf]] (1)pのn乗以下の自然数からpのn乗と互いに素でないものを除きましょう．~ (2)背理法を用いましょう．与えられた条件はhと互いに素なh未満の自然数は6個以下ということです．~ (3)は2と3はhと互いに素でないことに着目します．すなわち，2と3はhの素因数です．~ φ(mn)=φ(m)φ(n)については[[「ここ」:https://kamelink.com/public/others/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E9%96%A2%E6%95%B0.pdf]]を参照してください． //1.7-15一橋大・1.tex [[&ref(https://kamelink.com/public/2015/1.7-15%E4%B8%80%E6%A9%8B%E5%A4%A7%E3%83%BB1problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/2015/1.7-15%E4%B8%80%E6%A9%8B%E5%A4%A7%E3%83%BB1.pdf]] E(n)はオイラーのファイ関数，略してオイラー(Euler)関数と呼ばれるものです． //1.7-06横浜市大・医2.tex [[&ref(https://kamelink.com/public/2006/1.7-06%E6%A8%AA%E6%B5%9C%E5%B8%82%E5%A4%A7%E3%83%BB%E5%8C%BB2problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/2006/1.7-06%E6%A8%AA%E6%B5%9C%E5%B8%82%E5%A4%A7%E3%83%BB%E5%8C%BB2.pdf]] N=84773093 がどのように素因数分解されるか直ちに判断するのは困難ですが，~ φ(N)を知ると(3)のようにして素因数分解することができます．~ φ(N)は暗号理論で利用されています． //1.7-05佐賀大・理工1.tex [[&ref(https://kamelink.com/public/2005/1.7-05%E4%BD%90%E8%B3%80%E5%A4%A7%E3%83%BB%E7%90%86%E5%B7%A51problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/2005/1.7-05%E4%BD%90%E8%B3%80%E5%A4%A7%E3%83%BB%E7%90%86%E5%B7%A51.pdf]] φ(n) はオイラーのファイ関数と呼ばれていています．~ ｎ(=10，100，1500)を素因数分解し，１からｎまでの自然数から~ ｎと互いに素でない(ｎの約数となる)数を除くことを考えます． //1.7-05早稲田大・社会科学3.tex [[&ref(https://kamelink.com/public/2005/1.7-05%E6%97%A9%E7%A8%B2%E7%94%B0%E5%A4%A7%E3%83%BB%E7%A4%BE%E4%BC%9A%E7%A7%91%E5%AD%A63problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/2005/1.7-05%E6%97%A9%E7%A8%B2%E7%94%B0%E5%A4%A7%E3%83%BB%E7%A4%BE%E4%BC%9A%E7%A7%91%E5%AD%A63.pdf]] ｎとの最大公約数が1である自然数ということは，ｎと互いに素な自然数ということです． // $n$ 以下の自然数で $n$ との最大公約数が 1 であるような自然数の個数を $f(n)$ としたときの $f(77)$，$f(2^k3^n)$ //1.7-03名古屋大・文系3.tex [[&ref(https://kamelink.com/public/2003/1.7-03%E5%90%8D%E5%8F%A4%E5%B1%8B%E5%A4%A7%E3%83%BB%E6%96%87%E7%B3%BB3problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/2003/1.7-03%E5%90%8D%E5%8F%A4%E5%B1%8B%E5%A4%A7%E3%83%BB%E6%96%87%E7%B3%BB3.pdf]] f(n)はファイ関数と呼ばれています． //f(15),f(pq) /[[受験の月:http://examist.jp/mathematics/integer/totient-function/]] //1.7-93横浜市大・医・文理2.tex [[&ref(https://kamelink.com/public/1993/1.7-93%E6%A8%AA%E6%B5%9C%E5%B8%82%E5%A4%A7%E3%83%BB%E5%8C%BB%E3%83%BB%E6%96%87%E7%90%862problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/1993/1.7-93%E6%A8%AA%E6%B5%9C%E5%B8%82%E5%A4%A7%E3%83%BB%E5%8C%BB%E3%83%BB%E6%96%87%E7%90%862.pdf]] f(n)はオイラーのファイ関数(トーシェント関数)と呼ばれているものです．~ f(n)は n と互いに素な n 以下の自然数の個数を表しています． //1.7-92埼玉大・後理・工1.tex [[&ref(https://kamelink.com/public/1992/1.7-92%E5%9F%BC%E7%8E%89%E5%A4%A7%E3%83%BB%E5%BE%8C%E7%90%86%E3%83%BB%E5%B7%A51problem.png,nolink,70%,問題文をクリックしてみて下さい．);>https://kamelink.com/public/1992/1.7-92%E5%9F%BC%E7%8E%89%E5%A4%A7%E3%83%BB%E5%BE%8C%E7%90%86%E3%83%BB%E5%B7%A51.pdf]] f(n) はファイ関数と呼ばれています．~ (2)から(3)が面白い． //f(12)，f(13)，f(14)；m と n-m，f(n) は偶数であること
