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

learn more… | top users | synonyms

1
vote
1answer
79 views

Factorizing Composites

Say $N=AB$ where $A$ and $B$ are primes. We write: $$A=a+x,\qquad B=a-x.$$ That is, $$a=\frac{A+B}{2};\qquad x=\frac{A-B}{2};$$ $A$ and $B$ are odd numbers. Therefore $A+B$ and $A-B$ are even. And ...
27
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 ...
5
votes
2answers
659 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 ...
42
votes
16answers
41k 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 ...
16
votes
4answers
546 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 ...
2
votes
3answers
191 views

How to factor $2x^2 - 8y^2$

How to factor $2x^2 - 8y^2$ ? So far I got it down to $$2(x^2 - 4y^2),$$ but it's not the answer; I don't think it's factored enough.
2
votes
1answer
140 views

Is $ x^2+ax+a$ irreducible over ring $\mathbb{Z}$ of integers?

How to prove that polynomials of the form : $P(x)= x^2+ax+a$ , where $a \in \mathbb{Z^{+}}$ \ $ \left \{ 4 \right \} $ are irreducible over ring $\mathbb{Z}$ of integers ? Eisenstein's ...
5
votes
2answers
225 views

Is an algebraic formula for the number of cyclic compositions of n known?

From Wikipedia: In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) ...
1
vote
3answers
146 views

Adjunction of a root to a UFD

Let $R$ be a unique factorization domain which is a finitely generated $\Bbbk$-algebra for an algebraically closed field $\Bbbk$. For $x\in R\setminus\{0\}$, let $y$ be an $n$-th root of $x$. My ...
2
votes
1answer
64 views

Factor the binomial $36 m^2 - \frac{25}{4} $

OK, I got a new one... it's $36 m^2 - \frac{25}4 $ and I got: $(18m-\frac{5}2 )(18m+\frac{5}2 )$ although that is incorrect... where did I go wrong?
2
votes
1answer
173 views

How does the rational root test work?

I've doing some research in wikipedia, where appears this example:$$3x^{3} - 5x^2 + 5x - 2 = 0$$the rational solution must be among the numbers symbolically indicated by: $$±\frac{1,2}{1,3}$$ So ...
0
votes
2answers
963 views

Factor By Grouping 3rd Degree Polynomial

Just to be upfront, this is a homework question, I already know the answer, but I can't figure out how to get there or the logic behind the hint, which is really what I'm after. Please don't solve it ...
1
vote
1answer
92 views

How do I factor this kind of equations?

I was doing some integration by partial fractions exercises and I found this equation:$$\int_{0}^{1}\frac{x^{3}+1}{x^{4}+4x+3},$$ and I don't know how to factor that in order to compute the partial ...
1
vote
0answers
262 views

Factoring multivariate polynomials

If I have a multivariate polynomial $P[X_1,\dots,X_n]\in \mathbb{R}[X_1,\dots, X_n]$, is there a polynomial time algorithm to factor the polynomial into irreducible polynomials $\in ...
0
votes
0answers
59 views

What is this special type of factor called?

I'm wondering if there's a special term for the following: The (special factor) of a number $x$ is a pair of numbers that multiply to give $x$ but has the smallest difference compared to other ...
1
vote
0answers
70 views

lower bounds for maximum computing times for integer factorisation

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
1
vote
1answer
209 views

Polynomial Factorization

I was handed $x^3-x^2+x-2=0$ to factor, but I'm not sure how. I tried all the methods I know of--which, at the time of writing, are limited by my precalc math background (I'm working on that...). Is ...
0
votes
0answers
56 views

Figuring $x$ where $x = \max \{ \operatorname{round}(7),0 \}$

I'm a software developer and do very little with math but I have been called upon to incorporate a math function into my app I'm developing. I'm stumped as to how to figure $x$ where $x = \max \{ ...
2
votes
2answers
547 views

Number of factors less than a number

I need to find the number of factors of a large number $n^2$ that are less than $n$. Supposing I can find the prime factorization, it is simple to find the total number of factors as a combinatorial ...
1
vote
1answer
126 views

Interpolation of a sequence of polynomials (viewed in terms of q-analogue powers)

I'm trying to find closed-form expressions for a sequence of coefficients, such that the index of the coefficient occurs as number such that I can later interpolate to fractional indexes as well. ...
4
votes
1answer
407 views

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors?

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? For example, suppose we have $n = p * q = 167653$; in this case, $p = 359 = 101100111_2$ and $q = 467 = ...
2
votes
1answer
95 views

Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$. ...
3
votes
4answers
944 views

Can $A^2+B^2+C^2-2AB-2AC-2BC$ be a perfect square

I have come upon the equation $A^2+B^2+C^2-2AB-2AC-2BC$ and want to factor it. Because of the symmetry, I am wondering if it can be a perfect square or if there is some other nice factorization.
6
votes
1answer
226 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 ...
8
votes
4answers
689 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
3answers
81 views

Solving for the interval of time during which the height of a thrown ball is at least “h” feet

In dealing with inequalities I've run into a certain peculiarity which I am currently unable to explain. The example: Find the interval of time during which the ball is at least 32 feet above ground. ...
2
votes
4answers
221 views

Find largest integer $x$ such that $3^x$ is a factor of $27^5$

Is the following solvable using just arithmetic rather than a calculator, and if so, how? Which of the following numbers is the greatest positive integer x such that $3^x$ is a factor of $27^5~$? ...
5
votes
2answers
335 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 $$ ...
2
votes
6answers
262 views

Factoring Quadratics

Is there a method to find which numbers to use when simplifying quadratics? For example $x^2 + 5x + 6$ is easy enough to find, but what if I have bigger numbers, or I have this quadratic expression: ...
1
vote
3answers
139 views

Trigonometric factoring

Very next question, no idea what to do... I am suppose to factor $2\sin^2x + 3\sin x+1$ . I figure this is pretty simple so I do $(2\sin x)(2\sin x)+3 \sin x+1$ . For some reason this is incorrect ...
3
votes
2answers
124 views

Factoring Quantities Question

I was doing an exercise and ran into a problem with their use of factoring. Here is the problem specific to where the issue occurs: $$ \frac{(x^2 + 1)^{1/2} - x^2 (x^2 + 1)^{-1/2}}{x^2 + 1} = ...
6
votes
2answers
489 views

Is the factorization problem harder than RSA factorization ($n = pq$)?

Let $n \in \mathbb{N}$ be a composite number, and $n = pq$ where $p,q$ are distinct primes. Let $F : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ (*) be an algorithm which takes as an input $x ...
2
votes
2answers
128 views

Calculations with liars and sums of prime factors

Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement. Obviously one can simply ...
1
vote
4answers
8k views

Factoring Methods/Tricks

One of the things I've struggled with most in algebra/calculus is all the "factoring tricks". When I take time away from doing math I inevitably forget most if not all of them. The old proverb "use it ...
2
votes
3answers
203 views

Edge of factoring technology?

Schneier in 1996's Applied Cryptography says: "Currently, a 129-decimal-digit modulus is at the edge of factoring technology" In the intervening 15 years has anything much changed?
3
votes
4answers
333 views

Factorize $x^3-3x+2$

How can I factorize $x^3-3x+2$ ? The answer that I got on the internet is $(x-1)^2(x+2)$. It would be nice if anyone could also tell what these type of equations are called and where can I learn ...
2
votes
3answers
983 views

About the factors of the product of prime numbers

If a number is a product of unique prime numbers, are the factors of this number the used unique prime numbers ONLY? Example: 6 = 2 x 3, 15 = 3 x 5. But I don't know for large numbers. I will be using ...
3
votes
1answer
73 views

Techniques for forming square factorizations

Say you have the polynomial $$ x^4 + 2 + x^{-4} $$ Looking at it, you see you can do $$\begin{align*} x^4 + 1 + 1 + x^{-4} & =x^2( x^2 + x^{-2} ) + x^{-2}( x^2 + x^{-2} )\\ &= \left( x^2 + ...
3
votes
2answers
551 views

What's the best way to factor a 256-bit number?

Suppose $N$ is an RSA modulus (ie, it's the product of two distinct primes), 256 bits long. What is the best method to factor it? Trial division is out of the question, Pollard's Rho is probably out ...
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 ...
0
votes
1answer
234 views

Factoring the polynomial $2x^2 - 2x + 2$

I saw in my book that $2x^2 - 2x + 2$ factored became $2(x^2 - x + 1)$. Why it does not became $2(x(x - 1) + 1)$? Is it wrong or correct as well?
0
votes
1answer
124 views

How did they simplify this function

I'm currently practicing differentiation. The exercise I currently have is the following Find the derivative of: $(x + 6)^3 (9 x^3 - 2)^5$ Okay, well I can do that now. When I do this I uses the ...
3
votes
1answer
236 views

Factoring a trivariate polynomial

I would appreciate some help with factoring a trivariate polynomial. The polynomial in question is $$p(x,y,z)=a_1 x^7+a_2 x^5y+a_3 x^3y^2+a_4 xy^3+a_5 x^4z+a_6 x^2yz+a_7 y^2z+a_8 xz^2,$$ where the ...
0
votes
2answers
561 views

Factoring Multiple Variable Polynomials

This is in relation to a problem dealing with the three-dimensional analogue of Pell's Equation. I would like to factor $ x^3+Dy^3+D^2z^3-3Dxyz $ into $\frac{1}{2}(x+Dy+D^2y)$ and another factor. I ...