FrontPage

オイラーの \phi 関数

  • nを正整数とするとき,1からnまでの整数で,nと互いに素となるものの個数をφ(n)と表す.
    整数nとaとが互いに素とは,それらの最大公約数が1となることでもある.
  • 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)
  • オイラーの定理 nを正整数,aをnと互いに素な整数とする.このとき
    a^{\phi(n)} \equiv 1 \pmod n
    が成立する.
  • n=p(素数のとき),φ(p)=p−1であるから
    a^{p-1} \equiv 1 \pmod p
    が成立する.これはフェルマーの小定理とよばれている.

参考

オイラー関数(kamelink) / wikipedia / 青空学園 / オイラー関数とオイラーの定理 / kyの書架

入試問題

問題文をクリックすると解答をみることができます.

問題文をクリックしてみて下さい.

(1)pのn乗以下の自然数からpのn乗と互いに素でないものを除きましょう.
(2)背理法を用いましょう.与えられた条件はhと互いに素なh未満の自然数は6個以下ということです.
(3)は2と3はhと互いに素でないことに着目します.すなわち,2と3はhの素因数です.
φ(mn)=φ(m)φ(n)については「ここ」を参照してください.

問題文をクリックしてみて下さい.

E(n)はオイラーのファイ関数,略してオイラー(Euler)関数と呼ばれるものです.

問題文をクリックしてみて下さい.

N=84773093 がどのように素因数分解されるか直ちに判断するのは困難ですが,
φ(N)を知ると(3)のようにして素因数分解することができます.
φ(N)は暗号理論で利用されています.

問題文をクリックしてみて下さい.

φ(n) はオイラーのファイ関数と呼ばれていています.
n(=10,100,1500)を素因数分解し,1からnまでの自然数から
nと互いに素でない(nの約数となる)数を除くことを考えます.

問題文をクリックしてみて下さい.

nとの最大公約数が1である自然数ということは,nと互いに素な自然数ということです.

問題文をクリックしてみて下さい.

f(n)はファイ関数と呼ばれています.

問題文をクリックしてみて下さい.

f(n)はオイラーのファイ関数(トーシェント関数)と呼ばれているものです.
f(n)は n と互いに素な n 以下の自然数の個数を表しています.

問題文をクリックしてみて下さい.

f(n) はファイ関数と呼ばれています.
(2)から(3)が面白い.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-09-25 (水) 16:03:45 (1646d)