Purchase Solution

Mod Proof

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
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.

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)), ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Probability Quiz

Some questions on probability

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

View More Free Quizzes
Related BrainMass Solutions

  • Prime proofs

    Proof: The result should be (mod ). According to Wilson's Theorem, (mod ) for any prime number . So we have and thus . Since is also a prime, then we have . Now I want to show that .

  • Modular proofs

    Proof: is a primitive root module , then (mod ) and (mod ) for any . and are relative to each other, then . Now I claim that is a primitive root module . If not, we can find some , such that (mod ).

  • Lagrange's theorem

    Therefore, the equation (mod ) can have at most four solutions with the form This is a proof involving Lagrange's theorem.

  • Discrete math proofs

    Prove that: ab = [(a mod m ) * (b mod m) mod m ] Proof. Assume that a= p mod m and b= q mod m. Then we know that a=km+p b=lm+q for some integers k and l.

  • Examples of contrapositives conjectures, & counterexamples

    What is wrong with the following proof of the conjecture "If n^2 is positive, then n is positive.": Proof: Suppose that n^2 is positive.

  • Congruences and Primes

    Proof: First, I claim that (mod ) We know that . For , we have since is a prime. and thus we have (mod ). Thus (mod ). Second, we assume that , where , mod .

  • Chinese Remainder Theorem : Proof and Problems

    x O(mod pr')? (c) Let n and in be coprirne integers. Show ? x 0 (mod nrn) if and only if x2 ? x 0 (mod n) and ? x 0 (mod m). (d) How many solutions are there to the equation x2 ? x 0 (mod N) where N has collected prime factorization N = .

  • Use Gauss' Lemma to show that 17 is a quadratic residue module 19.

    Problem #7 Proof: According to the Quadratic Reciprocity Law, for any two odd primes and , we have If (mod 12), then . So . Thus we have If (mod 12), then . So . Thus we have . If (mod 12), then . So .

  • Ring Homomorphisms, Residues and Distinct Maximal Ideals

    Proof: Since is a ring, then for any , we have (mod ) (mod ) (mod ). (mod ) (mod ) (mod ). Thus for any , we have Thus is a ring homomorphism. 2.

View More Related Solutions