9 votes
Accepted

How to factor a polynomial quickly in $\mathbb{F}_5[x]$

The observation made by user8268 is the key to the following paper and pencil factorization. Not ruling out the existence of other possibilities — that trick simply works like charm. Let $\alpha$ be ...
Jyrki Lahtonen's user avatar
8 votes
Accepted

number of rational points of hyper elliptic curve $y^5=-x^2+x$ over $\Bbb{F}_{121}$

The job is easily done with computer support, here sage. Let us do this first. ...
dan_fulea's user avatar
  • 32.3k
7 votes

Distribution of Primitive Elements Finite Fields Prime Order

Gauss proved that the sum $S_p$ of all primitive roots modulo $p$ in the interval $[1,p-1]$ is congruent to $\mu(p-1)$ modulo $p$. This result appeared several times before in MSE and a possible proof ...
Sungjin Kim's user avatar
  • 19.9k
7 votes
Accepted

Roots of $x^4+x^3+x^2+x+1$ over $\mathbb{Z}_3[x]/(x^3-x+1)$.

Using the same notation, $x$, for both as the variable of the polynomial and the field leads to the mistake. The question is the following: Let $\mathbb{F}=\mathbb{Z}_3[x]/(x^3-x+1)$. Show that the ...
Levent's user avatar
  • 4,812
7 votes
Accepted

Under $ad-bc=1$, is every element of a finite field of the form $a^2+b^2+c^2+d^2$?

Carl's answer is nice. I am adding an elementary argument. If $q$ is even, then all the elements are squares, and the question is trivial as we can use $a=d=1, b=0$. So assume that $q$ is odd, when $...
Jyrki Lahtonen's user avatar
6 votes
Accepted

What is $\{u+u^p: u\in F\}$ in the finite field $F_{p^n}$?

Linear algebra to the rescue! Let $K=\Bbb{F}_{p^n}$ be the finite field of cardinality $p^n$, $p=\mathrm{char} K$, a prime number. The first and most obvious observation is that $$T:K\to K, u\mapsto u+...
Jyrki Lahtonen's user avatar
6 votes
Accepted

Find the product of all irreducible polynomials over $\mathbb{F}_p$ of degree $n$

We have the formula, valid for all $n$: $$T^{p^n}-T=\prod_{d\mid n}H_d(T).$$ The general (multiplicative) version of Möbius inversion then gives the answer $$H_n(T)=\prod_{d\mid n}(T^{p^d}-T)^{\mu(n/d)...
5 votes

For multiplications over a finite field, what happens to the elements which, after modulo the reducing polynomial, still don't fit in the field?

Let $m(x) = x^{128} + x^7 + x^2 + x +1$, the "reducing polynomial". In the field $K = \mathbb{Z}[x]/m(x)$ that polynomial represents $0$. So $$ f(x) = x^{128} + x^7 + x^2 + x = m(x) -1 $$ is ...
Ethan Bolker's user avatar
  • 93.8k
5 votes

How is multiplication defined in the field extension $\mathbb Z_p(\sqrt3+5i)$

It works just fine if you make the (in my humble opinion reasonable) assumption that $i$ stands for an element satisfying the equation $i^2+1=0$, and similarly $\sqrt3$ is a solution of $x^2=3$. The ...
Jyrki Lahtonen's user avatar
5 votes
Accepted

Doubt in algebraic closure of a finite fields

You are right to be concerned, I think there's much more to say about this and Dummit and Foote are being sloppy here. First, here is the construction that Dummit and Foote are alluding to with the ...
Qiaochu Yuan's user avatar
5 votes
Accepted

Conclude: $-3 \in K$ is a square if and only if $q \equiv 1 \bmod 3$.

The relation $q \equiv 1 \bmod 3$ holds iff $3 \mid q-1$ iff the (cyclic!) group $\mathbb{F}_q^{\times}$ has an element of order $3$, i.e. there is some $a \in \mathbb{F}_q$ such that $a^3=1$ and $a \...
Martin Brandenburg's user avatar
5 votes

Representing finite fields

Zech Logarithms are useful for performing addition when you represent elements as powers of a multiplicative generator. They depend on a choice of the minimal polynomial of the generator. Although all ...
Derek Holt's user avatar
  • 89.3k
5 votes

Irreducible polynomials in the field with 4 elements

You are searching for irreducible polynomials of degree $\le3$, so the elementary irreducibility test works: a quadratic or a cubic $f(x)\in\Bbb{F}_4[x]$ is irreducible if and only if it has no zeros ...
Jyrki Lahtonen's user avatar
5 votes

Need example of a finite noncommutative ring with inverses

A ring is called a division ring if any non-zero element is invertible. A field is a commutative division ring. So what you are asking for is a finite division ring which is not a field. Actually such ...
Temoi's user avatar
  • 1,218
4 votes
Accepted

$𝜑(𝑥) = 𝑥^{𝑛−1} + 𝑥^{𝑛−2} + ⋯ 𝑥 + 1$ then $(𝜑(𝑥))^2 = 𝑛𝜑(𝑥)$ in $𝔽[𝑥]/⟨ 𝑥^𝑛 − 1 ⟩$

This problem rewrites $$\left(\frac{x^n-1}{x-1}\right)^2\equiv n\frac{x^n-1}{x-1}\bmod{x^n-1}$$ i.e. $$x^n-1\equiv n(x-1)\bmod{(x-1)^2}$$ or equivalently $$(1+y)^n-1\equiv ny\bmod{y^2}.$$ This follows ...
Anne Bauval's user avatar
  • 33.4k
4 votes
Accepted

Is $x^{100} - x^2 + 1$ separable in an algebraic closure of $\mathbb{F}_2$

The fact that your polynomial has no root does NOT imply that it is irreducible (this kind of argument works only for polynomials of degree $2$ or $3$. Think of $(x^2+1)^2\in\mathbb{R}[x])$. (And your ...
GreginGre's user avatar
  • 14.8k
4 votes
Accepted

"Low degree Polynomials do not have too many roots" - what exactly does this mean?

It seems to me like "low degree polynomials don't have too many roots" is a kind of slogan which is meant to be memorable. This slogan is made precise by the statement "A (nonzero) ...
HallaSurvivor's user avatar
4 votes
Accepted

Can a basis together with the zero vector form a vector space?

It looks like you've mostly got it, there are just a few minor details missing. First, I agree with your deduction that $B$ cannot contain more than 1 element. So we have two possibilities - either $B ...
ConMan's user avatar
  • 24k
4 votes

Element of order $p + 1$ in $\mathrm{GL}_2(\mathbb{F}_p)$

Let $X$ be any such matrix. It must be diagonalizable over $\overline{\mathbb{F}_p}$ (because non-diagonalizable matrices have order divisible by $p$ due to the Jordan block), so it has two ...
Qiaochu Yuan's user avatar
4 votes

Every finite integral domain is a field (why is it commutative?)

An integral domain is commutative by definition, or at least the standard definition. (The term "abelian" is specific to groups, not ring multiplication.) You're thinking of what's generally ...
coiso's user avatar
  • 2,854
4 votes
Accepted

For what values of $q$ is the action of $SL_2(\mathbb{F}_q)$ on $\mathbb{P}^1(\mathbb{F}_q)$ alternating?

You are right, the action is alternating for all $q>2$. For $q>2$, $SL_2(\mathbb{F}_q)$ is generated by an element of order $3$ (an odd order permutation must be even) and elements of the form $\...
colt_browning's user avatar
4 votes

How to define the multiplicative group on the additive group of a finite field?

One way to do is to take an irreducible polynomial $f \in (\Bbb Z/p\Bbb Z)[x]$ of degree $n$ and then identify the additive groups of $(\Bbb Z/p\Bbb Z)^{n,\oplus}$ and $(\Bbb Z/p\Bbb Z)[x]/(f)$ via $(...
Lukas Heger's user avatar
  • 20.7k
4 votes

Under $ad-bc=1$, is every element of a finite field of the form $a^2+b^2+c^2+d^2$?

We first treat the case where $\mathbb F_q$ has characteristic two. If $x=0$, we may take $a=d=1$ and $b=c=0$. If $x\neq 0$, then there exists some square root $a$ of $x$; note $a\neq 0$. Taking $b=0$ ...
Carl Schildkraut's user avatar
3 votes
Accepted

Polynomials that are zero as functions on finite fields

Yes, the ideal $I=(x_1^q-x_1,\cdots,x_n^q-x_n)$ is exactly the collection of polynomials which vanish on $\Bbb F_q^n$. Lemma. If $p(x_1,\cdots,x_n)\in\Bbb F_q[x_1,\cdots,x_n]$ is a nonzero polynomial ...
KReiser's user avatar
  • 64.4k
3 votes

How many ways to arrange $n$ points in $(\Bbb F_q)^2$ with no three collinear?

We call a set of points in the affine plane in general position if no $3$ of them are collinear. Let $a_n(q)$ be the number of (ordered) $n$-tuples of pairwise points in $\mathbb{F}_q^2$ in general ...
azimut's user avatar
  • 22.6k
3 votes
Accepted

Satake correspondence for groups over finite field

This is known as Deligne-Lusztig theory. See Delinge, Lusztig Representations of Reductive Groups Over Finite Fields.
Kenta S's user avatar
  • 16k
3 votes

How to factor a polynomial quickly in $\mathbb{F}_5[x]$

My approach is almost certainly not what the author had in mind, but this technique seems quite effective: If $\alpha$ is a root of a cubic factor in some extension, then by Vieta the constant term of ...
Benjamin Wright's user avatar
3 votes
Accepted

Probability that a linear map is non-singular over $\mathbb{F}_q$

What the passage you've (mis)quoted actually says is: A matrix is $\color{red}{\text{non}}$-singular whenever the first row is non-zero, and for each and, for each $\ i < o_2\ $, the $\ i+1$-th ...
lonza leggiera's user avatar
3 votes
Accepted

Notes on global function fields

What is it about places above $\infty$ in a finite extension of $K(x)$ compared to places above some other place in $K(x)$ (all of them being trivial on $K$) that you feel you need to understand ...
KCd's user avatar
  • 45.5k

Only top scored, non community-wiki answers of a minimum length are eligible