Result
Without mod
Full turns
gcd(a, n)

    More about modular arithmetic

    Modular clock

    Five hours after 9 o'clock it is 2 o'clock, because 9 + 5 = 14 and 14 is 2 more than 12. That is modular arithmetic: counting on a clock that starts again at 0 after n. Pick an operation, enter n, a and b, and the calculator gives the answer with every step written out, from the remainder of a division to repeated squaring and the extended Euclidean algorithm, while the clock shows how the answer is reached. Choose an operation, then enter the modulus n and the numbers a and b; whole numbers of up to 30 digits work, negative ones too, and n can be up to 10^18. The clock has n positions with 0 at the top, and its hand points at the answer. Addition and subtraction are drawn as a spiral of b steps, one ring for each full turn; multiplication as jumps of a; powers as the chords a, a², a³ …, which close into a cycle; the inverse and division as the multiples that land on 1 or on a. The steps show the same calculation in numbers. Up to mod 20 the table of the operation is shown; click a cell to use its numbers. Example fills in a classic problem.

    How it works

    1. Choose an operation: a mod n, addition, subtraction, multiplication, division, a power or the inverse of a.
    2. Enter the modulus n and the numbers a and b, or pick an example such as the last digit of 7^2026 or a small RSA message.
    3. Read the answer and the steps, follow the path on the clock, and up to mod 20 click a cell of the table to try its numbers.

    What a mod n means

    a mod n is the remainder when a is divided by n: 17 mod 5 = 2, because 17 = 3 × 5 + 2. The remainder is always from 0 to n − 1, also for negative numbers: −7 mod 3 = 2, because −7 = −3 × 3 + 2. On the clock that means walking 7 steps backwards from 0. Two numbers with the same remainder are congruent, written 17 ≡ 2 (mod 5), a notation Carl Friedrich Gauss introduced in 1801. Sums, differences and products can be reduced mod n at any step, which keeps the numbers small.

    Where modular arithmetic is used

    Clocks and calendars work mod 12, mod 24 and mod 7: 100 days after a Wednesday is a Friday, because 100 mod 7 = 2. Check digits use it to catch typing errors, from ISBN-10 numbers (mod 11) to bank card numbers (mod 10) and IBANs (mod 97). Ciphers shift letters mod 26, and the affine cipher needs an inverse mod 26 to decrypt. RSA, which protects much of the internet, encrypts a message m as m^e mod n and decrypts with another power: with n = 3233, 65^17 mod 3233 = 2790 and 2790^413 mod 3233 = 65.

    Frequently asked questions

    How do you calculate a mod n for a negative number?

    Add or subtract multiples of n until the number is between 0 and n − 1. For −7 mod 3: −7 + 9 = 2, so the answer is 2. Some programming languages give −1 for −7 % 3 instead, because they round the quotient towards zero; in mathematics the remainder is never negative.

    What is a modular inverse?

    The inverse of a mod n is the number x with a × x ≡ 1 (mod n). The inverse of 7 mod 26 is 15, because 7 × 15 = 105 = 4 × 26 + 1. It exists only when a and n have no common factor, and the extended Euclidean algorithm finds it. Dividing by a mod n means multiplying by its inverse.

    How can a power like 7^2026 be calculated mod n?

    By repeated squaring: square 7 again and again, reducing mod n each time, to get 7^1, 7^2, 7^4, 7^8 and so on, then multiply the ones that make up 2026 in binary. That takes 10 squarings and 7 multiplications instead of 2,025 multiplications, and the numbers never grow larger than n². 7^2026 ends in 9.

    Why does the clock show 0 instead of 12?

    In modular arithmetic the remainders run from 0 to n − 1, so on a clock with 12 positions noon is 0. 12 ≡ 0 (mod 12); an ordinary clock just prints 12 where the mathematics writes 0.

    How big can the numbers be?

    a and b can have up to 30 digits and may be negative, and the modulus can be up to 10^18. The calculator works with exact whole numbers in your browser, so even RSA-sized examples give exact answers, and nothing is sent anywhere.

    Ready to try it?

    Open PictorX in your browser — no install, no credit card required to start.

    Go to Editor