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

learn more… | top users | synonyms

27
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
508 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?
-2
votes
5answers
2k views

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

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)$ ...
85
votes
11answers
5k 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 ...
9
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 ...
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$ ?
2
votes
3answers
358 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 ...
30
votes
4answers
2k 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
634 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 ...
5
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
68 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 ...
16
votes
2answers
902 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$ ...
5
votes
2answers
785 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 ...
3
votes
6answers
696 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 ...
11
votes
8answers
640 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 ...
8
votes
1answer
962 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 ...
6
votes
2answers
391 views

Factoring $X^{16}+X$ over $\mathbb{F}_2$

I just asked wolframalpha to factor $X^{16}+X$ over $\mathbb{F}_2$. The normal factorization is $$ X(X+1)(X^2-X+1)(X^4-X^3+X^2-X+1)(X^8+X^7-X^5-X^4-X^3+X+1) $$ and over $GF(2)$ it is $$ ...
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
288 views

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

Consider the following 2D infinitely large grid where the dots represent infinity: ...
17
votes
5answers
5k 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 + ...
43
votes
16answers
86k 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 ...
27
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
908 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 ...
16
votes
6answers
6k 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
445 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
18k 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
6answers
177 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 ...
2
votes
3answers
154 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
469 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 ...
11
votes
1answer
511 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 ...
1
vote
0answers
17 views

Complex filter factorizations - continued

Continuing from this rather silly trivial question factoring real valued filters into shorter complex ones, hoping this won't be as trivial. If we modify it a bit: $$z_0 = e^{2\pi i / 8}$$ and ...
1
vote
1answer
39 views

If $a/s$ is irreducible in $R_{S}$, then $a$ is irreducible in $R$

Let $R$ be a UFD, and let $S$ be a multiplicative subset of $R$ containing the unity of $R$. Show that if $a/s$ is irreducible in $R_{S}$, then $a$ is irreducible in $R$. (Bhattacharya, Basic ...
2
votes
1answer
186 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
499 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
1answer
65 views

Principal ideal domain with finitely many ideals

Let $aR$ be a nonzero ideal in a PID $R$. Show that $R/aR$ is a ring with only finitely many ideals. Honestly, I do not know how to start. Appreciate any tips.
0
votes
2answers
114 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
108 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
84 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 ...
-4
votes
2answers
131 views

Check if the number $3^{2015} - 2^{2015}$ is prime [closed]

Is $3^{2015} - 2^{2015}$ a prime. If not, why?
8
votes
3answers
28k 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 ...
7
votes
2answers
123 views

Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I ...
5
votes
2answers
252 views

Are Euclid numbers squarefree?

Are Euclid numbers squarefree ? An Euclid number is by definition a Primorial number + 1. See http://mathworld.wolfram.com/Primorial.html. In notation the $n$ th Euclid number is written as $E_n = ...
3
votes
2answers
73 views

Find the value of $\frac{S_{5}S_{2}}{S_{7}}$

If $a$, $b$, $c$ $\in \mathbb R$, we define $S_{k}=\frac{a^k+b^k+c^k}{k}$ (where $k$ is a non-negative integer). Given that $S_{1}=0$, find the value of $$\frac{S_{5}S_{2}}{S_{7}}$$ I tried: ...
8
votes
4answers
769 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 ...
6
votes
6answers
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.
22
votes
2answers
298 views

Solve $x^4+3x^3+6x+4=0$… easier way?

So I was playing around with solving polynomials last night and realized that I had no idea how to solve a polynomial with no rational roots, such as $$x^4+3x^3+6x+4=0$$ Using the rational roots test, ...
17
votes
1answer
652 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}$? ...
16
votes
0answers
271 views

Irreducibility of $~\frac{x^{6k+2}-x+1}{x^2-x+1}~$ over $\mathbb Q[x]$

The Artin—Schreier polynomial $~x^n-x+1~$ is always irreducible over $\mathbb Q[x]$, unless $n=6k+2$, in which case it seems to have only two factors, one of which is always $x^2-x+1$. The ...
5
votes
4answers
328 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 ...