Polynomial Modulo Calculator

Inputs

A(x)

Use terms like 3x^4, -2x, 5. No parentheses.

B(x) (for add/sub/mul/div/gcd)

M(x) (for A mod M or inverse)

Coefficient modulus p

Choose a prime for division, GCD, inverse, and modulus operations.

Operation

Show steps

Example Data

A(x)	B(x)	M(x)	p	Operation	Output
x^5 + 2x + 1	x^2 + 1	x^3 + x + 1	5	A mod M	Remainder of A by M over GF(5)
x^3 + 4x + 3	x + 2	-	7	Divide A by B	Quotient and remainder in GF(7)
x^4 + x^2 + 1	x^3 + 2	-	11	GCD(A,B)	Greatest common divisor in GF(11)

Result

Submit inputs to view the result. You can export after computing.

Formulae Used

Coefficient reduction: Each coefficient a is mapped to a mod p.

Polynomial division in GF(p)[x]: If B(x) has leading term c_b x^d with invertible c_b mod p, repeatedly subtract (c_r c_b^{-1}) x^{k} B(x) from the remainder, where c_r x^{d+k} is the current leading term.

Remainder (A mod M): The remainder of dividing A(x) by M(x) in GF(p)[x].

GCD and Inverse: Euclidean and extended Euclidean algorithms in GF(p)[x]; inverse exists iff gcd(A,M)=1. Results are made monic by scaling with the inverse of the leading coefficient.

How to Use

Enter polynomials using terms like 3x^2, -x, 5.
Choose a positive modulus p; prefer a prime for division, GCD, and inverses.
Select an operation: add, subtract, multiply, divide, remainder, GCD, or inverse.
For remainder or inverse, provide M(x) as the modulus polynomial.
Optionally tick Show steps to view division iterations.
Click Compute, then export the Result table and Example Data.

FAQs

It means arithmetic on coefficients modulo p, and, when a modulus polynomial M(x) is provided, reducing polynomials by taking remainders upon division by M(x).

For division, GCD, and inverses, yes—coefficients must be in a field GF(p). Addition and multiplication still work with any positive modulus, but division may fail.

Use terms like 3x^4, -2x, 7. No parentheses or spaces are required; the parser ignores spaces and handles signs and powers.

Likely because the leading coefficient of the divisor isn’t invertible modulo p, or because gcd(A,M) ≠ 1. Choose a prime p and coprime polynomials.

Yes, GCDs are scaled to be monic when possible by multiplying with the inverse of the leading coefficient modulo p.

You can for addition and multiplication. But division, GCD, and inverses require a field; otherwise some operations aren’t defined.

They capture the on-screen Result and Example Data tables and save them locally using client-side generation. No server storage is used.

Quick Reference: Small Prime Fields

p	Field	Invertible nonzero elements	Notes
2	GF(2)	1	Binary arithmetic; addition is XOR; popular in coding theory.
3	GF(3)	2	Trinary arithmetic; coefficients reduced to {0,1,2}.
5	GF(5)	4	Supports all operations shown; good for small demonstrations.
7	GF(7)	6	More residues allow richer examples without large numbers.
11	GF(11)	10	Prime ensures every nonzero coefficient is invertible.

Example Irreducible Moduli M(x)

These example polynomials are commonly used as moduli in finite fields. Verify irreducibility for your application.

p	Degree	Example M(x)	Comment
2	2	x^2 + x + 1	Classic irreducible over GF(2).
2	3	x^3 + x + 1	Irreducible; used in simple LFSR examples.
2	3	x^3 + x^2 + 1	Another degree-3 irreducible over GF(2).
2	4	x^4 + x + 1	Irreducible; builds GF(2^4).
2	4	x^4 + x^3 + 1	Irreducible; alternate for GF(2^4).
3	2	x^2 + 1	No roots in GF(3), thus irreducible.
3	2	x^2 + x + 2	No roots in GF(3), thus irreducible.
3	3	x^3 + 2x + 2	No roots in GF(3); commonly used example.

Operation Summary & Complexity (naïve algorithms)

Operation	Inputs	Output	Typical Complexity	Notes
Add / Subtract	A(x), B(x), p	A ± B	O(n)	Coefficient-wise mod p; works for any positive modulus.
Multiply	A(x), B(x), p	A · B	O(n²)	Schoolbook method; faster FFT/NTT not implemented here.
Divide	A(x), B(x), p	Q(x), R(x)	O(n²)	Requires p prime so leading coefficient is invertible.
Remainder A mod M	A(x), M(x), p	R(x)	O(n²)	Performs polynomial long division in GF(p)[x].
GCD	A(x), B(x), p	G(x)	O(n²)	Euclidean algorithm; result scaled to monic if possible.
Inverse mod M	A(x), M(x), p	A^-1 (if exists)	O(n²)	Exists iff gcd(A, M) = 1 in GF(p)[x].

Inputs

Example Data

Result

Formulae Used

How to Use

FAQs

What does “polynomial modulo” mean here?

Do I need a prime p?

How should I format inputs?

Why did division or inverse fail?

Does it make results monic?

Can I use non-prime moduli?

How do PDF and CSV exports work?

Related Calculators