All Questions
Tagged with polynomials finite-fields
126
questions
54
votes
3
answers
18k
views
Irreducible polynomial which is reducible modulo every prime
How to show that $x^4+1$ is irreducible in $\mathbb Z[x]$ but it is reducible modulo every prime $p$?
For example I know that $x^4+1=(x+1)^4\bmod 2$. Also $\bmod 3$ we have that $0,1,2$ are not ...
- 11.1k
83
votes
3
answers
13k
views
Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$
Let $f(x) \in \mathbb{Z}[x]$. If we reduce the coefficents of $f(x)$ modulo $p$, where $p$ is prime, we get a polynomial $f^*(x) \in \mathbb{F}_p[x]$. Then if $f^*(x)$ is irreducible and has the same ...
- 12k
68
votes
2
answers
33k
views
Number of monic irreducible polynomials of prime degree $p$ over finite fields
Suppose $F$ is a field s.t $\left|F\right|=q$. Take $p$ to be some prime. How many monic irreducible polynomials of degree $p$ do exist over $F$?
Thanks!
- 4,215
31
votes
6
answers
6k
views
Do we really need polynomials (In contrast to polynomial functions)?
In the following I'm going to call
a polynomial expression an element of a suitable algebraic structure (for example a ring, since it has an addition and a multiplication)
that has the form $a_{n}x^{...
- 5,255
17
votes
2
answers
22k
views
Reed Solomon Polynomial Generator
I am developing a sample program to generate a 2D Barcode, using Reed-Solomon error correction codes. By going through this article, I am developing the program. But I couldn't understand how he ...
- 389
17
votes
3
answers
20k
views
How many irreducible polynomials of degree $n$ exist over $\mathbb{F}_p$? [duplicate]
I know that for every $n\in\mathbb{N}$, $n\ge 1$, there exists $p(x)\in\mathbb{F}_p[x]$ s.t. $\deg p(x)=n$ and $p(x)$ is irreducible over $\mathbb{F}_p$.
I am interested in counting how many such $...
- 23.2k
15
votes
2
answers
7k
views
Why $x^{p^n}-x+1$ is irreducible in ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$
I have a question, I think it concerns with field theory.
Why the polynomial $$x^{p^n}-x+1$$ is irreducible over ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$?
Thanks in advance. It bothers me for ...
- 151
18
votes
3
answers
10k
views
Product of all monic irreducibles with degree dividing $n$ in $\mathbb{F}_{q}$?
In the finite field of $q$ elements, the product of all monic irreducible polynomials with degree dividing $n$ is known to be $X^{q^n}-X$. Why is this?
I understand that $q^n=\sum_{d\mid n}dm_d(q)$, ...
- 311
8
votes
2
answers
3k
views
Factoring $X^{16}+X$ over $\mathbb{F}_2$
I just asked wolframalpha to factor $X^{16}+X$ over $\mathbb{F}_2$. The normal factorization is
$$
X(X+1)(X^2-X+1)(X^4-X^3+X^2-X+1)(X^8+X^7-X^5-X^4-X^3+X+1)
$$
and over $GF(2)$ it is
$$
X(X+1)(X^2+...
- 83
26
votes
3
answers
29k
views
How can I prove irreducibility of polynomial over a finite field?
I want to prove what $x^{10} +x^3+1$ is irreducible over a field $\mathbb F_{2}$ and $x^5$ + $x^4 +x^3 + x^2 +x -1$ is reducible over $\mathbb F_{3}$.
As far as I know Eisenstein criteria won't help ...
- 555
3
votes
2
answers
2k
views
$x^p-x \equiv x(x-1)(x-2)\cdots (x-(p-1))\,\pmod{\!p}$
I got a question to show that :
If $p$ is prime number, then
$$x^p - x \equiv x(x-1)(x-2)(x-3)\cdots (x -(p-1))\,\,\text{(mod }\,p\text{)}$$
Now I got 2 steps to show that the two polynomials ...
- 33
12
votes
2
answers
2k
views
On irreducible factors of $x^{2^n}+x+1$ in $\mathbb Z_2[x]$
Prove that each irreducible factor of $f(x)=x^{2^n}+x+1$ in $\mathbb Z_2[x]$ has degree $k$, where $k\mid 2n$.
Edit. I know I should somehow relate the question to an extension of $\mathbb Z_2$ of ...
- 931
11
votes
2
answers
20k
views
Why is $X^4+1$ reducible over $\mathbb F_p$ with $p \geq 3,$ prime [duplicate]
I have proven that in $\mathbb F_{p^2}^*$ exists an element $\alpha$ with $\alpha^8 = 1$.
Let $f(X) := X^4+1 \in \mathbb F_p[X]$. How can I prove that $f$ is reducible over $\mathbb F_p$?
Has $f$...
user42761
7
votes
4
answers
5k
views
A cubic polynomial over a field is irreducible if it has no roots
I want to argue that argue that $\pi(\alpha)=\alpha^3+3\alpha+3$ is an irreducible polynomial over the finite field with 5 elements $\mathbb{F}_5$. My approach was just to check that $\pi$ has no ...
- 369
6
votes
1
answer
4k
views
How many irreducible factors does $x^n-1$ have over finite field?
The polynomial $x^n-1$ is needed to be factorized into irreducibles over finite field $\mathrm{F}_q$. How many are them?
I guess the question is about of number of cyclotomic cosets. Let $p$ be the ...
- 428