Explore BrainMass

Mod Proof

Let i, j, n be positive integers with i > j. Let f(x) in Zn[x] have non-zero constant term, and let d = o(x mod f(x)). Suppose that x^i and x^j have the same remainder on division by f(x). Prove that i-j >= d.

Theorem 4.7.2
Suppose that F is a field of order |F| = q and that f(x) in F[x] has degree n >= 1 and has non-zero constant term. Then there is an integer m <= q^n - 1 such that x^m = 1 (mod f(x)).

Definition 4.7.3
With f, q, n as in Theorem 4.7.2, the least integer m such that x^m = 1 (mod f(x)) is called the order of x modulo f(x) and we write m = o(x mod f). If o(x) = q^n - 1 then we call f(x) a primitive polynomial over F.

Solution Preview

Since x^i and x^j have the same remainder on division of f(x), then x^i=x^j (mod f(x)), ...

Solution Summary

A mod proof is provided. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.