javascript - 1 (mod N) とはどういう意味ですか?

Question

JavaScript で単純なアルゴリズムを実装しようとしています。どこを見ても、コードが機能する必要があります1 (mod N)。私が知る限り、何でも (または1%N) を法とする 1 は 1 です。

私は何が欠けていますか？それは常に 1 ですか? もしそうなら、なぜ 1 を使わないのでしょうか?

Answer 1

アルゴリズムはおそらく次のように言っています。

x ≡ 1 (mod N)  # x is congruent to 1 (modulo N)

と 3 つの(mod N)等号は、通常の算術演算ではなく、剰余算術を使用していることを示します。時計の針のようなものと考えてください。剰余算術では、とが同じ留数クラスに属することをx ≡ 1意味します。時間単位の時計をお持ちの場合、針を回すと針が同じ終了位置に移動します。x1N1x

あなたの特定のケースでは、 JavaScript のようx ≡ 1 (mod N)に表すことができますifは決して負ではありません。そうしないと、等しいはずなのに保持されません。たとえば、ただし、剰余算術の意味で「等しい」にもかかわらず、等しくありません。x % N === 1x-1 ≡ 1 (mod 2)(-1) % 2 === -11

負になることが予想xされる場合は、合同関係を再配置できます。

       x ≡ 1 (mod N)
⇒  x - 1 ≡ 0 (mod N)

x - 1合同であるということは、それ自体で0割り切れることを意味するNため、モジュロ演算子を安全に使用できます。

if ((x - 1) % N === 0) {
    ...
}