# 剰余計算機（モジュロ）

> 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.

操作できるページ：https://www.calcopenly.com/ja/math/modulo-calculator
分野：数学の計算機

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.

## 入力

- **Calculate** (選択肢：Remainder a mod n, Power a^b mod m, Inverse a⁻¹ mod m)
- **Dividend a**: Integers, decimals or fractions.
- **Divisor n**
- **Base a**
- **Exponent b**: Any size, e.g. 10^18. A negative exponent uses the inverse of a.
- **Modulus m**
- **Number a**
- **Modulus m**

## 結果

- 結果 — 主な結果
- Truncated remainder (sign of a)
- Euclidean remainder (never negative)
- Floored quotient ⌊a ÷ n⌋
- 正確な値

## 計算式

$$
\begin{gathered} a \bmod n = a - n\left\lfloor \frac{a}{n} \right\rfloor \\[6pt] a^{b} \bmod m \text{ by square-and-multiply} \\[6pt] a\,a^{-1} \equiv 1 \pmod m \end{gathered}
$$

## 計算例

### −17 mod 5

- Calculate: Remainder a mod n
- Dividend a: -17
- Divisor n: 5
- **結果: 3**
- **Truncated remainder (sign of a): -2**
- **Euclidean remainder (never negative): 3**
- **Floored quotient ⌊a ÷ n⌋: -4**
- 照合元：Python 3.8: -17 % 5 = 3, math.fmod(-17, 5) = -2.0, -17 // 5 = -4

### 17 mod −5

- Calculate: Remainder a mod n
- Dividend a: 17
- Divisor n: -5
- **結果: -3**
- **Truncated remainder (sign of a): 2**
- **Euclidean remainder (never negative): 2**
- 照合元：Python 3.8: 17 % -5 = -3, math.fmod(17, -5) = 2.0; Euclidean 17 − 5·⌊17/5⌋ = 2

### 7.5 mod 2

- Calculate: Remainder a mod n
- Dividend a: 7.5
- Divisor n: 2
- **結果: 1.5**
- **Truncated remainder (sign of a): 1.5**
- 照合元：Python 3.8: 7.5 % 2 = 1.5

### 4^13 mod 497

- Calculate: Power a^b mod m
- Base a: 4
- Exponent b: 13
- Modulus m: 497
- **結果: 445**
- 照合元：Wikipedia — Modular exponentiation worked example; Python pow(4, 13, 497) = 445

### 2^(10^18) mod 1 000 000 007

- Calculate: Power a^b mod m
- Base a: 2
- Exponent b: 10^18
- Modulus m: 1000000007
- **結果: 719,476,260**
- 照合元：Python 3.8 pow(2, 10**18, 10**9 + 7) (scratchpad forkA/verify_mod.py)

### RSA encryption 65^17 mod 3233

- Calculate: Power a^b mod m
- Base a: 65
- Exponent b: 17
- Modulus m: 3233
- **結果: 2,790**
- 照合元：Wikipedia — RSA (cryptosystem) worked example, c = 65^17 mod 3233 = 2790

## よくある質問

### How do you calculate a mod n?

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.

### Why do Python and JavaScript give different answers for a negative modulo?

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.

### How do you calculate large powers modulo a number?

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.

### What is a modular inverse?

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.

### What is the difference between remainder and modulo?

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|.

### 「剰余計算機（モジュロ）」の精度はどのくらいですか？

精度は入力値と計算方法の前提に依存します。十進演算には有効数字50桁を使いますが、推定、数値計算手法、元データの精度はそれより低い場合があります。表示の丸め処理でこれらの制約がなくなるわけではありません。 独立した出典の解答と照合した計算例：10。 例えば、「−17 mod 5」は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.

## 出典

- 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](https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/)
- [Wikipedia — Modular exponentiation (4^13 mod 497 example)](https://en.wikipedia.org/wiki/Modular_exponentiation)
- [Microsoft Excel MOD function](https://support.microsoft.com/office/mod-function-9b6cd169-b6ee-406a-a97b-edf2a9dc24f3)