アルゴリズム論特論（塩田）　2016年度教材　第5回

  • 授業内容
    • 法 n での除算
    • 剰余類
    • 既約剰余類
    • フェルマの小定理の別証明
    • オイラーの定理
      • φ(n) = ( 法 n の既約剰余類の個数 ) とすると
              gcd(a, n) = 1 ⇒ 法 n で a φ(n) = 1

  • ツボ
    • 法 n で a の逆数が存在すること ⇔ gcd(a, n) = 1

戻る