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 (proofreading)
m (→‎Introductory)
 
(9 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
By the [[Fundamental Theorem of Arithmetic]], every positive integer has a unique prime factorization. What is a prime factorization? It is a representation of a number in terms of powers of primes (it is of the form <math>{p_1}^{e_1}\cdot</math><math>{p_2}^{e_2}\cdot{p_3}^{e_3}\cdots{p_k}^{e_k} = n</math>, where ''n'' is any natural number).
+
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.
−
Prime factorizations are important in many ways, for instance, to simplify [[fractions]].
+
 
−
===Example Problem===
+
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.
 +
 
 +
==Primes and Prime Factorization Video==
 +
https://youtu.be/6xNkyDgIhEE?t=543
 +
 
 +
==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, <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.
 +
 
 +
==Example==
 +
 
 +
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.
 +
 
 +
Thus, the prime factorization of <math>38052</math> is <math>2^2 \cdot 3^2 \cdot 7 \cdot 151</math>.
 +
 
 +
==Problems==
 +
 
 +
===Introductory===
 +
* Practice Problems from [https://artofproblemsolving.com/alcumus/ Alcumus]
 +
** Prime Factorization (Prealgebra, Number Theory)
 +
 
 +
===Intermediate===
 +
* [[2000 AIME I Problems/Problem 1]]
 +
 
 +
== Resources ==
 +
 
 +
=== Books ===
 +
* [http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?page_id=10 Introduction to Number Theory] by [[Mathew Crawford]]
 +
=== Games ===
 +
* [http://thinkinghard.com/math/integers/PrimeShooter.html Prime Shooter]
 +
 
 +
 
 +
==See also==
 +
*[[Divisor]]
 +
*[[Divisibility rules]]
 +
 
 +
[[Category:Number theory]]

Latest revision as of 21:14, 5 January 2024

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.

Primes and Prime Factorization Video

https://youtu.be/6xNkyDgIhEE?t=543

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

  • Practice Problems from Alcumus
    • Prime Factorization (Prealgebra, Number Theory)

Intermediate

Resources

Books

Games


See also

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