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

learn more… | top users | synonyms

1
vote
3answers
79 views

Correctness of Fermat Factorization Proof

I have asked similar questions regarding this proof. But now I would like to know if my reformulation (after perseverance and different thinking) is correct. Prove: An odd integer $n \in \mathbb{N}$ ...
0
votes
1answer
65 views

Correctness of Fermat's Factorization

Is this proof correct: An odd integer $n \in \mathbb{N}$ is composite iff it can be written in the form $n = x^2 - y^2, y+1 < x$ Proof: $\leftarrow$ Want: $n = ab$ Where $a$ and $b$ are odd ...
2
votes
1answer
80 views

Factorization, Prime Numbers, and Limits to Our Grasp of Each

I have been fascinated with prime numbers ever since I was very young and actually setup a "Sieve of Eratosthenes" long before I ever knew that something like that existed. As I have gotten older and ...
1
vote
1answer
535 views

Product of 3 integers is 72, find the 3 integers that give the smallest sum

Product of 3 integers a, b, c equals 72, where every factor is positive integer. Find the integers a, b, c with the smallest sum. It's easy to get the factors of 72 manually and see that the 3 ...
2
votes
2answers
181 views

Complexity of finding the largest prime factor of a composite number

Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?
0
votes
0answers
165 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 ...
1
vote
2answers
3k views

Graphing Cubic Functions

I'm having a Little bit of trouble in Cubic Functions, especially when i need to graph the Turning Point, Y-intercepts, X-intercepts etc. My class teacher had told us to use Gradient Method: lets ...
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)$ ...
3
votes
3answers
1k views

Does knowing the totient of a number help factoring it?

Edit: The quoted question addresses only numbers of the form $p^a q^b$, I asked a general question for arbitrary $n$. If $n$ is a prime or a product of 2 primes then knowing its totient ...
0
votes
2answers
201 views

Finding total number of divisors which divide 2 given numbers [duplicate]

Possible Duplicate: Number of common divisors between two given numbers I need to find the total number of divisors which divide both the numbers lets say N and M. Actually I tried to think ...
0
votes
1answer
74 views

Distinct-degree factorization in finite fields

In $\mathbb{Z}_3$ $$ x^9 : x^4+x^3+x^2+2x+1 = x^5+2x^4+2x^2+2x$$ with remainder of $x$. In $\mathbb{Z}_7$ $$x^7 : x^4+5x^3+x+5 = x^3+2x^2+4x$$ with remainder of $x$. Is this random? Or is there ...
2
votes
0answers
169 views

How many co-primes are there for a big integer N over a specified interval?

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
6
votes
3answers
11k 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: ...
5
votes
2answers
375 views

Find all ways to factor a number

An example of what I'm looking for will probably explain the question best. 24 can be written as: 12 · 2 6 · 2 · 2 3 · 2 · 2 · 2 8 · 3 4 · 2 · 3 6 · 4 I'm familiar with finding all the prime ...
8
votes
1answer
3k views

Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
3
votes
1answer
342 views

Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
1
vote
2answers
85 views

Does this sequence have this interesting property relating to the prime factorization of the index?

Define a sequence as $a_0 = 0$ and $a_n$ equals the number of divisors of $n$ (including 1 and $n$) that are greater than $a_{n-1}$. This is sequence A152188 in OEIS, by the way. (For example, the ...
6
votes
3answers
401 views

Finding the number of factors of product of numbers

If $a,b,c,d\in\mathbb{N}$ be distinct. Each of which has exactly five factors, can we determine the number of factors of the product of $a,b,c,d$? Edit This is the solution given the in the back of ...
1
vote
2answers
1k views

A Tri-Factorable Positive integer

Found this problem in my SAT book the other day and wanted to see if anyone could help me out. A positive integer is said to be "tri-factorable" if it is the product of three consecutive integers. ...
0
votes
1answer
259 views

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

Consider the following 2D infinitely large grid where the dots represent infinity: ...
0
votes
2answers
320 views

Factoring for extremely large numbers that are a power of 2.

This is a variation of this question. I want to find the number of factors for a given large integer that I already know to be a power of 2. Given that the number is a power of 2, does that help by ...
2
votes
2answers
321 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
359 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 ...
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 + ...
4
votes
1answer
125 views

If $A,B$ are factors of $2^6 3^4 5^2,$ how many values of $|A-B|$ are possible?

Let $x=2^6 3^4 5^2$, then how many distinct values of $|A-B|$ are possible where $A, B$ are the factors of $x$? How to approach this problem?
7
votes
1answer
1k views

Even numbers have more factors than odd numbers…

This was an exercise to show that, in a sense, the even numbers have more prime factors than the odds, but--if it's right-- I still have a question. As an heuristic calculation, we could take a large ...
6
votes
4answers
1k views

Find all real solutions to $8x^3+27=0$

Find all real solutions to $8x^3+27=0$ $(a-b)^3=a^3-b^3=(a-b)(a^2+ab+b^2)$ $$(2x)^3-(-3)^3$$ $$(2x-(-3))\cdot ((2x)^2+(2x(-3))+(-3)^2)$$ $$(2x+3)(4x^2-6x+9)$$ Now, to find solutions you must set ...
5
votes
1answer
316 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 ...
2
votes
5answers
437 views

Factor $4x^3-8x^2-25x+50$ completely

Factor $4x^3-8x^2-25x+50$ completely The highest numbers you can take would be $1$, $2$, or $4$. Neither of those apply to all. So let's try the $x$! But the last term $50$ doesn't have an $x$ ...
1
vote
1answer
106 views

Factorize $f$ as product of irreducible factors in $\mathbb Z_5$

Let $f = 3x^3+2x^2+2x+3$, factorize $f$ as product of irreducible factors in $\mathbb Z_5$. First thing I've used the polynomial reminder theorem so to make the first factorization: ...
0
votes
2answers
73 views

Find monic grade 3 polynomial in $\mathbb Z_p[x]$ then factorize

Let $f = 15x^4+22x^3-x=0$ a polynomial in $\mathbb Z_p[x]$, find the first prime $p$ value that will make $f$ result in being grade 3 and monic. Then factorize $f$ in $\mathbb Z_3[x]$ as product of ...
1
vote
1answer
102 views

How to simplify [3a(b-c)+5][-3a(b-c)-5] by using special product?

In simplifying $$[3a(b-c)+5][-3a(b-c)-5],$$ I used $$4(au+bv)(cu+dv)=acu^2+(ad+bc)uv+bdv^2.$$ I failed to apply the formula to the equation because $a=3a$, $b=-3a$, $c=5$, $d=-5$, $u=(b-c)$, $v=?$ ...
0
votes
2answers
83 views

Find a prime number $p$ so that $f = \overline{3}x^3+ \overline{2}x^2 - \overline{5}x + \overline{1}$ is divided by $x-\overline{2}$ in $\mathbb Z_p$

Let $f = \overline{3}x^3+ \overline{2}x^2 - \overline{5}x + \overline{1}$ be defined in $\mathbb Z_p$. Find a prime number $p$ so that $f$ can be divided by $g = x-\overline{2}$, then factorize $f$ as ...
7
votes
3answers
114 views

How to see that the shift $x \mapsto (x-c)$ is an automorphism of $R[x]$?

In the process of studying irreducibility of polynomials, I encountered the criterion that $p(x)$ is irreducible if and only if $p(x-c)$ is irreducible. When trying to determine what properties of the ...
5
votes
1answer
935 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 ...
0
votes
3answers
225 views

Determine monic and degree 3 polynomial in $\mathbb Z_p$

I stumbled upon this kind of problem and I really can't get the hang of it. Will anyone please outline the way to solve it? Determine for which of the first $p > 0$ values the polynomial $f = ...
1
vote
1answer
165 views

How to factor $x^5 - x + 1$

As I understand it $x^5 - x + 1$ is not solvable by radicals. But it splits over $\mathbb{C}$, so how does it factor into linear factors?
0
votes
0answers
195 views

Approximations for the number of divisors of an integer

Given an integer $n$, I want to know the asymptotic order of: a. the number of distinct prime factors b. the number of non-distinct prime factors c. the number of distinct divisors d. the number ...
2
votes
2answers
147 views

Polynomial-related manipulation

My question is: Factorize: $$x^{11} + x^{10} + x^9 + \cdots + x + 1$$ Any help to solve this question would be greatly appreciated.
1
vote
0answers
138 views

A special factorization

Suppose that monic polynomial $f(x)\in\Bbb Z[x]$ such that for all $m\in\Bbb Z$, $m>1$, there's no integers $\langle r,r_1,\ldots,r_m\rangle$ such that $f(r)=f(r_1)\cdots f(r_m)$. Is there any ...
2
votes
3answers
381 views

Factoring by grouping: $x^4 - y^4 -4x^2 + 4$

Please help me factor $x^4 - y^4 -4x^2 + 4$ by grouping terms. Thank you.
1
vote
2answers
153 views

Factoring $x^4z-2z^2-4x^6+x^2z$

We want to factor $8x^4y^4-2y^8-4x^6+x^2y^4 = -2y^8 + (8x^4+x^2)y^4 -4x^6$. We substitute $x^4$ with $z$: Now we want to compute this $8x^4z-2z^2-4x^6+x^2z = -(x^2-2z)(4x^4-z)$ by hand. Therefore we ...
1
vote
2answers
734 views

Factoring multivariate polynomial

I'm trying to factor $$x^3+x^2y-x^2+2xy+y^2-2x-2y \in \mathbb{Q}[x,y].$$ The hint for the exercise is to use the recursive multivariate polynomial form. So I'm using $\mathbb{Q}[x][y]$: $$ x^3 + ...
2
votes
6answers
981 views

How do I factor trinomials of the format $ax^2 + bxy + cy^2$?

Take, for example, the polynomial $15x^2 + 5xy - 12y^2$.
3
votes
1answer
195 views

Dixon's random squares algorithm: a step in the proof of its subexp. running time

I am currently working to understand Dixon's running time proof of his subexp integer factorization algorithm (random squares). But unfortunately I can not follow him at a certain point in his work. ...
2
votes
4answers
73 views

Probably simple factoring problem

I came across this in a friend's 12th grade math homework and couldn't solve it. I want to factor the following trinomial: $$3x^2 -8x + 1.$$ How to solve this is far from immediately clear to me, ...
0
votes
2answers
102 views

Help with $1 + a + a(a-1) + a(a-1) (a-2) +\cdots+a(a-1)\cdots(a-(n-1))$

I want to rewrite the series $$1 + a + a(a-1) + a(a-1) (a-2) +\cdots+a(a-1)\cdots(a-(n-1))$$ as $(a^n-1)Y$ or $(a^{n-1}-1)Y$ Short-form: $$\{1+\sum_{i=1}^{n} \prod_{j=0}^{i-1}(a-j)\}$$ as $(a^n-1)Y$ ...
3
votes
2answers
218 views

Find $X$, $a$ : ALL prime factors of $(X^a - 1)/(X - 1) < X$

where $X$ is an odd prime, and $a$ is an odd integer. For example, let $X = 37$, $a = 3$, we get $$\frac{37^3-1}{36} = 3 \times 7 \times 67.$$ When factoring numbers such as this, I've noticed that ...
3
votes
3answers
206 views

Factorization of polynomials over $\mathbb{C}$

I'm stuck I don't know how to write this complex number equation as two factors although I know one of those factors is $z - 3$. Any ideas/advice appreciated. $$ f(z) = z^3 + (-6+2j)z^2 + ...
1
vote
4answers
1k views

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

How do I factor this polynomial: $2x^2-5xy-y^2$ ?