What does 1 (mod N) mean?

Question

I am trying to implement a simple algorithm in JavaScript. Wherever I look, it calls for the code to work out 1 (mod N). As far as I can tell, 1 modulo anything (or 1%N) is 1.

What am I missing? Is it always 1, and if so, why not just use 1?

Solution 1

The algorithm probably says something like:

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

The (mod N) and the triple equals sign denote that you're working with modular arithmetic, not normal arithmetic. Think of it like the hands of a clock. In modular arithmetic, x ≡ 1 means that x and 1 belong to the same residue class. If you have a clock with N hour divisions, turning the hand 1 time or x times will bring the hand to the same end position.

For your specific case, x ≡ 1 (mod N) can be represented as x % N === 1 in JavaScript if x is never negative. Otherwise, your equality will not hold even though it should: for example, -1 ≡ 1 (mod 2) but (-1) % 2 === -1, which isn't equal to 1 even though they're "equal" in the modular arithmetic sense.

If you expect x to be negative, you can just rearrange the congruence relation:

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

x - 1 being congruent to 0 means that it's divisible by N itself, so you can use the modulo operator safely:

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

Solution 2

How the modulo (%) operator works is defined in ECMA-262 §11.5.3. There are a few quirks, the ECMAScript modulo operator accepts floats as well as integers:

For integers:

1 % -Infinity returns 1
...
1 % -2 returns 1
1 % -1 returns 0
1 %  0 returns NaN
1 %  1 returns 0
1 %  2 returns 1
...
1 % Infinity returns 1

For floats,

1 % -1.1 returns 1
1 %  0.1 returns 0.09999999999999995
1 %  0.6 returns 0.4
1 %  0.5 returns 0
1 %  0.4 returns 0.19999999999999996
1 %  0.9 returns 0.09999999999999998
1 %  1.1 returns 1

So without the context of how the modulo operator is being applied, it's very difficult to determine why it's being used. Best of all would be documentation of the code, but I suppose that's not available.

One use is, where an integer is expected, to evaluate 0 and 1 as false and everything else as true, so:

if (1 % n) {
  // do this if n is something other than 0 or 1
}