Enrichment · STEM Explorations · Math

Clock arithmetic,
with the steps
written out.

Choose an operation and type the numbers, as large as you like. The calculator gives the exact remainder and shows the method: the squaring table for powers and the Euclidean algorithm for inverses, the arithmetic behind check digits and internet encryption.

CalculateWhat you get

The modular arithmetic calculator

The worked example: 7 to the 45th power, mod 13. Nothing you type leaves this browser.

Loading the calculator. If nothing appears, turn on JavaScript.

What you get

Enrichment · STEM ExplorationsFree

What you finish with
The exact result as a least non-negative residue, the gcd of a and m, and the full working: a squaring table for powers, a Euclidean algorithm table for inverses. It prints as a summary and downloads as a spreadsheet.
Who it is for
High school math students, computer science and cryptography students, math club students, and math teachers and tutors.
Format
Browser calculator for a phone, tablet or computer, by touch or keyboard. Whole numbers up to 300 digits. Prints a summary; downloads a spreadsheet (.csv); export and import a file.
Access
Free. No account, no sign-in and nothing to install. Everything you type stays in this browser; nothing is sent to Caveat.
Where it lives
The STEM Explorations space in Caveat Enrichment.
Support
Questions, a correction or a request: team@caveatacademic.com.

How to use it

  1. Choose an operation.
  2. Type a, b if the operation uses it, and the modulus m.
  3. Read the result and the table of steps.
  4. Try an inverse with an m that shares a factor with a to see when none exists.
  5. Print the summary or download the spreadsheet.

Calculate

How the methods work

Square and multiply; divide and back-substitute.

The worked example: 7 to the 45th power, mod 1345 in binary10110132 + 8 + 4 + 1Square and reduce7, 10, 9, 3, 9, 37 to 1, 2, 4, 8, 16, 32Keep the 1 bits7 × 9 × 3 × 3powers 1, 4, 8, 327⁴⁵ mod 138567 = 43 × 13 + 8The worked example: 7 to the 45th power, mod 1345 in binary10110132 + 8 + 4 + 1Square and reduce7, 10, 9, 3, 9, 37 to 1, 2, 4, 8, 16, 32Keep the 1 bits7 × 9 × 3 × 3powers 1, 4, 8, 327⁴⁵ mod 138567 = 43 × 13 + 8
Six squarings replace 44 multiplications: write 45 in binary, square 7 repeatedly mod 13, and multiply the squares that line up with the 1 bits.

Powers by repeated squaring

Write the exponent in binary. Square the base again and again, reducing mod m after each step so the numbers stay small, and multiply together the squares that line up with the 1 bits. A 300-digit exponent needs about a thousand squarings rather than an impossible number of multiplications, which is how encryption software does it.

Inverses by Euclid

An inverse of a mod m is a number x with a × x leaving remainder 1. It exists only when a and m share no factor. The Euclidean algorithm divides repeatedly to find the gcd, and tracking the coefficients along the way, the extended algorithm, produces x. When the gcd is not 1, the page says no inverse exists.

Sources

  1. OpenStax. Contemporary Mathematics (2023), section 3.1 and 3.6: prime factorization, gcd and clock arithmetic (openstax.org).
  2. Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, Seminumerical Algorithms (3rd ed.), section 4.5.2 (Euclid’s algorithm) and 4.6.3 (evaluation of powers).
  3. National Institute of Standards and Technology. FIPS 186-5, Digital Signature Standard (2023): modular exponentiation and inverses in RSA.
  4. NIST Digital Library of Mathematical Functions, chapter 27, Functions of Number Theory (dlmf.nist.gov).

The worked example is for practice. Your entries stay in this browser. Support: team@caveatacademic.com.