All Questions
Tagged with polynomials elementary-number-theory
668
questions
-6
votes
0
answers
32
views
How is this rough draft of a proof that $(x^2+10x-3=0)∉Qred? [closed]
I wanted to prove that the above quadratic is irreducible over Q without using common methods such as quadratic formula, discriminate, completing the square, rational root theorem, Eisensteins ...
5
votes
1
answer
82
views
Given nonzero $p(x)\in\mathbb Z[x]$. Are there infinitely many integers $n$ such that $p(n)\mid n!$ is satisfied?
This problem comes from a famous exercise in elementary number theory:
Prove that there are infinitely many $n\in\mathbb Z_+$ such that $n^2+1\mid n!$.
I know a lot of ways to do this. A fairly easy ...
- 786
1
vote
1
answer
36
views
Factoring integer polynomials by factoring their values then interpolating
Let $f\in\mathbb Z[x]$ be a non-constant integer polynomial, and let $n$ be a positive integer which is at least $\deg f$. Choose positive integers $a_1<\cdots<a_n$ such that $f(a_i)\neq 0$ for ...
- 1,101
0
votes
3
answers
103
views
Does there exists an integer-coefficient polynomial that extracts the highest digit of an integer in base p? [closed]
Given an odd prime $p$, a positive integer $1 \lt n$, and an integer $x \in \mathbb{Z}/p^n\mathbb{Z}$, does there exist an an integer-coefficient polynomial that extracts the highest digit of $x$?
The ...
- 9
3
votes
1
answer
149
views
Find non-zero polynomials $f(n)$ and $g(n)$ with integer coefficients such that $(n^2+3)f(n)^2+1=g(n)^2$
Find non-zero polynomials $f(n)$ and $g(n)$ with integer coefficients such that $(n^2+3)f(n)^2+1=g(n)^2$.
This problem comes from Pell's equation, which states that for $\forall m\in\mathbb{N}^*$, ...
- 681
-4
votes
1
answer
70
views
Does this proof of $f(X)\not\equiv0\pmod{n}$ (for this specific $f$) imply there is an integer $k$ such that $f(k)\not\equiv0\pmod{n}$? [closed]
A generalization of the following statement is proven in "Primes is in P":
$(X+1)^n-X^n-1\equiv0\pmod{n}$ iff $n$ is prime.
Their proof of the only if part goes something like: if $q^k\Vert ...
- 133
3
votes
2
answers
147
views
A conjecture about the sum of Faulhaber polynomials mod 2.
Context: In this question I asked about "Finding a polynomial function for alternating $m$ numbers of odds and even numbers in sequences" I noticed that all Faulhaber polynomials are ...
- 6,620
8
votes
1
answer
169
views
Finding a polynomial function for alternating m numbers of odds and even numbers in sequences
Context: The function $(-1)^n$ alternates between $1,-1$ because $n$ alternates between odd and even, I was trying to find a function $f(n)$ that will give $m$ positives then $m$ negatives and so on ...
- 6,620
2
votes
1
answer
68
views
Polynomial Divisibility by Factorial Plus One [closed]
Find all polynomials with integer coefficients $f$ such that $f(p) \mid (p-1)! + 1$ for all primes $p$.
Using Wilson’s theorem we find that $f(p)=p;-p$ satisfy the problem. I also thought about using ...
- 637
1
vote
0
answers
157
views
Prove $a^n+\frac{1}{a^n}$ is rational if $a+\frac{1}{a}$ is rational [duplicate]
Assume
$$a+\frac{1}{a}$$
is a rational number.
Prove that $a^n+\frac{1}{a^n}$ is a rational number.
I can easily prove it using induction. I would like to know if is it possible to prove it without ...
- 392
3
votes
2
answers
172
views
Sufficient condition for a polynomial $f$ over $\mathbb Q$ to be linear is $f(\mathbb Q)=\mathbb Q$.
I am reading a book (Polynomial Mappings by W. Narkiewicz) on invariance of polynomial maps where I found the following result along with a proof:
Theorem: Let $f\in\mathbb Q[x]$ be a polynomial such ...
- 1,101
1
vote
0
answers
55
views
Do polynomials taken modulo integers compose?
Intuitive Idea:
Say we have polynomials modulo positive integers; for instance, $f(x) = 3x + 1\pmod 5$ and $g(x) = 5x^2 - x + 3 \pmod 7$. (Yes, there is some abuse of notation here.) We may "...
- 181
19
votes
2
answers
766
views
Is the smallest root of a polynomial always complex if the coefficients is the sequence of prime numbers?
The smallest root of a polynomial is defined as the root which has the smallest absolute value. Consider the polynomial $a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$. I observed that if $a_n$, is the ...
- 20.8k
0
votes
0
answers
45
views
Proof of existence of composite number P(x) if P is a non-constant polynomial [duplicate]
Prove that if $P$ is a polynomial with integer coefficients, which is not a constant polynomial, then there is a natural number $x$ such that $P(x)$ is a composite number.
My first thought was to ...
- 11
1
vote
0
answers
70
views
Divisibility of sum of powers of $2$ and $3$
I am looking at the question, whether for some positive integers $h,k,l\in\mathbb{N}$ we have that
$$\left(3^{h+l}-2^{2(k+h)+l}\right)\,\big| \left( 2^{2k+l+1}-2^2 3^{l-1}-2^{2k+1}3^l\right).$$
I ...
- 1,271
3
votes
0
answers
40
views
Calculating $P(x) \bmod x^{k}$ at target value by sampling $P(x)$
Motivation
The motivation behind this question is from a computational mathematics and combinatorics background. It is often convenient to express a problem as a product of polynomials so that the ...
- 294
0
votes
0
answers
24
views
Difference between polynomials with integer and non integer coefficiants regarding number of roots of polynomial [duplicate]
There is a prior question to show that polynomial of degree 7 with all integer coefficiants has 7 integer values $ P(x1,x2...x7)=+-1$ cant be expressed as product of two polynomials with integer ...
- 33
-1
votes
1
answer
82
views
Prove that if polynomial with integral coefficients has a solution in integers, then the congruence is solvable for any value of modulus $m$. [duplicate]
Prove that if $F(x_1, x_2, \ldots, x_n) = 0$, where $F$ is a polynomial with integral coefficients, has a solution in integers, then the congruence $F(x_1, x_2, \ldots, x_n) \equiv 0 \pmod{m}$ is ...
- 402
3
votes
0
answers
90
views
On thickness of binary polynomials
OEIS A169945 introduces the concept of thickness of a polynomial as the magnitude of the largest coefficient in the expansion of the square of the polynomial. Considering the $2^{n+1}$ polynomials $p(...
- 9,592
0
votes
0
answers
49
views
Can you check this proof? Find all polynomials $P(x)$ with integer coefficients such that for each natural number $n, n$ divides $P(2^n)$ [duplicate]
Is this a good proof? I think it is allright but I am not sure. I want to prove this polynomial must be constant, with P(x)=0.
Suppose P isn't constant Let ord_p(2) denote the smallest number 0<k ...
- 27
2
votes
0
answers
69
views
Unsure about a step in proving $e$ is transcendental
I'm currently trying to understand the proof of e being transcendental in Julian Havil The Irrationals, but not sure how the following is concluded.
A polynomial of degree $mp+p-1$ is defined on the ...
- 107
20
votes
4
answers
578
views
When can products of linear terms differ by a constant?
We have
$$ X(X+3) + 2 = (X+1)(X+2)$$
and
$$ X(X+4)(X+5) + 12 = (X+1)(X+2)(X+6)$$
and
$$ X(X+4)(X+7)(X+11) + 180 = (X+1)(X+2)(X+9)(X+10).$$
Do similar polynomial identities exist for each degree?
That ...
- 2,071
0
votes
0
answers
53
views
Extended Euclidian algorithm for polynomials [duplicate]
this question follows one from yesterday that got deleted because it was a duplicate.
The problem was about solving this equation (in $ℚ[x]$) :
$$f(x)(2x^3 + 3x^2 + 7x + 1) + g(x)(5x^4 + x + 1) = x + ...
- 93
0
votes
0
answers
54
views
Simplest failures of Hasse principle
I’m trying to understand the simplest cases where a Diophantine equation has solutions in the reals and modulo all prime powers, but not in the integers.
I know classes of examples of degree 6 in 1 ...
- 361
4
votes
1
answer
84
views
When is $3136 - 6272 n + 3136 n^2 + n^{14}$ a perfect square?
When is $3136 - 6272 n + 3136 n^2 + n^{14} =z^2$ for $z \in \mathbb N$?
Here was my approach: Consider $3136 - 6272 n + 3136 n^2 + n^{14} \pmod 5$. Since any integral square must be equivalent to 0, 1,...
- 972
1
vote
1
answer
39
views
Can relative (or even absolute) quotient size be calculated from a list of polynomials which are multiples of a given variable?
I am working on a Diophantine equation in integers $x$ and $y$. The equation has been solved, so I already know the solutions (there are four) — I am trying to find a more elementary solution.
Through ...
- 7,929
8
votes
0
answers
200
views
Prove that $\Phi_{420}(69) > \Phi_{69}(420)$
Let $\Phi_n(x)$ denote the nth cyclotomic polynomial. Prove that $\Phi_{420}(69) > \Phi_{69}(420)$.
Observe that if $\phi$ denotes the Euler-phi function, \begin{align}
\phi(420) &= (2^2-2) \...
- 1,225
0
votes
0
answers
46
views
Prove that the order of 2 modulo 2n+1 is odd
Let $n$ be a positive integer such that there exists a polynomial $f(x) \in \mathbb{F}_2[x]$ of degree n such that $f(x)\cdot x^n f(1/x) = 1+x+\cdots + x^{2n}\in \mathbb{F}_2[x]$. Prove that the order ...
- 1,225
6
votes
1
answer
300
views
Multiply an integer polynomial with another integer polynomial to get a "big" coefficient
I am new to number theory, I was wondering if the following questions have been studied before.
Given $f(x) = a_0 + a_1 x + a_2 x^2 \cdots + a_n x^n \in \mathbb Z[x]$, we say that $f(x)$ has a big ...
- 1,641
1
vote
0
answers
133
views
$\lfloor a^m\rfloor \equiv -1\mod n $ for $a = n+\sqrt{n^2 - n}$
Let $n \ge 2$ be an integer. Let $a = n+\sqrt{n^2 - n}$. Prove that for any positive integer m, we have $\lfloor a^m\rfloor \equiv -1\mod n$.
Suppose $(x-a)(x-c) = x^2 + ux + v \in \mathbb{Z}[x]$ (...
- 869
1
vote
1
answer
99
views
Prove that the sequence $(a_n)_{n\ge 1}$ is unbounded
Let $f(x)$ be a non-constant polynomial with integer coefficients. For any $n\in\mathbb{N}$, let $a_n$ be the remainder when $f(3^n)$ is divided by $n$. Prove that the sequence $(a_n)_{n\ge 1}$ is ...
- 1,225
2
votes
1
answer
84
views
On a weak polynomial version of Erdős conjecture
This question is motivated by Erdős conjecture on arithmetic progressions. It is a weaker conjecture than Erdős' one.
Erdős conjecture on arithmetic progressions states, "If $A$ is a large set, ...
- 20.7k
0
votes
0
answers
68
views
Trouble understanding a number theory problem related to polynomials
I am following, titu's book on number theory, the level of examples is escalating at a very quick rate which caused me trouble understanding them.
The problem is as follows:
Let $f$ be a polynomial ...
0
votes
0
answers
79
views
Why does a polynomial over a composite modulus have more than $d$ roots, but over a prime modulus it has at most $d$ roots? [duplicate]
Is it true that when considering a degree $d$ polynomial $p(x)$ in a composite modulus $q$, it has more than $d$ roots (i.e., more than $d$ solutions to $p(x) \equiv 0 \pmod q$), and that when we ...
- 3,019
1
vote
1
answer
60
views
Find all possible values of $\alpha$
Suppose $n ≥ 0$ is an integer and all the roots of $x^3 + αx + 4 − (2 × 2016^n) = 0$ are integers.
Find all possible values of α.
This question is from INMO 2017. The solution goes this way . . .
Let ...
- 2,646
-1
votes
1
answer
45
views
Existence of Positive Integer Solution for a Polynomial Equation [closed]
Let $f(x)$ be a polynomial of degree n, and it is known that $f(x)$ has no positive integers as its roots. In other words, there are no positive integer values of x for which $f(x)=0$. Consider the ...
7
votes
0
answers
197
views
For which positive integers $m$ and $n$ do $x^m-x$ and $x^n-x$ being integers imply that $x$ is an integer
This is inspired by
Prove that $x$ is an integer if $x^4-x$ and $x^3-x$ are integers.
For which positive integers $m$ and $n$
do $x^m-x$ and $x^n-x$
being integers
imply that
$x$ is an integer.
$x$ is ...
- 108k
0
votes
1
answer
80
views
Parametric solution of quartic diophantine equation in three variables
How can I handle the quartic diophantine equation in three variables $x$, $y$ and $z$ $$x^4-x^2=y^2-z^2$$ in general, i.e, does exists a (three-variable) parametric solution?
What I've tried is ...
3
votes
2
answers
421
views
Polynomial system of equations over integers
I want to solve the system of equations:
$$\begin{cases}
x^4+4y^3+6x^2+4y = -137 \\
y^4+4x^3+6y^2+4x = 472
\end{cases}
$$
$x, y \in \Bbb{Z}$.
It most definitely amounts to messing around with algebra ...
- 1,488
1
vote
1
answer
106
views
$f(x)$ has a factor $(x-r)$, if and only if $f(r) = 0$ - why can't $f(r)$ be a factor of $(x-r)$?
It is clear from the polynomial remainder theorem that $(x-r)$ is a factor of $f(x)$ if $f(r) = 0$
Is there no function $f(r)$ which is a factor of $(x-r)$? does this only happen when $f(r) = 0$?
$f(x)...
1
vote
1
answer
86
views
Find all integer polynomials $f(x)$ such that $f(n)\mid 2^n-1$ for all $n\in\mathbb{N}^+$. [duplicate]
Find all integer polynomials $f(x)$ such that $f(n)\mid 2^n-1$ for all $n\in\mathbb{N}^+$.
So far, I have tried to plug in values of $n$, and see where that takes me. For example, plugging in $n=1$ ...
user1200609
1
vote
0
answers
53
views
A Theorem Regarding the Factorability of a Quadratic [duplicate]
After noticing some patterns in delta epsilon proofs, I was able to prove a theorem regarding the factorability of quadratics. My question is, if this proof is correct, has it been documented before? ...
- 142
2
votes
4
answers
531
views
Find the least prime $p$, such that for some positive integers $a$, $b$, $c$, $d$, $(ab + a - b)(bc + b - c)(cd + c - d)(da + d - a) = 2023^2p.$
Problem
Find the least prime $p$, such that for some positive integers $a$, $b$, $c$, $d$, $(ab + a - b)(bc + b - c)(cd + c - d)(da + d - a) = 2023^2p.$
This problem is from the algebra round of a ...
- 167
1
vote
1
answer
314
views
Find all integers $n$ such that $(n - 1)^2 + 3$ divides $n^3 + 2023$.
Problem: Find all integers $n$ such that $(n - 1)^2 + 3$ divides $n^3 + 2023$.
My Work:
$(n - 1)^2 + 3 = n^2 - 2n + 4$, which is always greater than 0 for all integers n.
Therefore, if $n^2 - 2n + 4$ ...
- 167
6
votes
1
answer
161
views
divisibility of the numerator of a alternating harmonic series
Let $p = 6n+1$ be a prime number. Prove that the numerator of the rational number
$$
\sum_{k=1}^{4n}\frac{(-1)^{k-1}}{k}
$$
is divisible by $p$.
What I've tried: Let
\begin{align}
g(x) &= (x+1)...
- 95
2
votes
0
answers
43
views
Maximal divisor of pairwise differences
Let $r \in \mathbb{N}$ be fixed. Define the function:
$$f : \mathbb{Z}^r \to \mathbb{N}, \quad (a_1, ..., a_r) \mapsto \max_{n \in \mathbb{Z}} \prod_{i<j} \gcd((n-a_i), (n-a_j))$$
It is perhaps not ...
- 2,466
4
votes
2
answers
217
views
prove that $x^{20}+(1-x)^{20}-20$ is square free
Prove that $x^{20}+(1-x)^{20}-20$ is square free (i.e. has no repeated roots).
Note that the claim holds iff $p'(x)$ is coprime to $p(x)$, where $p(x)=x^{20}+(1-x)^{20}-20$. $p'(x)= 20x^{19}-20(1-x)^{...
- 2,031
7
votes
1
answer
177
views
Product of differences of roots of unity
$\DeclareMathOperator{\lcm}{lcm}$
Denote by $\mu_n$ a primitive n-th root of unity. Examples suggest that
$$\prod_{0\le k\lt a \\ 0 \le l \lt b \\ k/a \neq l/b} (\mu_a^k - \mu_b^l)=\pm \lcm(a,b)^{\gcd(...
- 1,252
2
votes
0
answers
109
views
smallest monic polynomial that induces the zero function modulo $p^k$
I came across this problem while doing an assignment from my number theory class, and hope that someone can point me to a correct direction!
Define $d(n)$ to be the degree of the smallest monic ...
- 21
20
votes
2
answers
709
views
For what $n$ can we find a degree $\leq n-2$ polynomial such that $P(i) \in \{0 , 1 \}$ for $i \in [n]$, but not all identical.
For what $n$ is the following statement true:
There exists a choice of $ a_1, a_2, \ldots a_n \in \{ 0, 1 \}$, not all identical, such that there is a polynomial $F(x) \in \mathbb{R}[x]$ of degree at ...
- 70.4k