What is Factorization: Definition and 160 Discussions
In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is a factorization of the integer 15, and (x – 2)(x + 2) is a factorization of the polynomial x2 – 4.
Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any
x
{\displaystyle x}
can be trivially written as
(
x
y
)
×
(
1
/
y
)
{\displaystyle (xy)\times (1/y)}
whenever
y
{\displaystyle y}
is not zero. However, a meaningful factorization for a rational number or a rational function can be obtained by writing it in lowest terms and separately factoring its numerator and denominator.
Factorization was first considered by ancient Greek mathematicians in the case of integers. They proved the fundamental theorem of arithmetic, which asserts that every positive integer may be factored into a product of prime numbers, which cannot be further factored into integers greater than 1. Moreover, this factorization is unique up to the order of the factors. Although integer factorization is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the RSA cryptosystem to implement public-key cryptography.
Polynomial factorization has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its roots to finding the roots of the factors. Polynomials with coefficients in the integers or in a field possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by irreducible polynomials. In particular, a univariate polynomial with complex coefficients admits a unique (up to ordering) factorization into linear polynomials: this is a version of the fundamental theorem of algebra. In this case, the factorization can be done with root-finding algorithms. The case of polynomials with integer coefficients is fundamental for computer algebra. There are efficient computer algorithms for computing (complete) factorizations within the ring of polynomials with rational number coefficients (see factorization of polynomials).
A commutative ring possessing the unique factorization property is called a unique factorization domain. There are number systems, such as certain rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of Dedekind domains: ideals factor uniquely into prime ideals.
Factorization may also refer to more general decompositions of a mathematical object into the product of smaller or simpler objects. For example, every function may be factored into the composition of a surjective function with an injective function. Matrices possess many kinds of matrix factorizations. For example, every matrix has a unique LUP factorization as a product of a lower triangular matrix L with all diagonal entries equal to one, an upper triangular matrix U, and a permutation matrix P; this is a matrix formulation of Gaussian elimination.
Homework Statement
A is a 4 x 5 matrix equal to
[1 4 -1 5 3
3 7 -2 9 6
-2 -3 6 -4 1
1 6 9 8 2]
and b =
[5
40
15
12]
(b is 4 x 1)
Find the LU factorization and use it to solve Ax = b
Homework Equations
The Attempt at a...
Homework Statement
Most invertible matrices can be written as a product A=LU of a lower triangular matrix L and an upper triangular matrix U, where in addition all diagonal entries of U are 1.
a. Prove uniqueness, that is, prove that there is at most one way to write A as a product.
b...
Homework Statement
A positive integer a is called a square if a=n^2 for some n in Z. Show that the integer a>1 is a square iff every exponent in its prime factorization is even.
Homework Equations
The Attempt at a Solution
Well, I know a=p1^a1p2^a2...pn^a^n is the definition of...
Homework Statement
Prove unique factorization for hte set of polynomials in x with integer coefficients
Homework Equations
The Euclidean algorithm may be of some use
The Attempt at a Solution
Let's say that the polynomial is of the form anx^n + a(n-1)x^(n-1) ... a1x + a0
There...
Homework Statement
I'm trying to factorize a characteristic equation from my ODEs class, and I am having a problem when it comes to 4th, 5th or higher order differential equations.
Say this one:
r5-3r4+3r3-3r2+2r=0
Homework Equations
The Attempt at a Solution
Tried a lot of...
In my literature reviews I found a few things that I can't quite understand.
Homework Statement
I have the following equation:
http://img717.yfrog.com/img717/6416/31771570.jpg
I'm told that by using the eigenvalue factorization:
http://img89.yfrog.com/img89/760/83769756.jpg
, I can...
Homework Statement
My book is awful and I need clarification on a few things regarding LU factorization:
-If I am trying to express matrix A as a product of its upper triangular matrix (U) and the lower triangular matrix (L). I understand that I should find U first by Gauss-Jordon...
Homework Statement
Assume that the matrix A is diagonalizable : A=PDP-1, where D is the diagonal matrix of eigenvalues. Show that this factorization is not always unique
Homework Equations
The Attempt at a Solution
I have a couple of theories. The first being that since the...
Hi,
This isn't exactly homework, but I guess it goes here because it's a specific problem?
I'm working on some Fortran 90 code to simulate a quantum wire. Part of the calculation involves finding the determinant of the Hamiltonian. I'm currently doing this by calculating the Hamiltonian's LU...
Homework Statement
You bring the drinks for your soccer team every sixth game. Every third game is a home game. How many times will you bring the drinks to a home game if you have a 20 game season?
Homework Equations
i did the problem in my head, but I need to show my work to get the...
Homework Statement
In one part of a musical composition, the triangle player in an orchestra plays once every 12 beats. The tympani player plays once every 42 beats. How often do they play together?
Homework Equations
don't have any
The Attempt at a Solution
Insufficient...
Homework Statement
Presidential elections are held every four years. Senators are elected every 6 years. If a senator was elected in the presidential election year of 2000, in what year would he or she campaign again during a presidential election year?
Homework Equations
dont know...
Homework Statement
Margo has piano lessons every two weeks. Her brother Roberto has a soccer tournament every three weeks. Her sister Randa has an orthodontist appointment every four weeks. If they all have activities this Friday, how long will it be before all of their activities fall on...
given the Laplacian for a certain metric 'g'
\Delta f = \partial _i \partial ^{i}f + (\partial ^{i}f) \partial _ i log |g|^{1/2}
where a sum over 'i' dummy variable is assumed
the idea is , could we factorize this Hamiltonian a second order differential operator into two first order...
Homework Statement
in order to factorize 20 on the rings of Q( \sqrt 2) i must solve
Homework Equations
x^{2} -2y^{2}=10
The Attempt at a Solution
i do not know how to solve it, i have tried by brute force with calculator but can not get any response , the given hint is that...
Problem:
Let Y1,Y2,...,Yn denote a random sample from the uniform distribution over the interval (0,theta). Show that Y(n)=max(Y1,Y2,...,Yn) is a sufficient statistic for theta by the factorization theorem.
Solution:
http://www.geocities.com/asdfasdf23135/stat10.JPG
1) While I...
Homework Statement
Find the gcd of 22,471 and 3,266 and express in the form 22,471x + 3,266y
Homework Equations
The Attempt at a Solution
I know how to get the gcd of easy numbers... using the prime factorization. But how do I do that with numbers of this scale?
Homework Statement
1. Homework Statement
If n is a nonzero integer, prove that n cam be written uniquely in the form n=(2^k)m, where It is in the primes and unique factorization chapter so maybe that every integer n (except 0 and 1) can be written as a product of primes
Homework...
Homework Statement
If n is a nonzero integer, prove that n cam be written uniquely in the form n=(2^k)m, where k is greater than or equal to zero, and m is odd
Homework Equations
It is in the primes and unique factorization chapter so maybe that every integer n (except 0 and 1) can be...
Homework Statement
One algorithm for finding the prime factorization of a number n is the following: Starting with d = 2, and continuing until n\geqd, try to divide n by d. If n/d, then record d as a (prime) factor and replace n by n/d; otherwise replace d by d + 1.
a) When d is recorded...
Trivial Question Involving Factorization (again) :)
Homework Statement
Factorize (E+M)(E+M) - as in E for energy and M for Mass
Homework Equations
... n/a
The Attempt at a Solution
E^2+2ME+M^2
Thanks...
Homework Statement
I have to write an algorithm in C++ to determine the (i)reductibility of a polynomial of degree "n"
Homework Equations
Berlekamp algorithm is preferred.
The Attempt at a Solution
I have Googled for almost an hour now and didn't find anything helpful.
I...
Homework Statement
Prove that \forall f:X\rightarrowY there \exists Z, h: X\rightarrowZ is injective and g: Z\rightarrowY is surjective, so that f=g*h.
Homework Equations
There is already a conclusion from the factorisation theorem of functions that: \forall f:X\rightarrowY there...
Alright I have to questions one is on how to measure the time it takes for my computer to solve a particular code I've tried the the "tic toc" and that seems to be dependent on the time frame that I typed in tic and toc. I need something that Is only dependent on the time taken to process and...
(I'm not sure what forum to put this on: number theory because of factoring, programming because I want to automate it, computers because I don't intend to actually program anything myself, or general because it combines these.)
I'm looking for a program that I can use to partially factor...
I am not sure I fully understand the extension of the Unique Factorization Theorem (UFT) to Gaussian Integers (GI), by saying that the representation of a GI as a product of primes is unique except for the order of factors and the presence of units.
Is there a similar problem when the UFT is...
I've been tasked with proving the existence of a full rank factorization for an arbitrary m x n matrix, namely:
Let \textit{A} \in \textbf{R}^{m x n} with \textit{rank(A) = r} then there exist matrices \textit{B} \in \textbf{R}^{m x r} and \textit{C} \in \textbf{R}^{r x n} such that \textit{A =...
It occurred to me that the rationals Q have also a unique prime factorization, as long as you allow negative exponents on the factorization.
If a/b is a rational, then both a and b have a unique (integer) prime factorization, and the fraction can be expressed uniquely as a product of primes...
I am posting an integer factorization algorithm that I have developed. I am hoping for feedback on any obvious flaws that I might have missed before writing a computer programme to test it out.
Thanks in advance
Visu
Factorize:
x^3 − 2x^2 − 4x + 8 correct answer:
(x^3 − 2x^2) − (4x − 8)
x^2(x − 2) − 4(x − 2)
(x^2 − 4)(x − 2)
(x − 2)(x + 2)(x − 2)
(x − 2) 2(x + 2)
In the third line where the terms are grouped i don't understand why one of the (x - 2) is omitted? i.e shouldn't it be (x -2)^2 ?
I'm doing some basic factoring now to refresh my skills.
On one problem, it is asking to factor: (y^2 + 8)^2 - 36 y^2
I was able to get to where I factor the trinomials: (y-4)(y-2)(y+4)(y+2)
When it says to give the summary of factorization, it gives: (y^2 + 8)^2 - (6y)^2
I'm going...
For what values does \mathbb{Z}[\zeta] have unique factorization?
I know Kummer shown that \zeta being a 23-rd root of unity fails to have unique factorization.
This is for a proof but I was generally more curious so it isn't in the homework section.
If I were to make a set A which is defined as all the prime factors of an integer a there could be some numbers in A which are repeated, would these count as distinct members or not? The reason why I was...
Homework Statement
Is there like a formula with a name easy to remember of which the following is a specific instance:
x^200 -y^200 = (x-y)(x^199+x^198y+... + y^198*x + y^199)
?
Homework Equations
The Attempt at a Solution
This was taken from a math contest a few months ago.
Homework Statement
xx*yy=zz
find z if:
x=28 * 38
y=212 * 36
Homework Equations
Theres undoubtably some trick, but I have yet to find it
The Attempt at a Solution
Dont even think about calculator
I showed my math teacher, and...
Homework Statement
Let A and B be invertible n×n matrices and b be an n×1 vector.
Write a MATLAB function with inputs (A,B, b) to solve the equation x=B^−1*(2A^−1 + 1)b
Make use of functions "LU Facotrization, Forward Substituion and Backwards Substitution" and DO NOT calculat any...
ok i know about the thing, i think its called gauss-jordan, where you do elimination on [A I] and you get [I A^-1] or [R E]or something like that.
question is how can you get the E that puts A into reduced row echelon form with "row operations" only...supposedly some easy way ?
on pg 134...
Hello everyone. I'm stuck on this problem and not sure how to apply the Unique factorization therem also called (Fundamental Theorem of Arithmetic). Heres the problem:
http://suprfile.com/src/1/45ym0fx/lastscan.jpg
The back of the book gives a pretty big hint which is the following...
This method utilizes discrete binary operations, in particular notice that.
(I1) Div(x+y+z,a)=Div(x,a)+Div(y,a)+Div(z,a)+\{0,1,2\}
This means that for one of the elements of the included set {0,1,2} the equation is true. This notation is quite useful for carrying out long calculations...
[Of course some of you will let me know if we need numerical examples or if something just does not make sense, or if it is very similar to what somebody else has already done, and I appreciate that.]
Suppose we have a reducible polynomial over the natural numbers (zero include) such that...
for x^3 - 4x^2 -x = 0 , i have found one of the root which is 1 by dividing this equation by (x-1).
from there onwards i can't do already to find the other two roots.somebody pls help
thanx
Consider the following true statement. Given natural numbers n, m, s
(1) \sum_{i=0}^n a^i = \sum_{i=0}^s a^{(m+1)i} \sum_{i=0}^m a^i
iff
(2) n+1=(m+1)(s+1)
Now suppose that N is a natural number where
(3) N = \sum_{i=0}^n a^i
Now restrict a to the natural...
I haven't taken a math class since high school and I'm 23 now. I jumped right into Precalc 1 for the summer and the first chapter kicked my ass. I completely forgot how to factor and do LCD with algebraic equations and my professor just breezes by it like its nothing.
Can anyone explain the...
While I know the time complexity for all known prime factorization algorithms is exponential, I can't seem to get this results for a very simple algorithm.
First assume we're doing this with numbers that are simply the product of two primes (the kind you get when working with RSA and others)...
I need to determine whether or not \mathcal{O}_{-10} = \mathbb{Z}[\sqrt{-10}] is a unique factorization domain.
Now, I think the short answer is simply: NO.
The question is meant to be simple (I think).
I just finished proving that \mathcal{O}_{-5} = \mathbb{Z}[\sqrt{-5}] is NOT a...