Calculator Input
Use integers only. The form stays in a single vertical flow, while inputs adapt to large, medium, and mobile screens.
Example Data Table
| a | b | n | k | p | Key Outputs |
|---|---|---|---|---|---|
| 35 | 20 | 12 | 5 | 29 | gcd = 5, inverse of 35 mod 12 = 11, φ(12) = 4 |
| 18 | 6 | 7 | 4 | 21 | 18 ≡ 4, 6 ≡ 6 (mod 7), no congruence, p is composite |
| 14 | 49 | 9 | 3 | 13 | 14 divides 49? No, inverse of 14 mod 9 = 2, p is prime |
Formula Used
Euclidean algorithm: gcd(a, b) is found by repeated division until the remainder becomes zero.
Bézout identity: If gcd(a, b) = g, then integers x and y exist such that ax + by = g.
Least common multiple: lcm(a, b) = |ab| / gcd(a, b), provided neither integer is zero.
Congruence test: a ≡ b (mod n) exactly when n divides (a − b).
Modular inverse rule: a has an inverse modulo n only when gcd(a, n) = 1.
Euler totient: φ(n) = n × Π(1 − 1/p) over distinct prime factors p of n.
Fast modular exponentiation: repeated squaring evaluates ak mod n efficiently.
How to Use This Calculator
Enter integers a and b for divisibility, gcd, lcm, and Bézout checks.
Choose modulus n to test congruence, modular inverses, and Euler totient values.
Set exponent k when you want the reduced value of ak modulo n.
Provide prime candidate p to run a straightforward primality check.
Press the submit button to place the result block directly below the header and above the form.
Use the CSV button for spreadsheet-style export and the PDF button for a printable summary of the current analysis.
Frequently Asked Questions
1. Can this tool prove any number theory theorem automatically?
No. It supports proof work by generating computed facts, residues, gcd steps, and inverse checks. You still write the final theorem-specific argument yourself.
2. Why does the inverse sometimes not exist?
A modular inverse exists only when the chosen integer and the modulus are coprime. If their gcd is larger than 1, no inverse can satisfy the congruence ax ≡ 1.
3. What does the Bézout line tell me?
It shows specific coefficients x and y for ax + by = gcd(a, b). This identity often becomes the key step in divisibility proofs, inverse construction, and linear congruence arguments.
4. How is congruence decided?
The calculator subtracts the two integers and checks whether the modulus divides the difference exactly. That is the standard proof definition of congruence modulo n.
5. Is the primality test suitable for huge inputs?
It is practical for normal study-sized integers. Extremely large numbers may require specialized probabilistic or advanced deterministic algorithms beyond this teaching-oriented page.
6. Why include Euler’s totient?
Totient values help with Euler’s theorem, reduced residue systems, and modular cycle reasoning. They are especially useful when the base is coprime with the modulus.
7. What happens when one value is zero?
The page still computes valid gcd behavior, but divisibility and lcm statements follow special cases. Zero cannot act as a divisor, and lcm becomes zero when either input is zero.
8. Can I use the exports in worksheets or reports?
Yes. CSV works well for tabular review, and the PDF export creates a compact summary you can attach to notes, class material, or problem-solving records.