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

learn more… | top users | synonyms

1
vote
1answer
64 views

probability of a number not having factors below n?

I want to know the probability that a number is not divisible by any prime smaller than or equal to n. ie, I find a big number, I trial division it up to 300000 and don't find any factors. I want to ...
2
votes
5answers
3k views

Factoring Polynomials with four terms and two variables

I've been working on this for hours and cannot figure it out. When I search, I find factorization techniques that I already know but don't seem to be able to apply here, or that are for polynomials ...
1
vote
2answers
174 views

How to break apart this sum?

I have a summation I need to break apart but I can't figure it out http://www.collectionscanada.gc.ca/obj/s4/f2/dsk1/tape10/PQDD_0027/MQ50799.pdf $p.15$, right after line $(3.8)$ Going from the ...
5
votes
3answers
97 views

Given $N$, find $ab = N$ with $a$ and $b$ as close as possible

Given a number $N$ I would like to factor it as $N=ab$ where $a$ and $b$ are as close as possible; say when $|b-a|$ is minimal. For certain $N$ this is trivial: when $N$ is prime, a product of two ...
2
votes
2answers
83 views

Multiplying over Subtraction

I'd like to take maths seriously but I'm not that great at it, so I decided to learn at home. I know this is pretty basic, but as I said, I'm pretty bad at maths, haha. The worksheet gives me this ...
1
vote
0answers
110 views

What is the condition for a polynomial to be factorizable in linear real factors?

I have a polynomial $p_a(x,y)= x^2F(a)+y^2G(a)-xH(a)-I(a)$ where $F(a)$, $G(a)$, $H(a)$ and $I(a)$ some real fuctions of $a$ are. Which conditions must satisfy $a$ so that I can factorize the ...
0
votes
2answers
71 views

Transform a positive integer to find its next greatest factor

Suppose I am trying to find factors of a particular positive integer num. Suppose I also have a function findGreatestFactor(num) ...
1
vote
1answer
164 views

Factoring a polynomial with big integer coefficients and some known factors.

I have the following polynomial that I want to factor $$ \begin{align*} p(x)= &- 236364091 x^{13}- 28363690920 x^{12}- 1487737229594 x^{11}\\ &- 44880832661940 x^{10} - 860924276925225 x^9- ...
18
votes
4answers
756 views

Find all roots of $\,(x + 1)(x + 2)(x + 3)^2(x + 4)(x + 5) = 360$

The question is to find all complex roots of $$(x + 1)(x + 2)(x + 3)^2(x + 4)(x + 5) = 360$$ and it is meant to be solved by hand. Is there any quick way to solve this using some trick that I'm not ...
16
votes
1answer
392 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}$? ...
0
votes
1answer
220 views

Zeroes in a 3x3 Matrix Determinant

My professor found the cubic roots of a 3x3 matrix by doing the following. I don't understand how step 2 came about and why he applied the same for step 4 on row 1 instead of row 2. Step 1: ...
4
votes
1answer
144 views

How to implement birthday paradox continuation of elliptic curve factorization algorithm

I have already implemented Lenstra's algorithm for factoring integers using elliptic curves; it is shown below, or you can run it at http://ideone.com/QEDmMY. Beware that my code is optimized for ...
1
vote
1answer
48 views

factorization of numbers with euclidian approach

Anyone know about this topic?. Factorization of numbers with euclidian approach I searching in the internet, but i couldnt find any source of this topic?. Some one can help me about this topic?. I ...
11
votes
7answers
510 views

Can someone show me why this factorization is true?

$$x^n - y^n = (x - y)(x^{n-1} + x^{n-2}y + \dots + xy^{n-2} + y^{n-1})$$ Can someone perhaps even use long division to show me how this factorization works? I honestly don't see anyway to "memorize ...
0
votes
3answers
75 views

How to factorize a cubic equation?

How should I factor this polynomial: $x^3 - x^2 - 4x - 6$
1
vote
1answer
55 views

Polynomial factoring issue

I am dealing with an issue for which I do not find answer on the Internet. When I factorize a polynomial, I can get this structure: $$ (x-a)(x-b)(x-c)^2 $$ But sometimes I have seen others like: $$ ...
1
vote
1answer
230 views

Complexity of Pollard's p-1 method

I'm working on the complexity of various integer factorization algorithms and am kind of stuck on the complexity of Pollard's p-1 method. (I'm using Prime Numbers - A Computational Perspective by ...
2
votes
0answers
48 views

Different elliptic curves over given $\mathbb{F}_q$ can have different orders?

As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders? I assume yes. Let $q:=5$. Wikipedia gives $9$ points for ...
0
votes
0answers
66 views

Factoring from order finding?

It appears that if you have a finite field, F_p, and you can factor the order of the field, p-1, then you can easily construct an arbitrary nth root of unity in F_p and also check that it be primitive ...
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.
3
votes
0answers
103 views

Why does Lenstra ECM work?

I came across Lenstra ECM algorithm and I wonder why it works. Please refer for simplicity to Wikipedia section Why does the algorithm work I NOT a math expert but I understood first part well enough ...
3
votes
1answer
140 views

Classifying all ideals of a lattice $\mathbb{Z}[\sqrt{-d}]$

In Artin's Algebra he presents a method (that I am sure I am butchering) for classifying ideals of a given lattice $\mathbb{Z}[\sqrt{-d}]$ by taking any ideal $I$, choosing an element of minimum norm ...
5
votes
0answers
156 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
1
vote
1answer
247 views

Simplifying third degree polynomials

I am trying to figure out this simple problem but I have no idea how to do it. $\frac {2x^3 - 5x^2 -4x -3}{2x^3 + x^2 - 18x -9}$ I know that I can keep guessing at random to find a factor in the ...
0
votes
1answer
631 views

What is the term for the product of two prime numbers?

Numbers that can be factored down into 2 and only 2 prime numbers, such as: 25 (5 * 5) 9 (3 * 3) 12752041 (3571 * 3571) Is there a mathematical term for these ...
1
vote
2answers
1k views

Factoring polynomials of degree 6 in 2 ways.

Let $P(x)$ be an integer polynomial of degree $6$ that is irreducible over the integers. $P(x) = x^6 + (A+a) x^5 + (B+ aA+ b) x^4 + (C+aB+bA +c) x^3 + (aC +bB +cA) x^2 + (bC+cB) x + cC = x^6 + ...
2
votes
1answer
168 views

Factoring polynomials of degree 6 over extension fields.

Let $f(x)$ be a polynomial with integer coefficients that is irreducible over the integers and has degree 6. Let $L$ be the splitting field of $F$. Then we can ask, whether there exist intermediate ...
3
votes
2answers
446 views

Factoring in Z3[x]

I need to factor $x^6+x^4+x^2+1$ into irreducible parts in $Z_3[x]$. Obviously this polynomial reduces to $(x^4+1)(x^2+1)$ which is irreducible in $Z[x]$, but I'm not sure how to confirm that it's ...
3
votes
1answer
58 views

Factorising a quadratic equation

I've just started studying for an A-Level in Mathematics. This is probably a simple question but when I factorized the quadratic equation $15x^2+42x-9$ I took out the common factor $3$ to get ...
2
votes
5answers
121 views

Factorise $f(x)=x^5-x$ into a product of irreducibles in $\mathbb Z_{5}[x]$

So plugging in $1$ gives $f(1) = 0$ which means $1$ is a root and $f$ has a factor $(x-1)$ which is $\equiv (x+4)$ in $\mathbb Z_{5}[x]$ ? I then divide $f(x)$ by $(x+4)$ using polynomial long ...
4
votes
1answer
164 views

Dr. Math on factoring - mistake?

I am reading this article http://mathforum.org/library/drmath/view/75056.html and would like to ask if this section is correct: If it can, then you would have $f(x,y) = g(x,y) * h(x,y)$, ...
0
votes
4answers
85 views

Factor $x^3-x^2+2$ in $\mathbb Z_{3}[x]$

Factor $x^3-x^2+2$ in $\mathbb Z_{3}[x]$ and explain why the factors are irreducible. So the factor is supposed to be: $x^3-x^2+2 = 2(x + 1)(2x^2 + 2x + 1)= (x + 1)(x^2 + x + 2)$. But I don't ...
5
votes
0answers
156 views

Carmichael number factoring

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
0
votes
1answer
92 views

About Rings where the elements can be factored like $a^2 b$ … in multiple ways.

Im looking for non-UFD rings such that factoring of any element of that ring into irreducibles leads to either all factorizations squarefree or all factorizations squareful. Thus let $n$ be an ...
2
votes
2answers
178 views

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$. I know the answer is $1$. For some reason every way I compute this legendre symbol I get $-1$: ...
4
votes
2answers
183 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 = ...
2
votes
2answers
238 views

Which is the most correct factor tree?

I have been working through some factoring problems that include factor trees. Problem - using a factor tree, express 54 as a product of prime factors. My answer: 54 2*27 2*3*9 2*3*3*3 Textbook ...
4
votes
2answers
350 views

Solve logarithmic equation

I'm getting stuck trying to solve this logarithmic equation: $$ \log( \sqrt{4-x} ) - \log( \sqrt{x+3} ) = \log(x) $$ I understand that the first and second terms can be combined & the logarithms ...
1
vote
0answers
77 views

Understanding of Pollard rho factorization

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms. Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
4
votes
1answer
704 views

Factorization of $(x^7-1)$ into irreducible factors over $GF(4)$

I need to find cyclotomic cosets depending on $n=7$ and $q=4$ and find the factorization of $(x^7-1)$ into irreducible factors over $GF(4)$. Thanks for any advice.
0
votes
3answers
154 views

Pattern in Fermat Factorization

I have the Fermat Factorizations of $n = pq$ where $p$ and $q$ are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of $n, p, q$. ...
0
votes
3answers
149 views

Reducible polynomial + integer = Reducible polynomial?

Reducible polynomial + integer = Reducible polynomial ? As the title says. More specific : For every integer $n$, does there exist a pair of polynomials $p(x)$ and $q(x)$ such that: ...
1
vote
3answers
74 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
64 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
72 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
398 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
162 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
157 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
2k 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
121 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)$ ...