- #1

- 277

- 0

Over the field Zq the following polynomial:

x^q^n-x

is the product of all irreducible polynomials whose degree divides n

Thanks.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter gonzo
- Start date

- #1

- 277

- 0

Over the field Zq the following polynomial:

x^q^n-x

is the product of all irreducible polynomials whose degree divides n

Thanks.

- #2

- 644

- 1

[edit]Now that i think about it, you did mean Z_q. Let me call it F_q rather.

The proof of this is carried out over some steps.

1. Lemma : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n

This would imply that all monic irreducible polynomials over F_q that we see in the factorization of x^q^n-x (belonging to F_q[x]) are exactly those whose degree divides n

2. Lemma : An f belonging to F_q[x] has a multiple root iff (f,f') != 1

Now Consider g(x) = x^q^n-x. So g'(x) = -1. So from the above lemma, we get that all monic irreducible polynomials whose degree divides n, occur exactly once in factorization of g in F_q[x]

Hence proved.

I have avoided proofs of the above lemmas. I guess they should be simple enough to be proved.[/edit]

-- AI

Last edited:

- #3

- 277

- 0

- #4

mathwonk

Science Advisor

Homework Helper

2020 Award

- 11,154

- 1,349

- #5

mathwonk

Science Advisor

Homework Helper

2020 Award

- 11,154

- 1,349

usually Fq denotes the unique field of order q where q is a power of a prime p.

- #6

- 644

- 1

Proof :

First half -->

Let k be a root of f(x)

F_q(k) is a subfield of F_q^n (why??)

[F_q(k):F_q] = m

but [F_q^n : F_q] = n

Therefore, m divides n (why??)

Converse,

given m|n

F_q^m is a subfield of F_q^n (why??)

If k is a root of f,

then F_q(k) = F_q^m (why??)

Therefore, k is a root of x^q^n - x (why??)

Hence, f divides x^q^n - x

I have left a lot of details in the proof, try to fill them in.

-- AI

- #7

- 28

- 0

- #8

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

But to answer your question...

What are the definitions of all the things involved? Let's write them out.

1) What is the definition of min poly?

2) Suppose that f is reducible: f(x)=g(x)h(x) and that a is a root of f, i.e. f(a)=0.

3) Does that imply anything about g(a) or h(a)?

4) Remember this is a field

- #9

- 28

- 0

- #10

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

- #11

- 28

- 0

and the element [01110]

[00011]

[00111]

[11000]

[01000]

which is of order 31. It's minimal polynomial is x^5 + x^4 + x^3 + x^2 + 1. How can we assure that it's degree is 5 without evaluating it. It could as easily be 2 or 3 or whatever.

- #12

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

Ah, got you. Not having a good time with my return to this kind of mathematics.

- #13

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

- #14

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

the roots of a poly of degree k form a subfield of degree q^k, and hence any element has order at most q^k-1, if k is not n, then this is a contradiction.

- #15

- 2

- 0

- #16

- 2

- 0

I mean Zp(z), the field, of course.

Steve

Steve

Share:

- Replies
- 1

- Views
- 2K

- Replies
- 6

- Views
- 402