Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
1
vote
1answer
27 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(...
1
vote
1answer
22 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 ...
0
votes
0answers
45 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 $...
1
vote
1answer
41 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 \ ...
0
votes
1answer
22 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: ...
2
votes
1answer
73 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 ...
0
votes
1answer
42 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}...
1
vote
1answer
58 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 \...
-1
votes
1answer
71 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.
1
vote
1answer
58 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 ...
-1
votes
1answer
70 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$), ...
2
votes
2answers
155 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 ...
1
vote
1answer
93 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 ...
4
votes
1answer
56 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 ...
0
votes
2answers
52 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 ...
3
votes
3answers
89 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 ...
6
votes
5answers
661 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 ...
2
votes
0answers
53 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 $\...
1
vote
1answer
477 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)$ ( ...
3
votes
1answer
152 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$
0
votes
2answers
26 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 ...
0
votes
1answer
80 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 ...
2
votes
1answer
729 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 ...
1
vote
1answer
258 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) \...
1
vote
2answers
293 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 ...
-1
votes
2answers
123 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} $$
2
votes
1answer
36 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^{\...
2
votes
2answers
88 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? ...
1
vote
1answer
298 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 ...
0
votes
1answer
61 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 ...
2
votes
1answer
80 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 ...
1
vote
1answer
920 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 ...
3
votes
0answers
97 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)...