For questions about finding factors of e.g. integers or polynomials

learn more… | top users | synonyms

3
votes
4answers
417 views

Factoring $ac$ to factor $ax^2+bx+c$

I was watching a first-year high-school-algebra student struggle with factoring quadratics last night. Given a quadratic $ax^2+bx+c$ (I'll give you the exact example in a moment), her method — ...
23
votes
2answers
2k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
4
votes
4answers
2k views

How can we prove that among positive integers any number can have only one prime factorization?

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
1
vote
4answers
2k views

How to factor the quadratic polynomial $2x^2-5xy-y^2$?

How do I factor this polynomial: $2x^2-5xy-y^2$ ?
0
votes
3answers
687 views

Proof of $a^n+b^n$ divisible by a+b when n is odd

I read somewhere that $(a^n - b^n)$ It is always divisible by a-b. When n is even it is also divisible by a+b. When n is odd it is not divisible by a+b. and $(a^n + b^n)$ ...
74
votes
10answers
4k views

Why does factoring eliminate a hole in the limit?

$$\lim _{x\rightarrow 5}\frac{x^2-25}{x-5} = \lim_{x\rightarrow 5} (x+5)$$ I understand that to evaluate a limit that has a zero ("hole") in the denominator we have to factor and cancel terms, and ...
8
votes
7answers
599 views

Solve $\sqrt{x+4}-\sqrt{x+1}=1$ for $x$

Can someone give me some hints on how to start solving $\sqrt{x+4}-\sqrt{x+1}=1$ for x? Like I tried to factor it expand it, or even multiplying both sides by its conjugate but nothing comes up ...
4
votes
2answers
876 views

Factorize polynomial over $GF(3)$

I want to factorize $x^{11}-1$ over $GF(3)$ but I'm stuck at $(x-1)(x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1).$ I have tried to do it trial and error but failed. Is $$ ...
3
votes
6answers
541 views

Solving $\sqrt{7x-4}-\sqrt{7x-5}=\sqrt{4x-1}-\sqrt{4x-2}$

Where do I start to solve a equation for x like the one below? $$\sqrt{7x-4}-\sqrt{7x-5}=\sqrt{4x-1}-\sqrt{4x-2}$$ After squaring it, it's too complicated; but there's nothing to factor or to ...
5
votes
2answers
462 views

Factoring Quadratics: Asterisk Method

I'm teaching my students about factoring quadratics. We've done GCF, difference of two squares, squared binomials, and grouping. One of my colleagues then found this asterisk method on line. It's ...
11
votes
8answers
606 views

How to factor quadratic $ax^2+bx+c$?

How do I shorten this? How do I have to think? $$ x^2 + x - 2$$ The answer is $$(x+2)(x-1)$$ I don't know how to get to the answer systematically. Could someone explain? Does anyone have a link to ...
5
votes
1answer
329 views

Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})[X]$

Is it possible to determine how many irreducible factors $X^p-1$ in the polynomial ring $(\mathbb{Z}/q \mathbb{Z})[X]$ has and maybe even the degrees of the irreducible factors? ($p,q$ are a primes ...
0
votes
1answer
260 views

Calculating powers of 2 on a 2D grid without factoring.

Consider the following 2D infinitely large grid where the dots represent infinity: ...
28
votes
4answers
1k views

Fermat's Last Theorem and Kummer's Objection

In 1847 Lamé had announced that he had proven Fermat's Last Theorem. This "proof" was based on the unique factorization in $\mathbb{Z}[e^{2\pi i/p}]$. However, Kummer, proved that when $p=23$ we do ...
12
votes
5answers
3k views

Is there a simple explanation why degree 5 polynomials (and up) are unsolvable?

We can solve (get some kind of answer) equations like: $$ ax^2 + bx + c=0$$ $$ax^3 + bx^2 + cx + d=0$$ $$ax^4 + bx^3 + cx^2 + dx + e=0$$ But why is there no formula for an equation like $$ax^5 + ...
26
votes
2answers
2k views

Factorize $(x+1)(x+2)(x+3)(x+6)- 3x^2$

I'm preparing for an exam and was solving a few sample questions when I got this question - Factorize : $$(x+1)(x+2)(x+3)(x+6)- 3x^2$$ I don't really know where to start, but I expanded everything to ...
8
votes
4answers
729 views

How to determine in polynomial time if a number is a product of two consecutive primes?

How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find ...
14
votes
5answers
2k views

Factoring a hard polynomial

This might seem like a basic question but I want a systematic way to factor the following polynomial: $$n^4+6n^3+11n^2+6n+1.$$ I know the answer but I am having a difficult time factoring this ...
7
votes
1answer
381 views

How prove that polynomial has only real root.

Let this polynomial $f(x)=\displaystyle\sum_{i=1}^{n}a_{i}x^i,\;\;a_{i}\in \mathbb{R} $ have only real roots. Prove: The polynomial $g(x)=\displaystyle\sum_{i}^{n}C_{n}^{i}a_{i}x^i$ has only real ...
6
votes
3answers
12k views

Find the largest prime factor

I just "solved" the third Project Euler problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? With this on Mathematica: ...
2
votes
3answers
144 views

irreducibility of polynomials with integer coefficients

Consider the polynomial $$p(x)=x^9+18x^8+132x^7+501x^6+1011x^5+933x^4+269x^3+906x^2+2529x+1733$$ Is there a way to prove irreducubility of $p(x)$ in $\mathbb{Q}[x]$ different from asking to PARI/GP?
1
vote
2answers
263 views

Rabin's test for polynomial irreducibility over $\mathbb{F}_2$

I know that $f(x) = x^{169}+x^2+1$ is a reducible polynomial over $\mathbb{F}_2$. I want to show this using Rabin's irreduciblity test. First, I then have to check if $f$ is a divisor of ...
5
votes
2answers
744 views

A theorem about prime divisors of generalized Fermat numbers?

A theorem of Édouard Lucas related to the Fermat numbers states that : Any prime divisor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k\cdot 2^{n+2}+1$ whenever $n$ is greater than one. Does anyone ...
2
votes
1answer
440 views

Factoring a number $p^a q^b$ knowing its totient

We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically ...
0
votes
2answers
59 views

How to factor cubics having no rational roots

$$-8x^3 +8x -3 = 0$$ I've already tried the possible roots of $\pm 1$ and $3$ using the rational roots test, but none of these help break it down into something more workable. How do I solve this ...
-3
votes
2answers
75 views

Prove that the subgroup of the quotient group is cycling and infinitely generated

$$M = \left\{\,\dfrac{m}{13^n}\biggm| m\in \mathbb{Z}, n\in\mathbb{N} \,\right\}, \quad G = M/\mathbb{Z}$$ Prove that any subgroup $H < G$, $H\neq G$ is cyclic and infinitely generated and that ...
42
votes
16answers
50k views

What is a real world application of polynomial factoring?

The wife and I are sitting here on a Saturday night doing some algebra homework. We are factoring polynomials and we both had the same thought at the same time: when are we going to use this? I feel ...
10
votes
3answers
470 views

Irreducibility of $x^n-x-1$ over $\mathbb Q$

I want to prove that $p(x):=x^n-x-1 \in \mathbb Q[x]$ for $n\ge 2$ is irreducible. My attempt. GCD of coefficients is $1$, $\mathbb Q$ is the field of fractions of $\mathbb Z$, and $\mathbb Z$ ...
4
votes
3answers
15k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
16
votes
1answer
422 views

Irreducibility of $x^{n}+x+1$

Motivated by this problem, and KCd's comment on my answer, I am left with the following question: Question: Suppose that $n\not \equiv 2\pmod{3}$. Is $$x^n+x+1$$ irreducible over $\mathbb{Q}$? ...
6
votes
5answers
1k views

Is $x^4+4$ an irreducible polynomial?

We know that $p(x)=x^4-4=(x^2-2)(x^2+2)$ is reducible over $\mathbb{Q}$ even not having roots there. What about $q(x)=x^4+4\in \mathbb{Q}[x]$? Again, no roots.
3
votes
1answer
793 views

Factorize a Symmetric matrix as an 'Approximation' with an outer product.

(deprecated-taken back based on discussion(OLD)) What is a good way to factor a symmetric matrix $X$ as an outer product of two vectors $u$ and $v$. i.e, Find two vectors $u$ and $v$ such that ...
2
votes
3answers
322 views

Way to show $x^n + y^n = z^n$ factorises as $(x + y)(x + \zeta y) \cdots (x + \zeta^{n-1}y) = z^n$

For odd $n$ the Fermat equation $x^n + y^n = z^n$ factorises as $$(x + y)(x + \zeta y) \cdots (x + \zeta^{n-1}y) = z^n,$$ where $\zeta = e^{2 \pi i/n}$. I tried seeing this was true by multiplying ...
6
votes
1answer
230 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
5
votes
4answers
262 views

Factorize: $a^2(b − c)^3 + b^2(c − a)^3 + c^2(a − b)^3$

I want to factorize $a^2(b − c)^3 + b^2(c − a)^3 + c^2(a − b)^3$ . By inspection , I can see that substituting $b$ for $a$ yields $0$ thus $(a-b)$ is a factor . Similarly $(c-a)$ and $(b-c)$ are ...
5
votes
6answers
301 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 ...
5
votes
1answer
324 views

Finding the radical of an integer

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$? I ask this because for polynomials it's ...
5
votes
1answer
976 views

Can any Polynomial be factored into the product of Linear expressions?

Specifically I am wondering if... Given a Polynomial of n degree in one variable with coefficients from the Reals. Will every Polynomial of this form be able to be factored into a product of n ...
4
votes
4answers
523 views

Factorise: $2a^4 + a^2b^2 + ab^3 + b^4$

Factorize : $$2a^4 + a^2b^2 + ab^3 + b^4$$ Here is what I did: $$a^4+b^4+2a^2b^2+a^4-a^2b^2+ab^3+b^4$$ $$(a^2+b^2)^2+a^2(a^2-b^2)+b^3(a+b)$$ $$(a^2+b^2)^2+a^2(a+b)(a-b)+b^3(a+b)$$ ...
4
votes
5answers
422 views

Let $r,s,t$ be the roots of the equation $ x^3 - 6x^2 + 5x + 1$. What is the value of $(2-r)(2-s)(2-t)$?

Let $r,s,t$ be the roots of the equation $ x^3 - 6x^2 + 5x + 1$. What is the value of $(2-r)(2-s)(2-t)$? The question is mentioned in my math olympiad. Please explain how to solve the problem. I have ...
2
votes
2answers
328 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
3answers
367 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
1
vote
3answers
117 views

Is there a branch of mathematics that studies the factors of rational numbers?

Is there a branch of mathematics that studies the factors of rational numbers? I am imagining that defining this would work pretty much the same way as defining the factors x of an integer n: $\{x ...
1
vote
3answers
93 views

Find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\dots+\frac{1}{d_k}$.

Let $d_1,d_2,\dots,d_k$ be all the factors of a positive integer $n$ including $1$ and $n$. Suppose $d_1+d_2+\dots+d_k=72$. Then the value of $$\frac{1}{d_1}+\frac{1}{d_2}+\dots+\frac{1}{d_k}$$ is ...
1
vote
1answer
123 views

Factoring polynomials of degree $a p^b$ over extension fields.

Let $f(x)$ be an irreducible polynomial with integer coefficients, which is irreducible over $\mathbb{Z}$ and has degree $a p^b > p$ with $p,a,b>0$ and $p$ a prime. It appears that $f(x)$ ...
0
votes
0answers
166 views

Factoring polynomials $f(g(x))$ over extension fields.

This question is a variation on another one : related question Let $f(x)$ and $g(x)$ be polynomials with integer coefficients and discriminant of $f(x)$ > discriminant of $g(x)$ , which are ...
16
votes
4answers
568 views

Are polynomials of the form : $ f_n= x^n+x^{n-1}+\cdots+x^{k+1}+ax^k+ax^{k-1}+\cdots+a$ irreducible over $\mathbb{Z} $?

Is it true that polynomials of the form : $ f_n= x^n+x^{n-1}+\cdots+x^{k+1}+ax^k+ax^{k-1}+\cdots+a$ where $\gcd(n+1,k+1)=1$ , $ a\in \mathbb{Z^{+}}$ , $a$ is odd number , $a>1$, and ...
7
votes
3answers
605 views

How do I completely solve the equation $z^4 - 2z^3 + 9z^2 - 14z + 14 = 0$ where there is a root with the real part of $1$.

I would please like some help with solving the following equation: $$z^4 - 2z^3 + 9z^2 - 14z + 14 = 0$$ All I know about the equation is that there is a root with the real part of $1$. My approach ...
5
votes
1answer
132 views

The uniqueness of a special maximal ideal factorization

The following problem is from Michael Artin's Algebra, chapter 12, M.6, unstarred: Let $R$ be a domain, and let $I$ be an ideal that is a product of distinct maximal ideals in two ways, say ...
5
votes
2answers
174 views

elegant way to show $P= t^{1024}+t+1$ is reducible in $\mathbf{F}_{2}[t]$

This is homework exercise: $$P=t^{1024} + t + 1 , R = \mathbf{F}_{2}[t] \Rightarrow P \ \text{reducible in R}$$ I wanted to show this analogous to how a book shows it (book shows it with other ...