FrontPage
オイラーの
関数 †
- nを正整数とするとき,1からnまでの整数で,nと互いに素となるものの個数をφ(n)と表す.
整数nとaとが互いに素とは,それらの最大公約数が1となることでもある.
- m,nが互いに素であるとき
![\phi(mn)=\phi(m)\phi(n) \phi(mn)=\phi(m)\phi(n)](./teximg/d920c7f81c3871381c64497f93a660c13b05b2f18ce46f0ada0bd65ba15125c6.png)
(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) \phi(n)=n \left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\cdots\left(1-\frac{1}{r}\right)](./teximg/e85768d2002dda0cfec4d8a374ec6f583b05b2f18ce46f0ada0bd65ba15125c6.png)
- オイラーの定理
nを正整数,aをnと互いに素な整数とする.このとき
![a^{\phi(n)} \equiv 1 \pmod n a^{\phi(n)} \equiv 1 \pmod n](./teximg/4693b455388c614246b244df9bcaf83c3b05b2f18ce46f0ada0bd65ba15125c6.png)
が成立する.
- n=p(素数のとき),φ(p)=p−1であるから
![a^{p-1} \equiv 1 \pmod p a^{p-1} \equiv 1 \pmod p](./teximg/48e038b9b05f04b4ee163116a1964b8d3b05b2f18ce46f0ada0bd65ba15125c6.png)
が成立する.これはフェルマーの小定理とよばれている.
参考 †
オイラー関数(kamelink) /
wikipedia /
青空学園 /
オイラー関数とオイラーの定理 /
kyの書架
入試問題 †
問題文をクリックすると解答をみることができます.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
(1)pのn乗以下の自然数からpのn乗と互いに素でないものを除きましょう.
(2)背理法を用いましょう.与えられた条件はhと互いに素なh未満の自然数は6個以下ということです.
(3)は2と3はhと互いに素でないことに着目します.すなわち,2と3はhの素因数です.
φ(mn)=φ(m)φ(n)については「ここ」を参照してください.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](https://kamelink.com/public/2015/1.7-15%E4%B8%80%E6%A9%8B%E5%A4%A7%E3%83%BB1problem.png)
E(n)はオイラーのファイ関数,略してオイラー(Euler)関数と呼ばれるものです.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
N=84773093 がどのように素因数分解されるか直ちに判断するのは困難ですが,
φ(N)を知ると(3)のようにして素因数分解することができます.
φ(N)は暗号理論で利用されています.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
φ(n) はオイラーのファイ関数と呼ばれていています.
n(=10,100,1500)を素因数分解し,1からnまでの自然数から
nと互いに素でない(nの約数となる)数を除くことを考えます.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
nとの最大公約数が1である自然数ということは,nと互いに素な自然数ということです.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
f(n)はファイ関数と呼ばれています.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
f(n)はオイラーのファイ関数(トーシェント関数)と呼ばれているものです.
f(n)は n と互いに素な n 以下の自然数の個数を表しています.
![問題文をクリックしてみて下さい. 問題文をクリックしてみて下さい.](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)
f(n) はファイ関数と呼ばれています.
(2)から(3)が面白い.