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

learn more… | top users | synonyms

28
votes
2answers
3k 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 ...
-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)$ ...
4
votes
4answers
522 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?
86
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 ...
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$ ?
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
3answers
401 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 ...
8
votes
7answers
646 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 $$ ...
31
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 ...
2
votes
2answers
69 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
1k 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$ ...
3
votes
6answers
709 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
836 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
644 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
981 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
406 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
77 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
1answer
297 views

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

Consider the following 2D infinitely large grid where the dots represent infinity: ...
18
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 + ...
45
votes
16answers
93k 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
959 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
7k 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 ...
2
votes
6answers
178 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 ...
1
vote
2answers
504 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
552 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 ...
7
votes
1answer
454 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 ...
7
votes
4answers
19k 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: ...
3
votes
2answers
64 views

Finding integers satisfying $m^2 - n^2 = 1111$

We have to find the integers $m$ and $n$ which will satisfy the given condition: $$m^2-n^2=1111.$$ What could be the answer and how? i tried using trial and error and that took a long time.
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?
2
votes
1answer
66 views

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

I would like to if the polynomials of the form $x^{2^{n}}+1$ are irreducible over $\mathbb{Q}$ and in that case if there is some "easy" proof for that (where easy means not using a big theory like ...
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
506 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 ...
1
vote
0answers
18 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 ...
0
votes
2answers
121 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
134 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
86 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
137 views

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

Is $3^{2015} - 2^{2015}$ a prime. If not, why?
9
votes
3answers
31k 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 ...
23
votes
2answers
339 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, ...
7
votes
2answers
126 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 ...
13
votes
10answers
4k views

Taking Calculus in a few days and I still don't know how to factorize quadratics

Taking Calculus in a few days and I still don't know how to factorize quadratics with a coefficient in front of the 'x' term. I just don't understand any explanation. My teacher gave up and said just ...
10
votes
4answers
1k 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
2answers
265 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
76 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: ...
7
votes
1answer
2k 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 ...