整数論

Fermatの小定理 Eulerの定理 Carmichaelの定理

競技プログラミングでは を用いた数え上げ問題が頻出します。このとき途中で割り算を用いますが、計算途中のオーバフローを避けるためモジュラ逆数というものを使いますが、このモジュラ逆数はFermat*1の小定理やEuler*2の定理といったものを利用して計算さ…

Carmichael函数はEulerのトーシェント函数の約数

Carmichael*1函数はCarmichaelの定理に出てくる函数ですが、逆にこれ以外では出てこないと思います。しかし、定義が少し煩雑であるのと、この函数が返す値がEuler*2のトーシェント函数の与える値の約数になっていることについての証明をしたいので1つの記事…

Eulerのトーシェント函数

Euler*1のトーシェント函数*2とは主に と表記される、整数論における函数です。次のように定義されます。 $$ \varphi(n) = \#\{k \mid 1 \leq k \leq n,\ \gcd(n,\,k) = 1\} $$ 日本語で書くと から までの整数のうち、 と互いに素な整数の個数となります。 …

中国剰余定理 (ABC193-E Oversleeping)

ABC193のE問題は連立合同式についての問題でした。これは中国式剰余定理によって解を求めるものです。他にも拡張Eulerの定理についての証明においても中国式剰余定理は登場します。 名前と背景 定理の主張 証明(互いに素、二元のとき) 解の存在 解の一意性 …

拡張Eulerの定理(互いに素ではない場合) ARC113-B A^B^C

ARC113のB問題は としたとき の列が4(の約数)の周期で循環すること、 の列が2(の約数)の周期で循環することを利用する問題でした。これらについては実際に実験して求めた人やFermatの小定理やEulerの定理によって説明しようとした人などがいました。しかしこ…