Questions tagged [cyclotomic-polynomials]
For questions related to cyclotomic polynomials and their properties.
468
questions
0
votes
0
answers
19
views
Impact of plaintext modulus overflow in (B)FV homomorphic encryption
I just tried reading the paper "Somewhat Practical Fully Homomorphic Encryption" by Fan and Vercauteren but I got confused by their use of the coefficient-wise modulus.
They define the ...
2
votes
1
answer
56
views
Compute Intermediate Extensions of $\Bbb Q[\zeta]/\Bbb Q$.
Let $\zeta$ be a primitive $n^{\operatorname{th}}$ root of unity over $\Bbb Q$ then there is a natural isomorphism $$\operatorname{Gal}\left(\Bbb Q\left[\zeta\right]/\Bbb Q\right)\simeq \left(\Bbb Z/...
0
votes
0
answers
50
views
A prime $\mathcal{P}$ dividing $\mathbb{Q}(\zeta)$ divides $\Phi_{m}(\alpha)$
I came across the proof of the following fact in the Chapter $2$, Lemma $2.9$ of Lawrence CWashington's book, Introduction to Cyclotomic Fields.
Let $p$ be a rational prime, $n\in\mathbb{N}$ and $a\in\...
3
votes
2
answers
127
views
Using cyclotomic polynomials to show a polynomial is irreducible over $\mathbb{Q}$
I have been given the polynomial $$f(x)=x^8+x^7-x^5-x^4-x^3+x+1$$ and have been asked to show it is irreducible over $\mathbb{Q}$ by considering the product $(x^2-x+1)f$. (Looking it up, I realise $f$ ...
2
votes
0
answers
72
views
Cyclotomic Polynomials and The Existence of Infinite Prime Power
Prove that there exist infinitely many positive integers n such that all prime divisors
of $n^2 + n + 1$ are not greater than $\sqrt{n}$
This is a problem related to cyclotomic polynomial. It is ...
1
vote
1
answer
71
views
For $f \in \mathbb{Q}[x]$, does there necessarily exist $a \in \mathbb{Z}$ such that $af \in \mathbb{Z}[x]$ and is primitive?
I'm working through a proof from lecture notes in an algebra class that for all $n$, the $n$-th cyclotomic polynomial $\Phi_n$ has integer coefficients. The proof proceeds as follows:
Write $x^n - 1 =...
0
votes
0
answers
57
views
Polynomials of the form $X^n-c$
Is there any specific name for the polynomials of the form $X^n-c$ for some $n$ and $c$ is a complex number? They seem to be closely related to Cyclotomic polynomials.
0
votes
2
answers
75
views
Show that $Tr(A)$ is in the spectrum of $A+I$
If we have $p$ an odd prime number and the matrix $A$ $(p×p)$ with rational entries and we know that $\det(A^{p}+I)=0$, $\det(A+I)≠0$. How we can show $\operatorname{Tr}(A)$ is in the spectrum of $A+I$...
1
vote
1
answer
95
views
Find a Galois extension whose Galois group is $\mathbb{Z}_4 \times \mathbb{Z}_4$
In my notation, $\mathbb{Z}_n$ = the integers modulo $n$.
Find a Galois extension whose Galois group is $\mathbb{Z}_4 \times \mathbb{Z}_4$. (The additive group).
I thought about using cyclotomic ...
3
votes
0
answers
89
views
Intermediate Fields of $\mathbb{Q}(\zeta_{16})$ and Corresponding Splitting Polynomials
I'm trying to find all intermediate fields $\mathbb{Q} \subset E \subset \mathbb{Q}(\zeta_{16})$ and in particular, the polynomial that each of these fields split. I know that $\text{Gal}(\mathbb{Q}(\...
1
vote
1
answer
71
views
Frobenius automorphism modulo power of prime
This question is related to the one I have asked yesterday.
For an integer $m\geq 1$, consider the $m$th cyclotomic polynomial $\Phi_m(X)\in\mathbb Z[X]$. For an integer $r\geq 1$, we can find ...
0
votes
1
answer
59
views
Isomorphism between cyclotomic rings
This question is similar to the one posted here.
Let $m=m_1\cdots m_k$ be a positive integer decomposed into coprime prime powers $m_i$. For an integer $n\geq 1$, denote the $n$-th cyclotomic ...
2
votes
2
answers
132
views
Divisors count of $3^n\pm1$
During the investigation of $3^n\pm1$ visually saw that the divisors count of it are sums of $2^m$.
Especially if we take $n=p_1p_2$ ($p_i$ is prime) then at least for $n=p_1p_2<130$ it is either ...
0
votes
4
answers
94
views
$m+1$ generates the kernel of $Z_n^\times\to Z_m^\times$ where $m\mid n$ with the same prime factors
Suppose $m\mid n$. Using the First Isomorphism Theorem with respect to the homomorphism $$\begin{array}{rccc}f:&\mathbb{Z}_n^\times&\to&\mathbb{Z}_m^\times \\&x&\mapsto &x\bmod ...
1
vote
0
answers
25
views
Why is $\mathbb{F}_{p^r}$ the splitting field of the polynomial $X^{p^r-1}-1$? [duplicate]
Why is $\mathbb{F}_{p^r}$ the splitting field of the polynomial $X^{p^r-1}-1$? This is mentioned on my lecture notes but I don’t have a reference for this fact (and I couldn’t find it online).
0
votes
0
answers
27
views
Any normal third degree extension of $\mathbb Q$ contained in $\mathbb C$ must be contained in $\mathbb R$
We let $K\subset \mathbb C$ be a finite normal field extension of $\mathbb Q$ such that $[K:\mathbb Q]=3$. Show that $K\subset \mathbb R$.
I know that no cyclotomic extension of $\mathbb Q$ will do ...
0
votes
0
answers
48
views
On cyclotomics modulo prime powers
Regarding the ring $\mathbb{Z}[X]/\Phi_n(X)$ for the $n$'th cyclotomic polynomial $\Phi_n$, I find much literature on the nature of this ring taken modulo a prime $q$, that is literature on the ...
0
votes
0
answers
25
views
If $u$ is a unit of $\mathbb{Z[\xi_p]}$, $\frac{u}{\bar{u}}\neq -\xi_p^i$ for all $i$.
I am trying to prove the following:
Let $p$ be a prime. If $u$ is a unit of $\mathbb{Z[\xi_p]}$ (where $\xi_p$ is a primitive $p$-th root of unity), then $\frac{u}{\bar{u}}\neq -\xi_p^i$ for all $i$ ...
0
votes
2
answers
45
views
If $u$ is an $n$-th root of unity, $p$ is a prime number such that $p \nmid n$, then $P(u^p)=0$ where $P$ is the minimal polynomial of $u$
This is a step in a guided proof that the cyclotomic polynomial $\Phi_n$ is the minimal polynomial of $u$. I already know that $\Phi_n(0)=0$ so $P$ divides $\Phi_n$, I need to show the converse. Any ...
1
vote
0
answers
121
views
Prove that the roots of cyclotomic polynomial $\Phi_{p-1}(x) \equiv 0 (mod~p)$ are exactly the primitive roots mod p
$p$ is a prime, and $\Phi_{p-1}(x)$ denote the cyclotomic polynomial of order $p-1$. And I want to show the following:
$g$ is a solution of the congruence $\Phi_{p-1}(x) \equiv 0 (mod~p)$ if and only ...
2
votes
1
answer
59
views
If $1,\alpha_1,\alpha_2,..,\alpha_{n-1}$ denote the $n^{th}$ roots of unity, then what is $\prod_{k=1}^{n-1}(1-\alpha_k)$
Here's what we did in class :
$f(z)=z^n-1$ has all of the $n$ $n^{th}$ roots of $1$ as it's zeroes. Let's say that $\alpha_1=e^{\iota(2\pi/n)}$ and $\alpha_j=(\alpha_1)^j$ for $j\in[1,n-1]$. So $1,\...
1
vote
0
answers
13
views
density of low degree factors of X^N-1 in finite fields
Let N be an exponential number of the order O(p^n) for some p and n. How to estimate the density of (or as fraction of N) cardinalities of subsets of polynomials f(X) in GF(p)[X] such that
1.f(X) is ...
2
votes
2
answers
135
views
Stuck in a step of a proof that cyclotomic polynomials are irreducible.
I'm reading Additive Combinatorics by Tao and Vu and am stuck on a step in a proof they present (attributed to Gauss) that cyclotomic polynomials are irreducible over the integers. The argument ...
2
votes
0
answers
75
views
Solutions of $(x^p - y^p)/(x - y) = z^p $
I want to show that the diophantine equation
$ (x^p - y^p)/(x - y) = z^p $
where the prime $p > 3$, can just have trivial integer solutions $\{x, y, z\}$ like $\{1, -1, 1\}$
I used the theorem $IV$ ...
-1
votes
1
answer
59
views
How to prove that: Automorphism $\zeta_n\to\zeta_n^p$ leaves prime ideal factor of *p* unchanged. [closed]
Let's
(n,p)=1
$\zeta_n$ - n-root of unity
$\mathfrak p$ - prime ideal factor of prime number p
How to prove that automorphism $\zeta_n\to\zeta_n^p$ leaves $\mathfrak p$ unchanged.
2
votes
1
answer
144
views
If $P(P(x))=x^{36}$, does it imply $P(x)=x^6$?
Intro: This question has been inspired by the question If $P(P(x)-1) = 1 + x^{36}$ then $P(2)=$ . Here, we will consider (what was not explicitly mentioned in the original question) that $P$ is a ...
4
votes
1
answer
130
views
"Easy" proof that $\Phi_n$ has degree $\phi_n$
Let $\Phi_n(x)$ denote the minimal polynomial of $\zeta_n = e^{2\pi i/n}$ over $\mathbb{Q}$. Now it's clear that $\Phi_n$ is irreducible, so the difficulty is showing that it has degree $\phi(n)$, ...
1
vote
0
answers
101
views
$x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{F}_2$
I have a slight confusion about this argument below. Why did we need to show that there is no $\alpha\in \mathbb{F}_{2^2}^{\times}$ instead of $\mathbb{F}_{2}^{\times}$ in order to conclude?
We use ...
1
vote
1
answer
39
views
Constructing intersections in a regular polygon
Consider a regular polygon with $n$ vertices. The position of the vertices are given by $e^{2 i \pi k / n}$ for $k \in \{1 \ldots n\}$. The vertices are in $\mathbb{R}[i]$ but they are also in $\...
1
vote
1
answer
56
views
What is the correspondent sub-field of this cyclotomic extension, given by the Fundamental Theorem of Galois Theory?
I've been working on some problems regarding polynomials, and I ended up with the following question:
Suppose that $\zeta_{p^n}$ is a root of unity of order $p^n$, and consider the cyclotomic ...
1
vote
1
answer
134
views
Find $a \in \mathbb C$ such that $\mathbb Q (\zeta_5)= \mathbb Q(\sqrt 5, a)$ and $\left[ \mathbb Q(a): \mathbb Q \right]=2 $.
Let $\zeta_5= e^{\frac{2}{5} \pi i}= \dfrac{1}{4}(\sqrt 5 -1)+ i \left( \sqrt{\dfrac{5}{8}+ \dfrac{\sqrt 5}{8}} \right)$ be the principal fifth root of the unity. I know that $\left[\mathbb Q (\zeta_5)...
1
vote
0
answers
109
views
Cyclotomic Polynomial Proof
I am trying to understand this proof for the nth cyclotomic polynomial $\Phi_n(x)$ having integer coefficients, given in Fraleigh’s 7th edition A First Course in Abstract Algebra. The proof assumes $K$...
4
votes
1
answer
70
views
On some congruence in cyclotomic field
Let $k = \mathbb{Q}(\zeta_5)$ the $5^{th}$ cyclotomic field and $p$ a prime number verify $p\equiv 1 \pmod 5$.
Let $\lambda = 1-\zeta_5$ the unique prime of $k$ above $5$, precisely $5 = (1-\zeta_5)^...
1
vote
1
answer
110
views
Factoring cyclotomic polynomials in tree form
$\newcommand\ord{\text{ord}_n(q)}$
I've got the following formula for the $n$'th cyclotomic polynomial over the field $\mathbb{F}_q$ ($q=p^r$ and $(n,p)=1$) assuming $q\equiv1(\bmod m)$ as well as ...
3
votes
2
answers
209
views
Show that $1+\zeta+\dots+\zeta^{k-1}$ is a unit [duplicate]
Let $\zeta=e^{\frac{2\pi i}{p}}$ where $p\geq3$ is a prime. Consider the algebraic number field $K=\mathbb{Q}(\zeta)$. Let $k$ be a positive integer such that $(k,p)=1$ i.e., $k$ is co-prime with $p$. ...
3
votes
0
answers
54
views
Question on cyclotomic polynomials and the Möbius function
I'm doing an exercise on the Möbius function $\mu$. I've seen this equation but I don't understand it.
\begin{align*}
\mathrm{X}^{n}-1&= \prod_{d \mid n} \phi_d(X) \\
&=\prod_{d \mid n} \left(\...
0
votes
1
answer
47
views
If $s = 4m - 3$, then $\sigma(p^s) = (1 + p^{2m-1})(1 + p + \ldots + p^{2m-2})$. Is there a similar factorization for $\sigma(q^t)$ when $t=4n$?
Let $p,q$ be (odd) primes, and let $m,n,s,t$ be positive integers.
Denote the classical sum of divisors of the positive integer $x$ by $\sigma(x)=\sigma_1(x)$.
M. A. Nyblom showed that, if $s = 4m - 3$...
2
votes
0
answers
50
views
Some questions on cyclotomic polynomials
I observed that different books mention properties of cyclotomic polynomials in terms of lemmas (not obvious proof) and some books mention same thing as obvious thing. Here are two of them. Can one ...
1
vote
1
answer
43
views
How to write an arbitrary element of cyclotomic extension of 6th root of unity?
Let's say $\omega$ is a primitive $6^{\rm th}$ root of unity. Then we know $[\mathbb{Q}(\omega):\mathbb{Q}]=\varphi(6)=2$. If I count the number of linearly independent basis elements for $\mathbb{Q}(\...
0
votes
1
answer
17
views
Calculate $N(1-\xi_m)$, where $\xi_m= e^{\frac{2\pi i}{m}}$ and $m=p^l$
Let $K=\mathbb{Q}[\xi_m]$ be a number field, where $\xi_m= e^{\frac{2\pi i}{m}}$ and $m=p^l$. I want to calculate the norm of $(1-\xi_m)$. I know how to do this if $l=1$, but if $l> 1$ I get a bit ...
0
votes
0
answers
24
views
Simple proof that n divides $\sum_{1\le k<n, \gcd(k,n)=1} k$ [duplicate]
I was reading about cyclotomic polynomials defined as:
$$ \Phi_n(x) =
\prod_\stackrel{1\le k\le n}{\gcd(k,n)=1}
\left(x-e^{2i\pi\frac{k}{n}}\right)$$
The fact that the coefficients of these ...
1
vote
0
answers
45
views
Particular case of the law of quadratic reciprocity
Let $\mathbb{F}_q$ be a finite field of characteristic $p \neq 2,5$ .
What I've shown so far :
$x \in\mathbb{F}_q^* $ is a root of $\Phi_5 = X^4 + X^3 +X^2+X+1$ if and only if $x$ is of order 5 in $\...
0
votes
0
answers
74
views
Order and Structure of Galois group
I'm struggling with a question I've got as I can't seem to wrap my head around Galois theory much.
i)Prove that $\zeta^{2}$ is a primitive 8th root of unity and $\zeta^{4}$ is a primitive 4th root of ...
3
votes
0
answers
89
views
What can be said about the primality of Zsigmondy Numbers?
Let $\mathcal{Z}(n,a,b)=\frac{\Phi_n(a,b)}{\gcd (\Phi_n(a,b),n)}$ by the $n$-th Zsigmondy number to base $(a,b)$, where $\Phi_n(a,b)$ is the $n$-th homogeneous cyclotomic polynomial. Zsigmondy proved ...
2
votes
4
answers
117
views
How to prove $X^{4}+X^{3}+X^{2}+X+1$ is irreductible in $\mathbb{F}_{2}$
How to prove $X^{4}+X^{3}+X^{2}+X+1$ is irreducible over $\mathbb{F}_{2}$.
The main 2 "weapons" I have at my disposal is the Eisenstein criteria and reduction criteria but neither seem to ...
3
votes
1
answer
371
views
factoring a cyclotomic polynomial modulo a prime
I am having trouble with this: it appears that $x^{12} - x^6 + 1$ has a root $\pmod p$ only when $p \equiv 1 \pmod{36},$ in which case it completely factors as twelve linear terms.
It is easy to ...
1
vote
1
answer
75
views
Is $g(x,y)= \frac{f(x^{2y+1},y)}{f(x,y)}$ always an integer?
This question is similar to this other question:
Let $$ f(x,y):= \frac{x^y -1}{x+(-1)^y}$$
and $$ g(x,y):= \frac{f(x^{2y+1},y)}{f(x,y)}.$$
Let $y\ge1$ be an integer. Show that $g(x,y)$ is a ...
0
votes
0
answers
45
views
Cyclotomic polynomial with nonnegative coefficients
I know that the cyclotomic polynomial $\Phi_m = \prod (x-\zeta_m^c)$ for all $c$ coprime to $m$, with $\zeta_m$ a primitive $m^{th}$ root of unity is the unique minimal polynomial with integral ...
0
votes
0
answers
32
views
Why is $\mathbb{Q}[\zeta_{p}] = \{a_{0}, a_{1}\zeta, \dots, a_{p-2}\zeta^{p-2}, a_{i} \in \mathbb{Q}\}$, where $p \geq 2$ is a prime?
Let $p$ be a prime number $\geq 2$ and $\zeta := \zeta_{p}$ a complex number where $\zeta \neq 1$ and $\zeta^p=1$, i.e., is a $p$th root of unity. This is a question from a brazillian book, Introdução ...
0
votes
1
answer
143
views
Norm of generator of prime ideal
Let $K=\mathbb{Q}(\zeta_n)$ be a cyclotomic field. For a prime ideal $\mathfrak{p}$ in the ring of integers $\mathcal{O}_K$, we can write $\mathfrak{p} = (p,f_i(\zeta_n))$, where $\mathfrak{p}\cap\...