Calculate a mod n under the floored, truncated and Euclidean conventions, modular powers a^b mod m of large numbers, and modular inverses, with steps.
Cập nhật Ví dụ đã kiểm tra: 10
−17 ÷ 5 leaves 3 when the quotient is rounded down to −4 (Python, Excel MOD), but −2 when it is rounded toward zero to −3 (C, JavaScript %).
Python's %, Excel's MOD and most maths texts round the quotient down.
C, Java and JavaScript's % round the quotient toward zero.
The modulo operation a mod n gives the remainder left when a is divided by n. For positive numbers every convention agrees (17 mod 5 = 2), but for negative numbers they split: the floored remainder r = a − n⌊a/n⌋ takes the sign of the divisor, the truncated remainder rounds the quotient toward zero and takes the sign of the dividend, and the Euclidean remainder is never negative. The calculator shows all three, and also computes modular powers by square-and-multiply and modular inverses by the extended Euclidean algorithm.
Clock and calendar arithmetic, hashing and cyclic buffers all use remainders, and cryptography rests on modular powers. The default, −17 mod 5, is 3 under floored division (Python's %, Excel's MOD) but −2 under truncated division (the % of C and JavaScript). The textbook RSA example encrypts 65 as 65^17 mod 3233 = 2790.
Modular powers stay exact for exponents as large as 10^18 because every squaring is reduced mod m. An inverse a⁻¹ mod m exists only when gcd(a, m) = 1.
Nguồn đối chiếu: Python 3.8: -17 % 5 = 3, math.fmod(-17, 5) = -2.0, -17 // 5 = -4
Nguồn đối chiếu: Python 3.8: 17 % -5 = -3, math.fmod(17, -5) = 2.0; Euclidean 17 − 5·⌊17/5⌋ = 2
Nguồn đối chiếu: Python 3.8: 7.5 % 2 = 1.5
Nguồn đối chiếu: Wikipedia — Modular exponentiation worked example; Python pow(4, 13, 497) = 445
Divide, round the quotient down, and subtract: a mod n = a − n⌊a/n⌋. For 17 mod 5, 17 ÷ 5 = 3.4, which rounds down to 3, and 17 − 5 × 3 = 2. For −17 mod 5, −3.4 rounds down to −4, and −17 − 5 × (−4) = 3. On a 12-hour clock, 15:00 is 15 mod 12 = 3 o'clock.
They round the quotient differently. Python's % floors it, so −17 % 5 = 3, with the sign of the divisor; JavaScript, C and Java truncate toward zero, so −17 % 5 = −2, with the sign of the dividend. Both satisfy a = n × q + r. Excel's MOD matches Python. In JavaScript, ((a % n) + n) % n gives the floored answer when n is positive.
Use square-and-multiply: write the exponent in binary, square repeatedly, and reduce mod m after every step so the numbers never grow past m². For 4^13 mod 497, 13 is 1101 in binary and the answer is 445, the same as Python's pow(4, 13, 497). Computing 4^13 = 67,108,864 first works here, but not for exponents like 10^18.
The inverse of a modulo m is the number x with a × x ≡ 1 (mod m). 3⁻¹ mod 11 = 4 because 3 × 4 = 12 = 11 + 1. It exists only when gcd(a, m) = 1, so 2 has no inverse mod 10. The extended Euclidean algorithm finds it; in the textbook RSA example the private key 2753 is the inverse of 17 mod 3120, since 17 × 2753 = 46,801 = 15 × 3120 + 1.
For positive numbers they agree: 17 divided by 5 leaves 2 either way. For negative numbers the remainder in the C and JavaScript sense follows the sign of the dividend (−17 rem 5 = −2), while modulo in the mathematical sense follows the divisor or is never negative (−17 mod 5 = 3). When the two differ, they differ by exactly |n|.
Độ chính xác phụ thuộc vào dữ liệu nhập và giả định của phương pháp. Phép tính thập phân dùng 50 chữ số có nghĩa, nhưng ước lượng, phương pháp số và dữ liệu nguồn có thể kém chính xác hơn; làm tròn khi hiển thị không loại bỏ các giới hạn đó. Ví dụ có lời giải đã đối chiếu với nguồn độc lập: 10. Ví dụ, “−17 mod 5” được kiểm tra bằng Python 3.8: -17 % 5 = 3, math.fmod(-17, 5) = -2.0, -17 // 5 = -4.
Knuth, The Art of Computer Programming Vol. 1, §1.2.4 (mod) and Vol. 2, §4.6.3 (powers); Leijen (2001), Division and modulus for computer scientists; Wikipedia — Modular exponentiation (4^13 mod 497 example); Microsoft Excel MOD function.
Công cụ tính này có 10 ví dụ đã giải với đáp án từ các nguồn độc lập. Chúng được chạy trong bộ kiểm thử và bạn cũng có thể chạy tại đây.
Greatest common divisor (GCD, GCF or HCF) and least common multiple (LCM) of two or more whole numbers, with Euclid's algorithm step by step.
Prime factorization of any whole number up to 60 digits, with a factor tree, a prime or composite verdict, its divisors and the nearest primes.
Factor calculator: every factor and factor pair of a whole number up to 10¹⁸, its prime factorization, divisor count and sum, and perfect or abundant.