差分

このページの2つのバージョン間の差分を表示します。

この比較画面にリンクする

log:competitive:phi [2018/12/26 14:49]
127.0.0.1 外部編集
log:competitive:phi [2020/04/13 13:23] (現在)
にこなのにふわわあ
行 18: 行 18:
  
 ## できること ## できること
-$\displaystyle a^{p-1}\equiv 1{\pmod {p}}(フェルマーの小定理)+\a^{p-1}\equiv 1{\pmod {p}}\] 
 +(フェルマーの小定理)
  
 後にオイラーはこの定理を拡張した. 後にオイラーはこの定理を拡張した.
 a を n と*互いに素な整数のとき*これが成り立つ. a を n と*互いに素な整数のとき*これが成り立つ.
 (nは素数でなくても良い.) (nは素数でなくても良い.)
-$\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}$+\a^{\varphi (n)}\equiv 1{\pmod {n}}\]
  
 そこで, そこで,
-$\displaystyle a^b \equiv a^{b \mod \phi(n)} \pmod {n}$+\a^b \equiv a^{b \mod \phi(n)} \pmod {n}\]
 が成り立つ.これによって大きな数の冪乗が小さいオーダーで可能となる. が成り立つ.これによって大きな数の冪乗が小さいオーダーで可能となる.
  
最終更新: 2020/04/13 13:23