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

learn more… | top users | synonyms

24
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 ...
3
votes
4answers
462 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 — ...
5
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?
0
votes
3answers
1k 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)$ ...
2
votes
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$ ?
78
votes
11answers
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
3answers
1k 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 ...
4
votes
0answers
309 views

Integer Factorization: Possible progress [closed]

I build an algorithm for solving Integer Factorization problem when the number to factor is selected by multiplication of two prime numbers with the same bit count. So far I only been able to factor ...
1
vote
3answers
211 views

Multiplication partitioning into k distinct elements

Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are ...
29
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 ...
8
votes
7answers
625 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
1k 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 $$ ...
2
votes
2answers
64 views

Quadratic Polynomial factorization

This could be primary school stuff. But I want to ask it. In factoring $x^2+bx+c$ (i.e. $a = 1$ in $ax^2+bx+c$), we find $m$ and $n$ such that $m+n = b$ and $mn=c$. We can reason this well as ...
3
votes
6answers
621 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
661 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
624 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 ...
1
vote
2answers
63 views

If I remove the premise $a\neq b$ in this question, will the statement still be true?

I encountered this proving problem, I can do the proof but my question is why in the condition/premise we need $a$ to be unequal to $b$? My guess is that even $a=b$, the statement is still true, is it ...
0
votes
1answer
272 views

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

Consider the following 2D infinitely large grid where the dots represent infinity: ...
14
votes
5answers
4k 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 ...
9
votes
4answers
830 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 ...
2
votes
6answers
165 views

Given $x^2 + 4x + 6$ as factor of $x^4 + ax^2 + b$, then $a + b$ is [closed]

I got this task two days ago, quite difficult for me, since I have not done applications of Vieta's formulas and Bezout's Theorem for a while. If can someone solve this and add exactly how I am ...
15
votes
5answers
4k 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 ...
10
votes
1answer
436 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 ...
8
votes
1answer
771 views

Smallest number with a given number of factors

From my rather rudimentary explorations of this fascinating problem, I believe it to be a layered and rewarding subject for investigation. My question, essentially, is: How do you find the smallest ...
7
votes
1answer
414 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
14k 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
149 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
356 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 ...
2
votes
1answer
180 views

By viewing the polynomials as a difference of two squares, factorise the following polynomials.

By viewing the polynomials as a difference of two squares, factorise the following polynomial: $$x^4+x^2+1.$$ I searched but couldn't find a way to solve this Edit: By using Hans Lundmark hint, I ...
2
votes
1answer
472 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
105 views

How to factor polynomials in $\mathbb{Z}_n$?

How to factor a certain polynomial over $Zn$. for example factor the following polynomial into irreducible polynomials in $Z5$: $X^3+X^2+X-1$ or factor the following polynomial into irreducible ...
0
votes
2answers
79 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 ...
-4
votes
2answers
82 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 ...
44
votes
16answers
69k 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 ...
12
votes
3answers
701 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$ ...
6
votes
3answers
22k 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 ...
8
votes
4answers
425 views

Factor $x^4+1$ over $\mathbb{R}$

Factor $x^4+1$ over $\mathbb{R}$ Well, I read this question first wrongly, because the reader is about complex analysis, I did it for $\mathbb{C}$ first. I got. $x^4+1=(x-e^{\pi i/4 })(x-e^{3 ...
17
votes
1answer
610 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.
5
votes
1answer
1k 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 ...
3
votes
1answer
1k 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
2answers
148 views

Integer factorization: What is the meaning of $d^2 - kc = e^2$

I found an interesting behavior when placing the integer factorization problem in to geometry, I call it pyramid factoring. Lets assume we have $c$ boxes and we want to order them in to rectangle. ...
2
votes
3answers
418 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 ...
7
votes
1answer
237 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 ...
6
votes
5answers
346 views

Proving an expression is composite

I am trying to prove that $ n^4 + 4^n $ is composite if $n$ is an integer greater than 1. This is trivial for even $n$ since the expression will be even if $n$ is even. This problem is given in a ...
5
votes
4answers
293 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
392 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 ...
4
votes
4answers
650 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
445 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 ...