Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Prime factorization"

m (organized a little)
(Updated link to Prime Shooter and added example)
Line 1: Line 1:
 
For a positive integer <math>n</math>, the '''prime factorization''' of <math>n</math> is an expression for <math>n</math> as a product of powers of [[prime number]]s.  An important theorem of [[number theory]] called the [[Fundamental Theorem of Arithmetic]] tells us that every [[positive integer]] has a unique prime factorization, up to changing the order of the terms.   
 
For a positive integer <math>n</math>, the '''prime factorization''' of <math>n</math> is an expression for <math>n</math> as a product of powers of [[prime number]]s.  An important theorem of [[number theory]] called the [[Fundamental Theorem of Arithmetic]] tells us that every [[positive integer]] has a unique prime factorization, up to changing the order of the terms.   
 +
 
The form of a prime factorization is  
 
The form of a prime factorization is  
 +
<math>n = {p_1}^{e_1} \cdot {p_2}^{e_2}\cdot{p_3}^{e_3}\cdots{p_k}^{e_k}</math>
 +
where <math>n</math> is any natural number, the <math>p_{i}</math> are prime numbers, and the <math>e_i</math> are their positive integral exponents.
 +
 +
Prime factorizations are important in many ways. One instance is to simplify [[fraction]]s.
  
 +
==Techniques==
  
−
<math>\displaystyle n = {p_1}^{e_1} \cdot {p_2}^{e_2}\cdot{p_3}^{e_3}\cdots{p_k}^{e_k}</math>
+
The common method of prime factorization is checking prime numbers, case by case.  Use [[divisibility rules]] to check if primes (or powers of primes) are a factor and then move up to a different prime if said prime is not a factor.  When a prime is a factor, we factor out the prime and check for factors in the resulting number.
  
 +
Sometimes, we could easily see that a number is a multiple of a composite number or a prime.  For instance, <math>50</math> is a factor of <math>2650</math>, and <math>49</math> is a factor of <math>4998</math>.  In these cases, a good strategy is to choose the number accordingly to make factoring easier.
  
−
where <math>\displaystyle n</math> is any natural number, the <math>p_{i}</math> are prime numbers, and the <math>e_i</math> are their positive integral exponents.
+
==Example==
  
−
Prime factorizations are important in many ways. One instance is to simplify [[fraction]]s.
+
Consider the number <math>38052</math>.
 +
 
 +
* Because the last two digits of the given number are a multiple of <math>4</math>, we can rewrite <math>38052</math> as <math>2^2 \cdot 9513</math>.  Note that <math>9513</math> is not even, so we move on.
 +
* Because the sum of digits of <math>9513</math> is a multiple of 9, we can rewrite <math>38052</math> as <math>2^2 \cdot 3^2 \cdot 1057</math>.  Note that the sum of digits of <math>1057</math> is not a multiple of 3, so we move on.
 +
* Because <math>1057</math> does not end in <math>0</math> or <math>5</math>, we skip <math>5</math> as a factor.  As for <math>7</math>, after long division, we note that <math>1057 = 7 \cdot 151</math>, so we can rewrite <math>38052</math> as <math>2^2 \cdot 3^2 \cdot 7 \cdot 151</math>.  However, when doing long division again, <math>151</math> is not a multiple of <math>7</math>, so we move on.
 +
* Note that <math>11</math> is not a factor of <math>151</math>, so we can move on.  In fact, because <math>13 > \sqrt{151}</math>, we can declare <math>151</math> as prime and stop.
  
−
===Example Problem===
+
Thus, the prime factorization of <math>38052</math> is <math>2^2 \cdot 3^2 \cdot 7 \cdot 151</math>.
  
−
The prime factorization of 378 is <math>2^1\cdot3^3\cdot7^1</math>.
+
==Problems==
  
 +
===Introductory===
 +
* Practice Problems from [https://artofproblemsolving.com/alcumus/ Alcumus]
 +
** Prime Factorization (Prealgebra, Number Theory)
 +
* [[2000 AIME I Problems/Problem 1]]
  
 
== Resources ==
 
== Resources ==
 +
 
=== Books ===
 
=== Books ===
 
* [http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?page_id=10 Introduction to Number Theory] by [[Mathew Crawford]]
 
* [http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?page_id=10 Introduction to Number Theory] by [[Mathew Crawford]]
 
=== Games ===
 
=== Games ===
−
* [http://www.1729.com/math/integers/PrimeShooter.html Prime Shooter]
+
* [http://thinkinghard.com/math/integers/PrimeShooter.html Prime Shooter]
  
  
 
==See also==
 
==See also==
 
*[[Divisor]]
 
*[[Divisor]]
 +
*[[Divisibility rules]]
 +
 +
[[Category:Number theory]]

Revision as of 19:04, 11 June 2020

For a positive integer $n$, the prime factorization of $n$ is an expression for $n$ as a product of powers of prime numbers. An important theorem of number theory called the Fundamental Theorem of Arithmetic tells us that every positive integer has a unique prime factorization, up to changing the order of the terms.

The form of a prime factorization is $n = {p_1}^{e_1} \cdot {p_2}^{e_2}\cdot{p_3}^{e_3}\cdots{p_k}^{e_k}$ where $n$ is any natural number, the $p_{i}$ are prime numbers, and the $e_i$ are their positive integral exponents.

Prime factorizations are important in many ways. One instance is to simplify fractions.

Techniques

The common method of prime factorization is checking prime numbers, case by case. Use divisibility rules to check if primes (or powers of primes) are a factor and then move up to a different prime if said prime is not a factor. When a prime is a factor, we factor out the prime and check for factors in the resulting number.

Sometimes, we could easily see that a number is a multiple of a composite number or a prime. For instance, $50$ is a factor of $2650$, and $49$ is a factor of $4998$. In these cases, a good strategy is to choose the number accordingly to make factoring easier.

Example

Consider the number $38052$.

  • Because the last two digits of the given number are a multiple of $4$, we can rewrite $38052$ as $2^2 \cdot 9513$. Note that $9513$ is not even, so we move on.
  • Because the sum of digits of $9513$ is a multiple of 9, we can rewrite $38052$ as $2^2 \cdot 3^2 \cdot 1057$. Note that the sum of digits of $1057$ is not a multiple of 3, so we move on.
  • Because $1057$ does not end in $0$ or $5$, we skip $5$ as a factor. As for $7$, after long division, we note that $1057 = 7 \cdot 151$, so we can rewrite $38052$ as $2^2 \cdot 3^2 \cdot 7 \cdot 151$. However, when doing long division again, $151$ is not a multiple of $7$, so we move on.
  • Note that $11$ is not a factor of $151$, so we can move on. In fact, because $13 > \sqrt{151}$, we can declare $151$ as prime and stop.

Thus, the prime factorization of $38052$ is $2^2 \cdot 3^2 \cdot 7 \cdot 151$.

Problems

Introductory

Resources

Books

Games


See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Prime_factorization&oldid=125055"