あくまで備忘録なんで雑に記録しますオイラーのトーシェント関数
正の整数 n に対して、 n と互いに素である 1 以上 n 以下の自然数の個数 φ(n)
１２なら、１ ５ ７ １１ ＝ ４個
12 * ( 1 − 1/2 )( 1 − 1/3 ) = 4 （１ー素因数の逆数）を全部かける
p, q 互いに素の場合の、１〜ｐ＊ｑとの互いに素の個数
φ(n) = (p – 1) * (q – 1)
(p, q) = (3, 5) なら８個 （1 2 4 7 8 11 13 14）
エラトステネスの篩みたいに考えても良いかも
コメント