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?
32 Answers
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) { ... } 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 } 
