Modular arithmetic calculator
BigInt modular arithmetic: fast exponentiation a^b mod m, modular inverse via the extended Euclidean algorithm, the Chinese remainder theorem (coprime or not), Euler’s totient, GCD/LCM and small-range discrete logarithms.
Runs in your browserEvery computation happens in your browser — your data never leaves this device.
Input
Everything is computed with BigInt, so integers with dozens of digits stay exact; lines starting with # are ignored.
Result
24
101000What this tool does
- Practise RSA or elliptic-curve maths: a^b mod m uses square-and-multiply, and integers with dozens of digits stay exact.
- Solve congruence systems: enter conditions like “2, 3 / 3, 5 / 2, 7” and get x ≡ 23 (mod 105) — non-coprime moduli work too.
- Get a modular inverse when you need “division”: multiply by a⁻¹ instead, and the tool shows the a·x mod m check for you.
- Number theory homework stays in one place: Euler φ, GCD, LCM and small-range discrete logarithms are all here.
Example
Input
Congruences: 2, 3 / 3, 5 / 2, 7 (that is x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7))
Output
x ≡ 23 (mod 105); solution x = 23 with modulus M = 105, checks 23 ≡ 2 (mod 3); 23 ≡ 3 (mod 5); 23 ≡ 2 (mod 7)
Write one “remainder, modulus” pair per line. Moduli need not be coprime, and contradictory systems report “no solution” instead of inventing an answer.
Frequently asked questions
Why is there no “division” in modular arithmetic?
Because only numbers coprime to m have a multiplicative inverse mod m: x with a·x ≡ 1 (mod m) exists exactly when gcd(a, m) = 1. The tool therefore computes inverses with the extended Euclidean algorithm and reports “no inverse” instead of returning a wrong value.
How is fast exponentiation different from repeated multiplication?
It splits the exponent into binary digits and squares the base each step, giving O(log b) work. For an exponent with hundreds of bits, multiplying directly would need 2^b steps. The unit tests cross-check it against naive repeated multiplication.
Does the Chinese remainder theorem need coprime moduli?
The classic version does, but this implementation is the general one: when merging two congruences it checks gcd first, solves when the difference divides it and reports “no solution” otherwise. So x ≡ 1 (mod 4) with x ≡ 3 (mod 6) still gives 9 (mod 12).
How large a discrete logarithm can it solve?
It brute-forces up to one million steps by default, which fits small exercises with moduli up to a few million. Larger ranges need baby-step giant-step, which this tool does not implement — exceeding the step limit reports “no solution”.
Can large integers lose precision?
No. Every operation uses BigInt rather than Number, so values far beyond 2^53 such as 2^100 stay exact. Euler’s totient needs factorisation, and trial division is capped at 10^12 — beyond that it reports an error instead of guessing.
Keywords：modular arithmetic模运算modular exponentiation快速幂modular inverse模逆元chinese remainder theorem中国剩余定理euler phi欧拉函数discrete log离散对数bigintgcd lcm