All Questions
Tagged with congruences polynomials
8 questions
1
vote
1
answer
83
views
Complexity of solving system of binary quadratic equations modulo $3$
A special case of this question and
another question
What is the complexity of solving system of binary quadratic equations modulo
$3$?
$f_i(x_i,x_j)=0 \bmod 3, \deg{f_i}=2$.
Modulo $2$ can be ...
- 25.4k
5
votes
2
answers
287
views
Modulo $x^2 + y^2 - 1$, is every homogeneous polynomial that is a square of a polynomial, necessarily of sum of squares of homogeneous polynomials?
I am hoping this question is alright for Math Overflow. I didn't get a definitive solution in Math Stack Exchange.
Let $f(x, y) \in \mathbb{R}[x, y]$ be a homogeneous polynomial with real coefficients ...
- 331
1
vote
1
answer
89
views
Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)
Formally, let $K$ be a field, $a \in K[x]$, $D \subseteq K$, and $E = \{(x_i, a(x_i)) \mid x_i \in D\}$ be distinct evaluations of $a$ where $\lvert E\rvert > \operatorname{deg}(a)$ (so $E$ ...
- 539
3
votes
1
answer
195
views
Solutions to nonhomogeneous quadratic equation mod $N$
Is there any way to find non-trivial solutions to the equation $x^2 + y^2 - x \equiv 0 \mod{N}$? There are clearly several trivial solutions, for example $(x, y) = (0, 0), (1, 0), (2^{-1}, 2^{-1}), (2^...
- 1,703
1
vote
1
answer
111
views
Density of a set of numbers dividing a fixed number with polynomial exponent
Fix a positive integer $a>1$ and let $f\in\mathbb{Z}[x]$ be a polynomial with positive leading coefficient. We define a set $S$ of positive integers,
$$
S=\{n\in\mathbb{Z}^+:n\mid a^{f(n)}-1\}.
$$
...
- 1,096
8
votes
1
answer
407
views
Cardinality of the image of a polynomial modulo $p^n$
Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial and let $p$ be a prime number. I'm looking for results about $$N_f(p^k) := \#\{(f(n) \bmod p^k) : n \in \mathbb{Z}\},$$ as $k \to +\infty$, where $...
- 81
2
votes
0
answers
110
views
"Close" roots of polynomials and Pillai property
A sequence of integers $a(n)_{n \geq 0}$ has the Pillai property if there exists an integer $G \geq 2$ such that for all integers $k \geq G$ there exists an integer $n \geq 0$ such that none of the $k$...
- 33
7
votes
1
answer
1k
views
Roots of a polynomial in a finite field related to Fermat's Last Theorem
In my class, we proved the following condition: define the polynomial $P_l(x)$ as
$$P_l(x) = \sum_{r=1}^{l-1}{\frac{1}{r}x^{l-1-r}}$$
Then if for all $a \in \mathbb{Z}/l\mathbb{Z}-\{0,1\},$ $P_l(x)$...
- 495