0
votes
1answer
38 views

Modulo Quadratic Polynomials

Can you, given a large number N, find a, b, c such that ax^2 + bx + c = 0 has at least N roots? All of this is in any mod you choose.
2
votes
1answer
16 views

Polynomial factorisation on integers modulo n

Is there a known (efficient) algorithm to compute the list of factors of a polynomial modulo $n$ (for any integer $n$)? For example in $\mathbb Z_8$, $X^2+2X$ has a list of 4 factors (multiplicity 1 ...
1
vote
1answer
24 views

Factoring in terms of Irreducibles

Factor the polynomial $x^5 + 2x^3 + 3x^2 + 1$ as a product of irreducible polynomials in $\mathbb{Z}_5[x]$. My thoughts: I know what the definition of an irreducible function is but as far as methods ...
1
vote
1answer
37 views

How to give irreducible factorization in $\mathbb{Z}_5$?

I have this polynomial: $$f=x^5+2x^3+4x^2+x+4$$ How can i find the irreducible factorization(in $\mathbb{Z}_5$)?I can find the roots easily but thats not enough.
1
vote
1answer
28 views

Find a polynomial mod $n$ injective on a given set

This question is inspired by this challenge on CodeGolf.SE, in which the goal is to create a hash function with specified collisions. I thought a polynomial over the integers mod $n$ might be a nice ...
0
votes
1answer
50 views

Galois field splitting a polynomial

Can someone explain to me how i would go about doing a problem like this? I don't really know where to start. GF refers to a Galois field. I'm struggling to even understand exactly what they want me ...
2
votes
1answer
25 views

modulo of 2 polynoms

I'm trying to understand the example given in the wikipedia explanation of the algorithm of Reed Solomon: http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction. We have $p(x) = 3x^6 + ...
0
votes
4answers
49 views

polynomial time in finding constituent prime factors of an integer

If given an integer n = pq, p and q are primes, and a way of computing phi(n) in polynomial time is given. Can we also get the value of p and q in polynomial time? The answer is we can, but how? We ...
1
vote
2answers
77 views

Modular arithmetic with polynomial

Given n=pq, where p and q are primes, P(x) is polynomial and z∈Zn. I need to prove that: P(z) ≡ 0 mod n iff P(z mod p) ≡ 0 mod p AND P(z mod q) ≡ 0 mod q. If i ...
0
votes
0answers
22 views

Why CRC 32 Generator is not divisible by 11?

The CRC 32 Generator is a 33 bit bin number: 100000100110000010001110110110111 According to the pdf (Page 18): http://www.cs.illinois.edu/class/fa07/cs438/slides/CS438-04.Error.pdf Odd number of ...
1
vote
2answers
81 views

quadratic equation with two variables

i try to solve the equation below has a solution or not $x^2-97y-40 =0$ if solution exists, $x^2-40$ must be congruent to 0 modulo $97$. if i could show the congruence above implies that ...
2
votes
0answers
32 views

Congruence of polynomials

Prove that $y^i \equiv y^{i \pmod 4} \pmod {y^4 + 1}$ for all $i \ge 0$. Any hints on how to solve this? I don't even know where to start.
4
votes
1answer
133 views

Fast way to find the smallest root $\mod M$ of a polynomial

Suppose you're given a polynomial of degree $d$ with integer coefficients: $$ P(x) = \sum_{i=0}^{d}{a_i x^i} $$ Is there a fast way to find the smallest root modulo $M$, where $M$ is some composite ...
1
vote
3answers
215 views

Show $f(X)=a_nX^n+\cdots+a_1X+a_0$ has degree $n$ modulo $N$, $f(a)\equiv 0$ (mod $N$) then $f(X) \equiv (X-a)g(X) $(mod $N$)

In Niels Lauritzen, Concrete Abstract Algebra, I'm having trouble showing the following: The problem starts out like this: $f(X)=a_nX^n+\cdots+a_1X+a_0, a_i \in \mathbb Z, n \in \mathbb N$ Part ...
4
votes
2answers
67 views

Multiplicative polinomial inverse revisited

As it usually goes with asking questions for a third person... You don't get it right the first time. Question I asked here is as follows: Let $A(x)$ be a polynomial with integer coefficients. Is ...
0
votes
2answers
393 views

Polynomials' multiplicative inverse

Let $A(x)$ be a polynomial with integer coefficients. Is there always a polynomial $B(x)$ for which $$A(x)\cdot B(x)\equiv 1\pmod n$$ (for a given integer $n$). If the answer isn't yes, an answer ...
1
vote
1answer
91 views

how to interpret theorem about polynomial factorization over modulo ring?

polynomial $X^n+a_1X^{n-1}+...+a_n \in \Bbb Z_2[X]$ doesn't have linear factors $\iff a_n(1+\sum a_i) \neq 0$. How then $f(X)=X+1$ can has no linear factors? Doesn't the condition expands to ...
2
votes
1answer
79 views

Related To Polynomial Division

How to prove the following result Show how a polynomial with odd number of term will never be divisible by a divisor with $x+1$ as factor for modulo $2$ arithmetic. I don't have any idea.
3
votes
1answer
69 views

Find all integer solutions of $35x^{31} + 33x^{25} + 19x^{21} \equiv 1 \pmod{ 55}$

Find set of all integers x for which the following holds: $35x^{31} + 33x^{25} + 19x^{21} \equiv 1 \pmod {55}$ Since $55 = 5\cdot 11$, simultaneous congruences: $35x^{31} + 33x^{25} + 19x^{21} ...
4
votes
2answers
90 views

Finding root using Hensel's Lemma

Hensel's Lemma calculates root of a polynomial $\in \mathbb{Z}_p[X]$ but is there any other significance to other branches of mathematics or outside mathematics? Why is finding root of ...
5
votes
6answers
267 views

Show that $x^4 +1$ is reducible over $\mathbb{Z}_{11}[x]$ and splits over $\mathbb{Z}_{17}[x]$.

Reduction into linear factors $\mathbb{Z}_{17}[x]$: This part is not too hard: $x^4 \equiv -1$ mod 17 has solutions: 2, 8, 9, 15 so $(x-2)(x-8)(x-9)(x-15) = x^4 -34 x^3 +391 x^2-1734 x+2160 \equiv ...
0
votes
2answers
415 views

How to factor a polynomial modulo p?

Is there a general strategy to factoring a polynomial modulo p? I've looked on Google but I've had a hard time finding anything that specifically outlines an approach that I can understand.
0
votes
4answers
99 views

Polynomial division in $\mathbb{Z}_n[x]$

For which value of $n$ is $x^3-x$ divisible by $2x-1$ modulo $n$?
1
vote
1answer
182 views

GCD of two polynomials in Mod 2 [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ Let $p$ and $q$ be distinct primes. I wonder is the following statement always true? $$\gcd(x^p-1, x^q-1) ...
1
vote
2answers
69 views

Find the inverse of $\alpha^{38}$ in $\mathbb F = \mathbb Z_2[x]/\left<x^4+x+1\right>$

Let $\alpha$ be a root of $x^4+x+1$ and we are given some powers of $\alpha$ as linear combinations of $1,\alpha,\alpha^2$ and $\alpha^3$ $\alpha^4=\alpha+1$ $\alpha^5=\alpha^2+\alpha$ ... (the rest ...
0
votes
3answers
39 views

What are all the elements of $\mathbb Z_{2}[x] / <x^3+x+1>$

List all the elements of $\frac{\mathbb Z_{2}[x]}{<x^3+x+1>}$ (the set of remainders) Please verify my understanding: Since the polynomial is of degree 3, the remainders must have degree at ...
0
votes
1answer
52 views

How to get the equivalence classes for $m(x) = x^2+1$ in $\mathbb Z_{2}[x]$?

For $m(x) = x^2+1$ in $\mathbb Z_{2}[x]$, we have $$\frac{\mathbb Z_{2}[x]}{ \langle x^2+1 \rangle} = \{0, 1, x, x+1\}$$ How do we get that set? I think it's supposed to be a set containing all ...
1
vote
3answers
245 views

How many distinct degree 7 polynomials are there over the modular arithmeic modulo 7?

If it's infinite, is it countable or uncountable infinite? I am a newbie to this topic... I don't know what modular arithmetic for polynomials means. Can someone please give me a link where I can ...
0
votes
1answer
101 views

$\mathbb{Z}/n\mathbb{Z}[T]$ and zero divisors

I read the following in wiki, but I can't understand what is meant by "divisor" there. Notice that $(\mathbb{Z}/2\mathbb{Z})[T]/(T^{2}+1)$ is not a field since it admits a zero divisor ...
1
vote
3answers
101 views

How to show that $h(x^p) \equiv h(x)^p \pmod{p}$? [duplicate]

Possible Duplicate: Why $g(x^{p})=(g(x))^{p}$ in the reduction mod $p$? Let $h(x) \in \mathbb{Z}[x]$ and $p$ be a prime. We know that for any integer $\alpha$ we have that $\alpha^p \equiv ...
1
vote
1answer
582 views

Solving a polynomial modulo an integer

Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot ...
2
votes
4answers
85 views

Turn fractions into $\mathbb Z_7$ elements

I had to perform a division between two polinomials $2x^2+3x+4$ and $3x+4$, my book suggests to do this operation without worrying about the modulo. So my result is ...
1
vote
2answers
482 views

Question about CRT

The question rephrased and compressed: Let $F=F_2[a]$ be a finite extension field of the field of two elements $F_2$. We are given a polynomial $R(X)\in F[X]$, and pairwise coprime irreducible ...
5
votes
2answers
700 views

How are polynomials mod m reduced?

How do you reduce polynomials that are mod m? For example if I have 10x + 5 (mod 3) can I just reduce that to x + 2 (mod 3)?
0
votes
1answer
67 views

Asociated polynomials

Hi I have another problem..Two polynomials a(x) and b(x) are asociated iff a(x)|b(x) and b(x)|a(x)….Right? And now my problem..And polynomials are indivisible when gcd is asociated with 1..And there ...
0
votes
1answer
125 views

Dividing in $\mathbb{Z}_m[x]/p(x)$

how can I divide for example $\frac{x^2+1}{2x+1}$ in $\frac{\mathbb{Z}_3[x]}{x^3+1}$? It's like normal polynomial dividing but here I got in first step $\frac{x}{2} (\frac{x^2}{2x}=\frac{x}{2}$).What ...