Tagged Questions
6
votes
6answers
183 views
Representing the function $\mathbb Z_9\to\mathbb Z_9$, $f(0) = 1$, $f(1) = \ldots = f(8) = 0$ as a polynomial in $\mathbb Z_9[x]$
Let $\mathbb Z_9=\left\{0,1,2,3,4,5,6,7,8\right\}$ be the set of integers modulo 9 and $f:\mathbb Z_9 \rightarrow \mathbb Z_9$ be a function.
Assume $f(0)=1$, $f(1)=f(2)=...=f(8)=0$. What is the ...
2
votes
2answers
30 views
Infinite Integral Domains
Let $D$ be an infinite integral domain, and let $g,h \in D[X]$. Show that if $g(x) = h(x)$ for all $x \in D$, then $g = h$.
I understand this means a one-to-one correspondence, but how do I go about ...
3
votes
2answers
108 views
Polynomial $x^3- xy^3$ and the like over finite fields.
Let $f_{a,n}(x_1,x_2)$ be a polynomial in $\mathbb{F}_p[x_1,x_2]$, where $\mathbb{F}_p$ is a finite field or oder $p$ (perhaps, we may first assume that $p$ is prime) depending on $a\in\mathbb{F}_p$ ...
1
vote
2answers
68 views
Sum of divisors is prime implies number of divisors is prime.
I've seen this posted but I haven't seen this in depth as i need it. I turned this in as homework but only got 1 out of 3 on it, so any clarification would be wonderful.
Show that if the sum of all ...
5
votes
0answers
91 views
Proof that $t^8+2t^6+4t^4+t^2+1$ is reducible in $\mathbb{F}_p$
Prove that the polynomial $t^8+2t^6+4t^4+t^2+1$ is reducible in $\Bbb F_p$, for all $p\in \Bbb P$.
Here are some examples:
$t^8+2t^6+4t^4+t^2+1=(1 + t + t^4)^2\pmod{2}$
$t^8+2t^6+4t^4+t^2+1=(1 + t) (2 ...
3
votes
2answers
50 views
How often must an irreducible polynomial take a prime value?
Suppose $f(x)$ is an irreducible polynomial over $\mathbb Z$ of degree $n$. Is it always the case that there exist distinct $x_1,\ldots,x_{2n+1}\in \mathbb Z$ such that $f(x_1),\ldots,f(x_{2n+1})$ are ...
2
votes
0answers
62 views
question on minimal polynomial
Let $\alpha$ be a root of $x^3+3x-1$ and let $\beta$ be a root of $x^3-x+2$. Find the minimal polynomial of $\alpha^2+\beta$.
My attempt to solution was this: i found a monic polynomial with integer ...
8
votes
3answers
146 views
Using Hensel's Lemma to Factor a Polynomial over $\mathbb{Z}_4[x]$
We recently learned about codes over $\mathbb{Z}_4$, and Hensel's Lemma. The lemma is as follows:
Let $f(x) \in \mathbb{Z}_4[x]$. Suppose $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$, where $h_1(x), ...
10
votes
1answer
190 views
Why is $x^3-5x$ injective on the rationals?
I've found the statement on the internet that the polynomial $x^3-5x$ is injective on the rational numbers, but without any comments on how to prove it. I think it means it must be easy, but I don't ...
2
votes
2answers
67 views
Proof of lack of pure prime producing polynomials.
Now I have heard this (correct me if I am wrong) that for every polynomial, there is some positive integer for which it is composite. What is the most elementary proof of this.
1
vote
3answers
62 views
Can a non-integer polynomial w/ natural number domain have natural number range?
If we have a polynomial function, such that one of its coefficients are not an integer, is it possible that for all natural numbers (0 exclusive) it will return a natural number? Please provide ...
0
votes
1answer
23 views
Distinct-degree factorization
I'm trying to understand distinct-degree factorization from Wikipedia.
I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$.
We start with $i=1$. I calculate $g = ...
1
vote
1answer
25 views
Given $p(x)$ is a polynomial of degree $n$, and $r$ to be its root, how to prove that $|r| \le \max(1, \sum_{i=1}^n |{a_i \over a_0}|)$?
Let $p(x)=a_0x^n+a_1x^{n-1}+\cdots+a_n,a_0 \ne 0$ to be univariate (1 variable) polynomial of degree $n$.
Let $r$ be its root, i.e. $p(r)=0$.
How can I prove that:
$$|r| \le \max\left(1, ...
0
votes
1answer
57 views
Formal identity for sum of polynomials over a finite field.
Suppose $F$ is a finite field of order $q$ a prime power. If $f\in F[x]$ of degree $t$, set $|f|=q^t$. Let $\sigma(f)=\sum_{g\mid f}|g|$ where the sum is over the monic divisors of $f$.
Why does
...
2
votes
1answer
89 views
Determining the sign of the Gauss sum under the change of variable $x\mapsto 1+u$.
I'm having a hard time deciphering some old notes. The aim is to determine the sign of the Gauss sum. Paraphrasing:
Take the polynomial
$$
...
1
vote
1answer
75 views
$x^{6}+30x^{5}-15x^{3}+6x-120$can't be written as products of two polynomials of rational coefficients and positive degrees.
Prove that $x^{6}+30x^{5}-15x^{3}+6x-120$ can't be written as a product of two polynomials of rational coefficients and positive degrees.
0
votes
0answers
105 views
prove cubic equation has no positive integer root
prove $q_1t^3+(k_2-1)t^2-k_2((q_1^2-1)k_1+1)^2=0$ has no Positive integer root, t is variable , $q_1$ is constant and $k_1,k_2$ are parameter
$q_1>0, k_1>0, k_2>0$, and all characters ...
1
vote
1answer
57 views
Proof of discovering two large prime numbers in polynomial time
$N=p*q$ is a product of two distinct primes. Show that if $\phi(N)$ and 2N are known, then it is possible to compute p and q in polynomial time.
so, I know that $\phi(N)=(p-1)(q-1)$
Given this, if ...
5
votes
1answer
87 views
Irreducible polynomials over $F_q$ with exponents of the form $q^k - 1$.
Let $q$ be some prime power. Is there an explicit family of irreducible polynomials in $F_q[X]$ of the form $\sum_j a_j X^{q^j - 1}$? Thanks!
1
vote
6answers
285 views
Proof by “infinite induction”
Prove that $\sum_{i=1}^{n} i^3 = \left( \frac{n(n+1)}{2} \right)^2$.
We can check this is true for n=0,1,2,3,4. Since the right side is a polynomial of degree 4, and the left side is a sum of ...
2
votes
2answers
72 views
Encode the message $[1,1,0,1,1,0,1]$ in BCH code based on the field $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1}$
So here's what I understand so far:
$\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1} = GF(16)$
The code is written as $[x^{14},x^{13},x^{12},x^{11},x^{10},x^{9},x^{8}$ $|$ ...
1
vote
0answers
35 views
Does an irreducible polynomial in K(t)[x] give an irreducible polynomial in K[t][x]
Let $K[t]$ be the ring of polynomials over a field $K$. Let $K(t)$ be its fraction field. Let $f$ be an irreducible polynomial in $K(t)[x]$. There exists an element $a\in K[t] $ such that $af$ is in ...
1
vote
1answer
111 views
Generate a polynomial w/ integer coefficients whose roots are rational values of sine/cosine?
I'm a high school calculus/precalculus teacher, so forgive me if the question is a little basic. One of my (very gifted) students recently came up with a construction yielding a quartic, one of whose ...
1
vote
2answers
90 views
About a certain type of polynomial
Let $p$ be a polynomial over the set of positive integers such that $p(n) > n$ for all positive integers $n$. It is also known that for every positive positive integer $m$ , there exists a term of ...
0
votes
3answers
111 views
Reducible polynomial + integer = Reducible polynomial?
Reducible polynomial + integer = Reducible polynomial ?
As the title says.
More specific :
For every integer $n$, does there exist a pair of polynomials $p(x)$ and $q(x)$ such that:
...
1
vote
0answers
90 views
Matiyasevich polynomial proof
Can someone provide a proof, or a link to a proof, of why does the Matiyasevich polynomial always generate primes for the nonnegative results? Any help will be appreciated.
2
votes
0answers
94 views
Restriction on polynomial with integer coefficients
Let $P$ be a polynomial with integer coefficients such that for every positive integer $n$, $P(n)$ divides $2^n - 1$.
Show that $P(x) =1$ or $P(x) = -1$ for all $x$.
1
vote
2answers
41 views
Polynomial factors
Why must $x^2 + x + 1$ be a factor of $x^5+x^4+x^3+x^2+x+1$?
I know that when we divide $x^5+x^4+x^3+x^2+x+1$ by $x^3+1$ we get $x^2 + x + 1$, but is there an argument/theorem or anything that ...
1
vote
1answer
153 views
How to demonstrate that there is no all-prime generating polynomial with rational cofficents?
It seems like there is no polynomial with finite variables known, which could generate all prime numbers, by integer assignments. Is there a proof that such polynomial can not exist and does anyone ...
0
votes
0answers
55 views
Computing Swinnerton-Dyer polynomials?
The formula for Swinnerton-Dyer polynomials is given here. However it doesn't seem to readily lend itself to fast computation. I'm ideally looking for an algorithm which computes it fairly quickly ...
3
votes
1answer
118 views
Roots of rational equation with multiple variables?
Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$.
For $k = 1$, it can be ...
1
vote
1answer
251 views
Solving a polynomial modulo an integer
Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot ...
5
votes
2answers
212 views
Polynomials representing primes
Suppose over $\mathbb{Z}$ we are given an irreducible polynomial $p(x)$.
Can we say that $p(x)$ at least represents a prime as $x$ runs through integers?
Thanks in advance
8
votes
1answer
122 views
Homogeneous polynomials in two variables taking integer values
It is known that ${x\choose 0},{x\choose 1},\ldots,{x\choose n}\in\mathbb{Q}[x]$ is a $\mathbb{Z}$-basis for set of polynomials of degree at most $n$ which map $\mathbb{Z}$ into itself.
For fixed ...
1
vote
0answers
129 views
A special factorization
Suppose that monic polynomial $f(x)\in\Bbb Z[x]$ such that for all $m\in\Bbb Z$, $m>1$, there's no integers $\langle r,r_1,\ldots,r_m\rangle$ such that $f(r)=f(r_1)\cdots f(r_m)$. Is there any ...
4
votes
2answers
135 views
Proving the Möbius formula for cyclotomic polynomials
We want to prove that
$$ \Phi_n(x) = \prod_{d|n} \left( x^{\frac{n}{d}} - 1 \right)^{\mu(d)} $$
where $\Phi_n(x)$ in the n-th cyclotomic polynomial and $\mu(d)$ is the Möbius function defined on the ...
2
votes
3answers
144 views
When is this polynomial equal to a square?
When is $f(k):=8k^2+8k+1$ a square for $k\in\mathbb Z_{\geq 0}$?
How do I begin on this? I see $f(k)$ is a square for $k=0,2$, but I do not know where to go from here.
1
vote
1answer
57 views
Finding generators of cubic Kummer extensions
Let $K$ be a number field containing $\mu_3$, the third roots of unity. Consider a monic irreducible cubic polynomial $f \in K[x]$ whose discriminant $\Delta$ is a square in $K$. Thus the splitting ...
13
votes
1answer
288 views
Roots with equal fractional parts
Question. ¿Does there exist an integer $n>1$ such that there exist positive integers $a,b$ such that $\{\sqrt[n]{a}\}=\{\sqrt[n]{b}\},a\neq b$ and $a$ and $b$ aren't perfect n-th powers? ( $\{x\}$ ...
4
votes
1answer
113 views
A simple-looking diophantine equation
Consider the diophantine equation $Q(x,y,z)=0$, where $x$, $y$ and $z$
are nonnegative integer unknowns and
$$
Q(x,y,z)=x^3 + (-2y + 2)x^2 + ((z - 6)y + (2z + 1))x + ((2z - 4)y + 3z)
$$
Since the ...
7
votes
1answer
99 views
Number of roots
Would I be right in thinking that $x^m\equiv 1 (\mod n)$ has only $m$ distinct roots? If not, would it be true if m,n are coprime or simply distinct primes? My gut feeling is that there should ony be ...
5
votes
2answers
3k views
Reed Solomon Polynomial Generator
I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
11
votes
2answers
505 views
What is the simplest ellipse that goes through exactly 13 lattice points?
The ellipse $-30 x + 3 x^2 - 10 y - 3 x y + 4 y^2$ goes through exactly 11 lattice points.
Another such ellipse is $4 - 30 x + 2 x^2 - 5 y - x y + 3 y^2$. What is the simplest ellipse that goes ...
7
votes
0answers
288 views
The radical solution of a solvable 17th degree equation
(The question is at the bottom of the post.) Here's a "natural" solvable 17-th deg eqn with small coefficients:
$$\begin{align*}
x^{17}-6 x^{16}&-24 x^{15}-42 x^{14}-31 x^{13}-23 x^{12}-7 ...
5
votes
1answer
462 views
Are the primes found as a subset in this sequence $a_n$?
Below is a introduction that contains some background to my question. The question is found at the bottom.
By calculating the eigenvalues of the matrix defined by the recurrence:
$\displaystyle ...
0
votes
3answers
78 views
Splitting a multiplication into multiple smaller steps, reaching the same result
Suppose I have a number, x, which should be doubled every second.
If one had a function which is called exactly once every second, the solution would be simple: All you would have to do was ...
3
votes
1answer
400 views
How many solutions are there to $F(n,m)=n^2+nm+m^2 = Q$?
Let $n,m$ be two positive integers, we consider:
$$F(n,m)=n^2+nm+m^2$$
Let $Q$ be one value reach by $F(n,m)$.
How many different pairs $(n,m)$ verify $F(n,m)=Q$?
28
votes
0answers
711 views
All polynomials with no natural roots and integer coefficients such that $\phi(n)|\phi(P(n))$
Let $P(x)$ be a polynomial with integer coefficients such that the equation $P(x)=0$ has no positive integer solutions. Find all polynomials $P(x)$ such that for all positive integers $n$ we have ...
3
votes
2answers
110 views
The equation $F(x) \equiv 0 \pmod m$ has integer solution for x
Let $F(x)=(x^2-17)(x^2-19)(x^2-323)$ and let $m$ be a positive integer. How can one show that the equation $F(x) \equiv 0 \pmod m$ has an integer solution?
3
votes
4answers
683 views
Simple formula for integer polynomial with $2\sin(2\pi/n)$ as a root?
Is there a simple formula an integer polynomial that $2\sin(2\pi/n)$ satisfies?
For $2\cos(2\pi/n)$ the answer is relatively nice. For any given $n$, we have $2\cos(2\pi/n)= z + z^{-1}$ where $z = ...
