1 (mod N) có nghĩa là gì?

Question

Tôi đang cố triển khai một thuật toán đơn giản trong JavaScript. Bất cứ nơi nào tôi nhìn, nó kêu gọi mã để làm việc ra 1 (mod N). Theo như tôi có thể biết, 1 modulo (hoặc 1%N) là 1.

Tôi đang thiếu gì? Nó luôn luôn là 1, và nếu có, tại sao không chỉ sử dụng 1?

Answer 1

Thuật toán có thể nói cái gì đó như:

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

Các (mod N) và equals triple ký biểu thị rằng bạn đang làm việc với số học modula, không số học bình thường. Hãy nghĩ về nó như bàn tay của một chiếc đồng hồ. Trong số học mô-đun, x ≡ 1 có nghĩa là x và 1 thuộc về cùng một residue class. Nếu bạn có đồng hồ với các bộ phận giờ N, hãy xoay tay 1 thời gian hoặc x lần sẽ mang bàn tay đến cùng một vị trí kết thúc.

Đối với trường hợp cụ thể của bạn, x ≡ 1 (mod N) có thể được biểu diễn dưới dạng x % N === 1 trong JavaScript nếu x là không bao giờ tiêu cực. Nếu không, sự bình đẳng của bạn sẽ không giữ mặc dù nó cần: ví dụ: -1 ≡ 1 (mod 2) nhưng (-1) % 2 === -1, không bằng 1 mặc dù chúng "bằng nhau" trong ý nghĩa số học mô-đun.

Nếu bạn mong đợi x là tiêu cực, bạn chỉ có thể sắp xếp lại các mối quan hệ tương đẳng:

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

x - 1 là đồng dư với 0 có nghĩa là nó chia hết cho N chính nó, vì vậy bạn có thể sử dụng toán tử modulo một cách an toàn:

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

Answer 2

Cách hoạt động của toán tử modulo (%) được xác định trong ECMA-262 §11.5.3. Có một vài quirks, các nhà điều hành modulo ECMAScript chấp nhận nổi cũng như các số nguyên:

Đối với số nguyên:

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 

Đối với phao,

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 

Vì vậy, nếu không có sự bối cảnh như thế nào các nhà điều hành modulo đang được áp dụng, rất khó để xác định lý do tại sao nó được sử dụng. Hay nhất của tất cả sẽ là tài liệu của mã, nhưng tôi cho rằng đó là không có sẵn.

Một sử dụng là, nơi một số nguyên dự kiến, để đánh giá 0 và 1 là sai và mọi thứ khác là đúng, vì vậy:

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