Skip to main content

Questions tagged [polynomial-congruences]

Questions about congruences where the modulus is a polynomial. For questions concerning congruences between polynomials where the modulus is an integer, use the tag (modular-arithmetic) instead.

Filter by
Sorted by
Tagged with
0 votes
0 answers
24 views

What is the inverse of $[x^4+x^3+1]$ in $Z_{2}[x]/(x^2+x+1)$? [duplicate]

$x^4+x^3+1$ and $x^2+x+1$ are co-prime in $Z_{2}[x]$, so $[x^4+x^3+1]$ is a unit in $Z_2[x]/(x^2+x+1)$. Then, $[x^4+x^3+1]$ has an inverse, which I thought I could find by finding $a,b,c,d$ satisfying ...
Per Christian Strøm's user avatar
1 vote
1 answer
33 views

The number of solutions to the congruence equation $P(x) \equiv 0 (\mathrm{mod}\ p^\alpha)$

Let $P(x)$ be a polynomial with integer coefficients, and $p$ be a large prime. I want to find the number of solutions to the congruence equation $$P(x)\equiv 0(\mathrm{mod}\ p^\alpha).$$ In my ...
Misaka 16559's user avatar
2 votes
1 answer
66 views

Is there any prime $p$ such that $6x^3 − p^2 − y^2 = 0$ has an integer solution?

I need to find whether there is any prime for which $6x^3 − p^2 − y^2 = 0$ has a integer solution. For prime $p \neq 3$ ,considering this equation in modulo $3$ ,I find that there is no solution. But ...
ビキ マンダル's user avatar
1 vote
1 answer
53 views

corollary of the partition congruence

I was going though the paper of Ramanujan entitled Some properties of p(n), the number of partitions of n (Proceedings of the Cambridge Philosophical Society, XIX, 1919, 207 – 210). He states he found ...
Sangama's user avatar
  • 23
-1 votes
2 answers
34 views

Polynomial Congruence Equation

Struggling with this question: $15x^3 -6x^2 + 2x +26 \cong 0 \mod343$. Here is what I have so far: By Hensel's Lemma if we have a solution to $f(x) \cong 0\mod p$ we can find solution to $f(x) \cong 0\...
Ncrest's user avatar
  • 23
0 votes
0 answers
68 views

if a homogeneous polynomial is the square of a polynomial modulo $x^2 + y^2 - 1$, is it also congruent to a sum of squares of homogeneous polynomials?

Let $f(x, y)$ be a homogeneous polynomial with real coefficients in $2$ determinates $x , y$. Suppose that $$f(x, y) \equiv g(x, y)^2 \pmod{x^2 + y^2 - 1}$$ for some polynomial $g(x, y)$, where $g(x, ...
Colin Tan's user avatar
  • 143
0 votes
2 answers
232 views

$F[x]/(p(x))$ contains the roots of $p(x)$

The following theorem and exercise are from "Abstract Algebra, An Introduction, 3rd Edition, Thomas W. Hungerford" Corollary 4.19 Let $F$ be a field and let $f(x) \in F[x]$ be a polynomial ...
JustANoob's user avatar
  • 1,669
0 votes
1 answer
161 views

Regarding output for $p$-adic expansion on PARI/GP

The input sqrt$(2+O(7^{10}))$ on PARI/GP yields the output: $ 3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 + 6*7^9 + O(7^{10}).$ Which is essentially the solution of the congruence $X^2 \...
SARTHAK GUPTA's user avatar
0 votes
1 answer
18 views

Find coefficient $c$ that makes a valid congruences

I've got a problem from book Integer, Polynomials, and Rings by Ronald S. Irving, page 227. The question: Is there a value of the coefficient $c$ in the field $\mathbb{R}$ that makes $x^4+3x^3+2x+1 \...
liz_chan's user avatar
4 votes
1 answer
122 views

How many quadratic functions mod 12 have exactly two roots?

There was a challenge question in this Socratica video and [EDIT: I misunderstood the question and] boy is it giving me a headache! I thought the question was: How many $(a,b,c)$ triples in $\Bbb Z_{...
vaebnkehn's user avatar
  • 143
0 votes
0 answers
72 views

Show that a congruence involving prime power is solvable.

Let $a,b$ be integers not divisible by a prime $p$, show that if $ax^p \equiv b\pmod {p^2}$ is solvable then, $ax^p \equiv b\pmod {p^n}$ is solvable. What I've tried is by letting $x = w + v$, then $...
link's user avatar
  • 53
2 votes
2 answers
497 views

Most efficient solution to find polynomial congruence for 0 mod p

I was given the polynomial $$f(x) = x^4 + 2x^3 + 3x^2 + x + 1$$ and told to find $$f(x) \mod 17 = 0 $$ I found the solution to be $$x = 8 + 17n$$ However, I arrived at this solution by computing all ...
Nick Trotsky's user avatar
1 vote
1 answer
74 views

Let $f(x)=x^3+x^2-5$. Show that for $n=1, 2,3, ...$ there is a unique $x_n$ modulo $7^n$ such that $f(x_n)\equiv 0\pmod{7^n}$.

My gut feeling for solving this problem is to use strong induction. Starting with the base case $n=1$ we can check each of the seven congruence classes and find that $x_1=2$ is the unique solution. ...
Bryce Smith's user avatar
0 votes
1 answer
122 views

Two polynomials congruence modulo $p$ [closed]

This is a result that I found in a compettion. But I didn't known it is false or true. Let $n$ be a positive integer and $p$ be a prime divisor of $n$. Prove that if $$x^{\varphi(n)}-1\equiv (x^{p-1} -...
user avatar
0 votes
1 answer
153 views

How to solve a non-linear system of modulus equations?

I have the following problem: $$ 2x^2 + 8 \equiv 6 \;(\bmod\;13)$$ $$x \equiv 2 \;(\bmod\;15)$$ I have tried applying the Chinese remainder theorem, but could not figure out how to make it work, as ...
Maoepr3n's user avatar
1 vote
1 answer
99 views

Prove that $F(x)=(x^2-17)(x^2-19)(x^2-323)\equiv 0 \pmod{p^j}$ is solvable for all $p$ prime and $j\in\mathbb{N}$

Problem: Prove that $F(x)=(x^2-17)(x^2-19)(x^2-323)\equiv 0 \pmod{p^j}$ is solvable for all $p$ prime and $j\in\mathbb{N}$. My attempt: With the help of Euler's criterion, I was able to prove that $F(...
WLOG's user avatar
  • 1,296
1 vote
1 answer
58 views

Confusion about why the reduction of non-linear congruence seems to require only a single choice of prime power $p_i^{k_i}$

I have a question about solving non-linear congruences : So say that we have $f(x)\in \Bbb Z[x]$, and we want to solve $f(x)=0(\mod{p_1^{k_1}….}p_n^{k_n}$. My lecture notes tell me that this can be ...
excalibirr's user avatar
  • 2,795
0 votes
0 answers
256 views

Implication of theorem about congruence modulo p(x)

This question is related to this: Congruence modulo p(x) and this Congruence in F[x], proof involving infinity I'll just restate the theorem in question before my question: Let $F$ be a field and $...
Thomas Fjærvik's user avatar
1 vote
1 answer
46 views

A non-trivial solution for $\lambda_1 + 2 \lambda_2 + \cdots + (p-2)\lambda_{p-2} = 0$ in $\mathbb{Z}_p$

Let $K = \mathbb{Z}_p$, where $p$ is a prime number and $p \neq 2,3$ . Find a non-trivial solution for the system: $$\left\{ \begin{align} & \lambda_1 + \lambda_2 + \cdots + \lambda_{p-2} = 0 \ ...
Croos's user avatar
  • 1,809
0 votes
1 answer
142 views

How to do congruence-class arithmetic?

When working through this question: Write out the addition and multiplication tables for the congruence-class ring $F[x]/(p(x))$. $F=\mathbb{Z_2}$; $p(x)=x^{3}+x+1$. [Question #1 in section 5.2: ...
AMN52's user avatar
  • 37
2 votes
1 answer
550 views

Elementary Number Theory - Determining if there exist roots for a polynomial congruence with a prime modulus

If we consider something like the polynomial $f(x) = x^3-1$, and we want to know if there exists any solutions at all for $x^3 - 1 \equiv 0 \ (mod \ p)$, where $p$ is prime, is there a way to answer ...
Stawbewwy's user avatar
0 votes
1 answer
329 views

For $f(x)=0 \mod n$ with $n=2 \mod 4$ has solution congruence classes as $2^{k-1}$ for $k$ is number distinct prime dividing $n$

I was encountered one example in Elementary Number theory By Jones and Jones . I understand whole example except what is argument for number of soultion congruence classes for $n=2 \mod 4$ as $2^{k-1}...
Curious student's user avatar
1 vote
1 answer
159 views

Congruent solution implies an integer solution.

Let us consider a polynomial $p\in \mathbb{Q}[x]$ with $p(\mathbb{Z})\subseteq \mathbb{Z}$, such that for each $a\in \mathbb{N},\,p(n)\equiv 0 \,(\text{ mod } a\,) $ has a solution for some $n\in \...
Surajit's user avatar
  • 1,216
0 votes
1 answer
642 views

Solve $x^2 -3x+2 \equiv 0 \pmod 6$ [closed]

I need help understading how to solve this equation. $x^2-3x+2 \equiv 0 \pmod 6 $ I'm having trouble with the said equation.
Harrys Kavan's user avatar
1 vote
2 answers
107 views

Congruence modulo ($2^{10}$)

Good evening, i’d like to discuss the following congruence which i’m stuck with, with you, hoping to find answers : Find the number of solution of $$x^5-16x\equiv 0 \mod 2^{10}$$ I think i have to ...
jacopoburelli's user avatar
-1 votes
1 answer
101 views

Prove that $a^2,a^4,...,a^{p-1}$ are the quadratic residues modulo $p$.

Let $p$ be an odd prime $(p,a)=1$. Then, by Fermat's theorem, $a^{p-1}$ is congruent to $1$ (mod $p$). If $p-1$ is the smallest positive value of $e$ such that $a^e$ is congruent to $1 $(mod $p$), ...
HelloWorld's user avatar
2 votes
2 answers
596 views

Lagrange Theorem Application in Number Theory

I'm studying the theory of congruences in number theory. I found a theorem called Lagrange Theorem that state Given a prime p , let $f(x)=c_0+c_1x + \cdots + c_n x^n$ be a polynonomial of degree n ...
user avatar
1 vote
1 answer
141 views

Elementary Number Theory: Cubic Congruences

Solve $5x^3 -2x + 1 \equiv 0 $ mod 243. We're using Hensel Lifting theorem to solve. I am trying to use the example we did in class but I am not following. I know we need to the dericative and find ...
Rose's user avatar
  • 289
4 votes
1 answer
65 views

Find $f\in \mathbb{Z}_{p}\left[X\right]$ such that $f\left(X^{m}\right)$ is divisible by $\Phi_{p-1}$.

Let $p$ be a prime natural number, let $m\in\left\{ 2,\,\ldots,\,p-2\right\}$ and let $\Phi_{p-1}\in \mathbb{Z}_{p}\left[X\right]$ the cyclotomic polynomial corresponding to $p-1$. Find the ...
thebalans's user avatar
  • 103
0 votes
2 answers
80 views

How to find the multiplicity of a polynomial?

How can you find the multiplicity of a polynomial? I have to find all $n \in \mathbb{N}$ such that $9\mid n^4+n^3-2n^2+n+4$. The recommended method is to solve by congruence but I haven't been able ...
whatDoYouMean's user avatar
3 votes
3 answers
158 views

Can I used polynomial congruence for prove 3 divide $n^3-n$?

I'm not sure this method can work to prove 3|$n^3-n$? by let we have polynomial congruence $n^3-n\equiv 0(mod3)$ then if all residue class mod 3 are the roots of congruence 3|$n^3-n$ the ...
Lingnoi401's user avatar
  • 1,765
6 votes
5 answers
3k views

Solutions of $x^2-6x-13 \equiv 0 \pmod{127}$

I started learning number theory, specifically polynomial congruences, and need help with the following exercise. Here it is: Does the congruence $x^2-6x-13 \equiv 0 \pmod{127}$ has solutions? I ...
user avatar
2 votes
0 answers
82 views

Let $R = \mathbb{Q}[x]$ and let $I = (x^2 + 2x + 2)R$ be the principal ideal generated by $x^2 + 2x +2$. Two questions are below.

i) Show that any element of $R$ is congruent modulo $I$ to a unique polynomial of the form $ax+b$ where $a,b \in \mathbb{Q}$? ii) Show that any element of the quotient ring $R/I$ is of the form $\...
M.Byrne's user avatar
  • 181
1 vote
1 answer
769 views

Solution of polynomial congruence

We all know that If $(a,m) = 1$ , Then the linear congruence $ax\equiv b(mod\ m)$ has exactly one solution. Can we conclude something similar for quadratic congruence $ax^{2}+bx+c\equiv 0(mod\ m)$ ( ...
SARTHAK GUPTA's user avatar
3 votes
1 answer
217 views

How to solve system of congruences of polynomial? [closed]

Find a polynomial $p(x)$ such that $p(x)\ \equiv 1\mod\ x^{100}$ and $p(x)\ \equiv 2\mod\ (x-2)^3$
ILiveInValhalla's user avatar
0 votes
2 answers
31 views

$f \in\mathbb Q[X]$, $ [f] = [f \operatorname{div} X^5] $ in $ \mathbb Q[X]/\equiv_{X^5} $

I have to proof if the following statement is true or false: $f \in\mathbb Q[X]$, $ [f] = [f \operatorname{div} X^5] $ in $ \mathbb Q[X]/\equiv_{X^5} $ Since I am new to that I have tried to think ...
jublikon's user avatar
  • 943
0 votes
1 answer
239 views

rewriting a polynomial congruent to 0 mod m

If $m$ is an odd integer and $m$ and $a$ are relatively prime, we can multiply the inverse of $a$ and complete the square to rewrite $$ax^2 + bx + c ≡ 0 \mod m $$ as $$y^2 ≡ d \mod m$$ express $d$ in ...
greenteam's user avatar
  • 333
2 votes
1 answer
1k views

solve x for a cubic congruence equation with large prime mod.

For $x^3 = 123456789 \pmod{1000000007}$ given $1000000007$ is a prime. Find $x$. My school only teach us about linear congruence equation, and it is an extra credit question. Therefore, I think the ...
Hugo's user avatar
  • 33
2 votes
1 answer
545 views

Equality of polynomial functions modulo n

Fix positive integers $m$ and $n$. For all polynomial functions $f,g: \mathbb{Z}^m \to \mathbb{Z}$ define the equivalence relation $\sim$ by $$f \sim g \iff \forall x \in \mathbb{Z}^m \ ( \ f(x) \...
DAS's user avatar
  • 732
1 vote
2 answers
489 views

solve $x^2 -4x +13 \equiv 0 \pmod{81}$?

How do I solve $x^2 -4x +13 \equiv o \pmod{81}$ ? I know that this is the same as $x^2 -4x +13 \equiv x^2 + 2x + 1 \equiv (x +1)^2\equiv 0\pmod{3^4}$ but why is $x \equiv -1\pmod{3}$ the only ...
Jamelia Jones's user avatar
-1 votes
2 answers
155 views

Is there a solution for $x^6 \equiv 5 \pmod {71}$? [closed]

How can I verify that a solution exists for $$ x^6 \equiv 5 \pmod {71} $$
greedsin's user avatar
  • 581
2 votes
1 answer
60 views

Understanding the following lemma

While studying primitive roots, I came across the following lemma: Lemma: Let $p$ and $q$ be primes and suppose that $q^\alpha\mid p-1$, where $\alpha\geq 1$. Then there are precisely $q^\alpha - q^{\...
Apurv's user avatar
  • 3,373
2 votes
2 answers
324 views

Can the concept of congruence be applied to the remainder of a polynomial division?

I know this is a very simple question, so please I apologize but I am not familiar with it: Can the concept of (modular arithmetic) congruence be applied to the remainder of a polynomial division? ...
iadvd's user avatar
  • 8,905
1 vote
1 answer
551 views

Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$ [duplicate]

I tried to solve this equation but without a success: $3x^{2}+6x+1 \equiv 0 \pmod {19}$ I concluded hat $x(x+2)\equiv 6 \pmod{19}$, the only way i think to solve this is by just trying all the ...
ben's user avatar
  • 11
0 votes
1 answer
80 views

Polynomials in Finite Field

Given $\Bbb F_{32}=\Bbb F_2[X]/(X^5+X^2+1)$ where the polynomial is irreducible over $\Bbb F_2$, how would I compute $(a^4+a^2)*(a^3+a+1)$ given $a=[X]$ is the congruence class of [X]? Multiplying ...
sebastianross's user avatar
2 votes
1 answer
90 views

How to find all the roots in this ring?

Let $F:= \mathbb{F}_7[x]/(x^2+3x+1)$ Is it a field? Find all the roots in F of the polynom $f (Y) := Y^2+[3]_{F}Y +[1]_{F} \in F[Y]$. Attempt: It is a field, because $x^2+3x+1$ is irreducible $\in ...
Angelo Tricarico's user avatar
1 vote
1 answer
2k views

What is the congruence class of $x^3\mod x^3+x+1$?

I have a given Polynom congruence with a Polynom $x^3+x+1$ ... so the set of the congruence classes is $\{0, 1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$ But what would look this like? $$x^3\mod x^3+x+1\equiv ...
Toralf Westström's user avatar
3 votes
0 answers
106 views

Need hints on the following algebra problems.

I've been looking at these for over an hour and I don't understand how to do them. Any hints would be greatly appreciated. Let $p(x) = x^3 + x + 1$ and $F = Z_3[x]/\langle p(x)\rangle$. Factor $p(x)...
Don Larynx's user avatar
  • 4,703