All Questions
45 questions
17
votes
2
answers
2k
views
Polynomials for natural numbers and irreducible polynomials for prime numbers?
Let $p$ be a prime and $n$ be a natural number.
Define inductively for prime numbers: $f_1(x) := 1$, $f_2(x):=x$, $f_p(x) := 1+\prod_{q\mid p-1} f_q(x)^{v_q(p-1)}$.
Is $f_p(x)$ always irreducible for ...
- 3,064
3
votes
1
answer
188
views
Is there a uniform family of polynomials $f_p(x) =x^2 + a(p)x + b(p)$ such that $f_p(x)\in \mathbb{Z}[x]$ is irreducible and irreducible mod $p$?
Let $p\in\mathbb{Z}$ be a positive prime number.
Is there a "uniform" family of polynomials $f_p(x) =x^2 + a(p)x + b(p)$ of degree two such that $f_p(x)\in \mathbb{Z}[x]$ is both irreducible ...
- 237
1
vote
0
answers
107
views
Polynomial divisible by unbounded primes with exponent one
Let $f(x)$ be squarefree polynomial with integer coefficients and
degree at least $3$.
Is it true that for all sufficiently large $n$, $f(n)$ is divisible
by prime $p$ with exponent one and $p$ is ...
- 25.4k
5
votes
1
answer
392
views
Divergence of primes dividing polynomials
Let $Q : \mathbb{Z} \rightarrow \mathbb{Z}$ be a polynomial. Form the set
$$M_{Q} := \{p:\text{ }p\text{ is prime, }\exists n_{p}\in \mathbb{Z}\text{ so that }p|Q(n_{p})\}$$
Is $$\sum_{s \in M_{Q}}\...
- 227
3
votes
1
answer
1k
views
Root of polynomials in a finite field
I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number.
For example : $p=2^{2020}-69$ ...
- 4,074
5
votes
0
answers
160
views
Reducibility of $f(x)^{2^n}+1$ and $f(x)^{2^n}+g(x)^{2^n}$
Related to generalized Fermat numbers.
Let $f(x),g(x)$ be coprime polynomials with integer coefficients.
Assume that if $f(x)$ or $g(x)$ are of the form $h(x)^k$ then $k$ is power
of two.
Q1 Is it ...
- 25.4k
18
votes
1
answer
713
views
Is the p-adic density of the image of a polynomial always rational?
This question was previously posted here on MSE.
Let $P(x)$ be a polynomial with integer coefficients, and let $p$ be a prime number. For $n\in\mathbb N$, let $I_n$ be the number of integers $i\in\{1,\...
- 654
5
votes
0
answers
370
views
Large prime factors of n²+1
Iwaniec proved (and many people extended) that the number of $n \le x$ for which $n^2+1=P_2$ (product of at most two primes) is $\gg x/\log x$. I am wondering what is known/can be proved for the ...
- 51
5
votes
1
answer
347
views
Checking if polynomial can be iterated and only take prime values
I have the polynomial $f(x) = x^2-x+1$ and I am wondering if there is a positive prime value $p$ such that $f(p),f^2(p),f^3(p)\dots$ are all prime.
I have ran some computer simulations and I feel like ...
- 1,835
6
votes
1
answer
931
views
What are prime number values of the trinomial $q(n) = n^2 + n + 41$? Assuming $n$ is a positive integer
Are there infinitely many integer values $n$ such that $q(n)$ is a prime number?
Numerical evidence points to a yes answer.
This is similar to Landau's 4th problem from 1912.
(The conjecture that ...
- 187
5
votes
0
answers
205
views
Is there a polynomial version of Wilson's theorem which can avoid Cramer flavored conjectures?
Wilson's theorem states that a natural number $n > 1$ is a prime number if and only if the product of all the positive integers less than $n$ is one less than a multiple of $n$.
Is there a version ...
- 13.9k
4
votes
0
answers
187
views
Small solutions of $f(x_1,...,x_n) \equiv 0 \pmod p$
Let $f(x_1,...,x_n)$ be polynomial with integer coefficients.
Is the following possible:
For almost all primes $p$ exist integers $X_1,...,X_n$
such that:
$f(X_1,...,X_n) \ne 0$
$f(X_1,...,X_n) \...
- 25.4k
4
votes
0
answers
182
views
Integer polynomial inducing a permutation of order $p$ on $\mathbb{Z}/p\mathbb{Z}$ for infinitely many $p$
Let $Q\in \mathbb{Z}[x]$ be a non-linear polynomial. Can there exist infinitely many primes $p$ such that $Q(\mathrm{mod}\:p)$ induces a permutation $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$ ...
user158636
16
votes
2
answers
1k
views
Injective integer polynomial is injective modulo some prime
Let $Q\in \mathbb{Z}[x]$ be a polynomial defining an injective function $\mathbb{Z}\to\mathbb{Z}$. Does it define an injective function $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$ for some prime ...
user158636
1
vote
0
answers
133
views
Primes which do not divide certain homogeneous polynomials
It is known that if $x^2 + y^2 = z^2$ is a primitive Pythagorean triplet then $z$ is not divisible by any prime of the form $4k-1$. The following is a generalization of this classical result which ...
- 5,470
-2
votes
1
answer
181
views
Polynomials of minimum degree that interpolate primes in intervals
Given an interval $[a,b]$ what is the minimum degree of univariate polynomials in $\mathbb Q[x]$ that passes through all primes between $a$ and $b$ (denoted by $\mathbb P[a,b]$ with total number of ...
- 1,826
2
votes
0
answers
84
views
quadratic residues and cubic polynomials [closed]
I'm really not sure about this, but I've heard somewhere that for any prime $p$,
$|\sum_{x=0}^{p-1} (\frac{ax^3 +bx^2 +cx +d}{p} ) |\le \sqrt{2p}$ holds.
Does anyone know a proof for this inequality ...
- 141
1
vote
1
answer
119
views
Sequences of positive integers $(a_{k})_{k \in \omega}$ that only give finitely many zeros modulo $p_{k}$ in total for all polynomials
Let $(a_{k})_{k \in \omega}$ be a sequence of positive integers such that $a_{k} < p_{k}$, $a_{k} \leq a_{k+1}$ and $\lim_{k \rightarrow \infty} a_{k}=\infty$ where $p_{k}$ is the k-th prime ...
- 311
0
votes
1
answer
356
views
A sufficient condition for a set of primes to be the set of reducibility of an integer polynomial
Let $P$ be the set of all positive primes. Let $S$ an arbitrary infinite subset of $P$ satisfying the following assumption: there exists a finite Galois extension $K$ of $\mathbb{Q}$ and a conjugacy ...
user145520
3
votes
1
answer
253
views
Сomplement of the set of numbers of the form $ 4mn - m - n$?
Numbers of the form $4mn-m-n$ where $m,n\in\mathbb{Z}^+$ are
$$
A=\{2, 5, 8, 11, 12, 14, 17, 19, 20, 23, 26, 29, 30, 32, 33, 35, \ldots\}
$$
The set complement of the above set is
$$
B=\{1, 3, 4, 6, ...
- 841
7
votes
3
answers
401
views
On $\{P(x)+Q(y):\ x,y=0,\ldots,p-1\}$ with $p$ prime
QUESTION: Is my following conjecture (formulated in 2016) true? How to solve it?
Conjecture. For any non-constant polynomials $P(x)，Q(x)\in\mathbb Z[x]$, there is a positive integer $N(P,Q)$ ...
- 15.6k
2
votes
0
answers
121
views
How to choose a prime p s.t. n-th cyclotomic polynomial splits into as much as possible irreducible polynomials while p is almost constant size?
The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $n$ is usually ...
- 33
4
votes
1
answer
287
views
Why do polynomials $x^n + 1 \bmod N$ close a shorter cycle when $n$ is even than when $n$ is odd?
Polynomials $f(x) \bmod N$, where $f(x)$ is of integer coefficients and $N$ is a composite of two distinct primes $p, q$, form a cycle --- usually leaving a tail because the cycle tends to close not ...
- 43
1
vote
0
answers
202
views
Prime generating polynomials
Continuation to this previous question.
According to Lemke-Oliver, an irreducible polynomial $G$ of degree $g$ with positive leading coefficient and $\Gamma_G\neq0$ (with $\Gamma_G$ a certain factor ...
- 195
9
votes
0
answers
324
views
Semi-primes represented by quadratic polynomials
According to Lemke-Oliver, irreducible quadratic polynomials $G$ with positive leading coefficient and $\rho(2)<2$, (where $\rho(m)$ denotes the number of incongruent solutions to the congruence $G(...
- 195
8
votes
2
answers
354
views
Let $f \in \mathbb{Z}[x]$. Does $\bar{f}$ have as many roots in $\mathbb{F}_p$ as $f$ has in $\mathbb{C}$ for infinitely many primes $p$?
Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial. Consider $\bar{f} \in \mathbb{F}_p[x].$ Let $\rho_p$ be the number of distinct roots of $\bar{f}$ in $\mathbb{F}_p$, and let $\rho$ be the number ...
3
votes
1
answer
205
views
How does the minimal degree of a monic polynomial with all values divisible by $p^n$ asymptotically behave?
Let $p$ be a prime number. For every $n \in \mathbb N$, let
$A_{p,n}:=\{\deg P(X) : P(X)\in \mathbb Z[X]$ is monic and $p^n|P(m), \forall m \in \mathbb Z$ $\}$ .
As user abx notes below, $A_{p,n}$ ...
user111492
19
votes
2
answers
2k
views
Is there an explicit expression for Chebyshev polynomials modulo $x^r-1$?
This is an immediate successor of Chebyshev polynomials of the first kind and primality testing and does not have any other motivation - although original motivation seems to be huge since a positive ...
- 18.4k
3
votes
0
answers
408
views
The second conjecture about the degrees of special polynomials
Define the congruence "modulo m" on exponential Taylor series following the previous post (A conjecture about the degrees of special polynomials)
It has been conjectured, that if we define the ...
- 237
6
votes
1
answer
665
views
On the distribution of roots modulo primes of an integral polynomial
For motivation and related questions, see below.
Rough sketch of the question.
View $\bigsqcup_{p \text{ prime}} (\mathbb{Z}/p\mathbb{Z})$ as a ‘subset’ of the unit circle, via $a\pmod{p} \mapsto e^{...
- 83
8
votes
1
answer
1k
views
An elementary lower bound on the number of primes
Recall the second Chebyshev function: $$\psi(x) = \sum_{p \leq x} \lfloor \log_p x \rfloor \log p$$ where $x$ is a positive integer, and $p$ runs over all primes $\leq x$.
In a hunt for an "...
- 11.3k
6
votes
1
answer
364
views
Negative coefficient in an almost cyclotomic polynomial
Let $a,b,c,d$ be four prime numbers. We set the polynomial :
$$P(X)=\frac{(1-X^{abc})(1-X^{abd})(1-X^{acd})(1-X^{bcd})(1-X^a)(1-X^b)(1-X^c)(1-X^d)}{(1-X)^2(1-X^{ab})(1-X^{ac})(1-X^{ad})(1-X^{bc})(1-X^{...
- 75
7
votes
2
answers
883
views
Unexpectedly prime rich cubic polynomial
We got a cubic polynomial which is unexpectedly prime rich.
Let $f(x)=29160 x^3 + 30132 x^2 + 8046 x + 643$ and
$\pi_f(n)$ the number of primes values of $f(x)$ for $x \in [1,n]$.
Let $F(n)=\frac{\...
- 25.4k
17
votes
3
answers
2k
views
About the prime divisors of values of polynomials
Let $P$ be a polynomial having integer coefficients (and degree $\geq 3$), and let $\mathscr P_P$ be the set of prime numbers dividing some value $P(n)$ with $n \in \mathbb Z$.
Is it true that $\...
- 3,866
4
votes
0
answers
279
views
Analog of Euler's factoring technique
Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials?
Euler's two squares factoring states that numbers ...
- 13.9k
5
votes
1
answer
727
views
Sum of two squares and implication of Bunyakovsky conjecture
Bunyakovsky's conjecture states that a polynomial with integer
coefficients takes infinitely many prime values at integers,
unless this is impossible for trivial reasons.
Let $a_1(x), a_2(x), a_3(x), ...
- 25.4k
1
vote
0
answers
195
views
Lower bound on number of smooth values of polynomial at primes
Given a polynomial $f$, it is known believed that the number of smooth values of $f$ has a positive proportion (for fixed $u$, $\lim_{X\rightarrow\infty} \frac{|\{ n < X\ :\ f(n)\ is\ X^u\ smooth \}...
- 4,593
4
votes
2
answers
865
views
Can a polynomial be almost always divisible by a member of a finite set of primes?
Special case of Bunyakovsky conjecture
Let $f(x)$ be non-constant irreducible polynomial with integer
coefficients, no fixed prime factor and positive
leading coefficient. Let $S$
be a finite set of ...
- 25.4k
4
votes
3
answers
623
views
Set of primes dividing polynomials and composition
For a non-constant polynomial $A \in \mathbb{Z}[x]$, let $\mathcal{P}(A)$ denote the set of prime numbers $p$ which divide $A(n)$ for some integer $n$. If $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ for ...
- 85
12
votes
1
answer
1k
views
Least prime $p$ such that an irreducible polynomial of degree $n$ has no root modulo $p$?
This question is inspired by an old question of Greg Kuperberg, about how small is the first prime $p$ which makes a given monic polynomial $P$ with integral coefficient have a (simple) root modulo $p$...
- 26k
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730
22
votes
1
answer
2k
views
Primes represented by two-variable quadratic polynomials
I'm looking over a paper, "Primes represented by quadratic polynomials in two variables" [1] which attempts to characterize the density of the primes in two-variable quadratic polynomials. ...
- 9,114
3
votes
3
answers
958
views
solutions to equation mod a prime
I know that characterizing the solutions to an equation in a finite field is generally difficult, but I was wondering if anyone had anything to say about the equation
(ab)^2 + a^2 + b^2 = 0 mod p
I ...
- 39
32
votes
1
answer
4k
views
Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $
EDIT, 9 March 2014: when I asked this in 2010, I did not have the courage of my convictions, and so did not ask for an if and only if proof, as Kevin Buzzard quite properly pointed out. Such problems ...
- 25.7k
11
votes
3
answers
2k
views
What primes divide the discriminant of a polynomial?
Given a monic polynomial $p(t) = t^n + ... + c_1 t + c_0$ with integer (or rational) coefficients and with roots $a_1, \dots a_n$, we can compute its discriminant, which is defined to be $\prod_{i< ...
- 111