Explore BrainMass
Share

Explore BrainMass

    Mod Proof

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com October 9, 2019, 6:39 pm ad1c9bdddf
    https://brainmass.com/math/discrete-math/mod-divisibility-proof-93933

    Solution Preview

    Proof:
    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.

    $2.19