Calculator
Example Data Table
| Base a | Modulus n | phi(n) | gcd(a,n) | Theorem Check | Example Power Result |
|---|---|---|---|---|---|
| 7 | 40 | 16 | 1 | 7^16 mod 40 = 1 | 7^123 mod 40 = 23 |
| 3 | 10 | 4 | 1 | 3^4 mod 10 = 1 | 3^27 mod 10 = 7 |
| 5 | 12 | 4 | 1 | 5^4 mod 12 = 1 | 5^19 mod 12 = 5 |
| 4 | 15 | 8 | 1 | 4^8 mod 15 = 1 | 4^29 mod 15 = 4 |
| 2 | 9 | 6 | 1 | 2^6 mod 9 = 1 | 2^100 mod 9 = 7 |
Formula Used
Euler theorem states that if gcd(a,n) = 1, then:
a^phi(n) ≡ 1 mod n
For a prime factorization n = p1^r1 × p2^r2 × ... × pk^rk, the totient is:
phi(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)
When gcd(a,n) = 1, a large exponent k can be reduced:
a^k mod n = a^(k mod phi(n)) mod n
The calculator also computes the direct modular power with a digit based method. It avoids expanding huge powers.
How to Use This Calculator
- Enter the base value a.
- Enter the modulus n. It must be greater than 1.
- Enter an optional exponent k for a modular power problem.
- Choose how many rows to show in the residue table.
- Press Calculate.
- Read the factorization, phi(n), gcd check, theorem verification, and reduced exponent result.
- Use the CSV or PDF button to export the calculated solution.
Euler Theorem in Modular Arithmetic
Euler theorem is a core result in number theory. It connects a base, a modulus, and Euler totient function. The theorem says that a raised to phi n leaves remainder one when a and n are coprime. This simple statement powers many modular shortcuts. It is useful in contests, cryptography, coding, and algebra courses.
Why This Calculator Helps
Large powers are hard to compute directly. A number like 17 raised to 987654321 has far too many digits. Modular arithmetic only needs the remainder after division by n. This calculator reduces that large exponent by phi n when the coprime condition is satisfied. It also computes the direct modular residue using digit based exponentiation, so very long exponent strings can be handled without expanding the full power.
Totient and Factor Insight
The most important step is finding phi n. The tool factors the modulus into prime powers. It then applies the product formula for the totient. A prime modulus has phi n equal to n minus one. A composite modulus needs each distinct prime factor. Seeing the factor table helps users understand why the final totient appears.
Coprime Check Matters
Euler theorem only applies when the greatest common divisor of a and n equals one. The calculator shows that check clearly. If the values are not coprime, the modular power can still be computed. However, the theorem based reduction is not reported as valid. This prevents a common mistake in homework solutions.
Study and Verification Use
The residue table shows powers from zero upward. It lets students notice cycles, repeated residues, and the point where Euler theorem predicts one. The CSV file is useful for spreadsheets and classroom records. The PDF file gives a compact solution summary for sharing, printing, or attaching to assignments.
Practical Applications
Euler theorem is used when reducing powers in congruence problems. It also appears behind RSA style thinking, modular inverse arguments, and repeated remainder patterns. By combining factorization, phi calculation, exponent reduction, and residue tables, this page gives a complete workflow instead of only a final number.
The layout keeps inputs, results, examples, and explanations close together. Users can audit each step before copying answers into notes or worksheets with confidence.
FAQs
What does Euler theorem say?
It says a^phi(n) leaves remainder 1 modulo n when a and n are coprime. The condition gcd(a,n) = 1 is required.
What is phi(n)?
Phi(n), also called Euler totient, counts positive integers up to n that are relatively prime to n.
Why is the gcd check important?
Euler theorem only works when gcd(a,n) equals 1. Without that condition, exponent reduction by phi(n) may give a wrong result.
Can this calculator handle large exponents?
Yes. The exponent field accepts long whole numbers. The calculation uses modular digit processing instead of expanding the full power.
What happens when a and n are not coprime?
The calculator still finds a^k mod n. It does not mark Euler based reduction as valid because the theorem condition fails.
Why is prime factorization shown?
Prime factorization explains how phi(n) is found. It also helps users verify each number theory step manually.
What is the residue table for?
The residue table shows repeated modular patterns. It helps students see cycles and compare them with the theorem result.
Can I export my result?
Yes. After calculation, use the CSV button for spreadsheet data or the PDF button for a compact solution report.