Factorization of Integers

Integer factorization decomposes a number into smaller numbers called the divisors, such that when these smaller divisors are multiplied they return the original number.

Factorizing integers allows us to better understand the property of that number than you would if you simply wrote the number as it is.

Fundamental Theorem of Arithmetic:

Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers. $_\square$

Writing numbers as the product of prime is called prime factorization. Prime factorization is important in the study of divisors. We can say from the above statement that primes are the building block of numbers.

In the following examples, we will see how factorization is helpful when solving problems.

What is the sum of the digits in the decimal representation of $64^{20}\times 25^{55}$?

---

Rewriting the expression gives

$$64^{20}\times 25^{55}=\left(2^{6}\right)^{20}\times \left(5^{2}\right)^{55}=2^{120}\times 5^{110}.$$

Putting the $2$ and $5$ together, we have

$$(2*5)^{110}\times 2^{120-110}=10^{110}\times 2^{10}.$$

This is equal to $1024$ with $110$ zeros at the end, Thus the sum of the digits is equal to $1+0+2+4=7$. $_\square$

We can see from the above example that factorizing a number can give more information about that number. Let us look at another example.

Let the number $$59^{5}+5\times 59^{4}+10\times 59^{3}+10\times 59^{2}+5\times 59+1=a^{p}b^{q}c^{r},$$ where $a<b<c$, then what is the value of $p+q+r$?

---

Let $x=59$, then the left side of the given expression can be rewritten as

$$x^{5}+5\times x^{4}+10\times x^{3}+10\times x^{2}+5\times x+1=(x+1)^{5}.$$

Thus, we have $(x+1)^{5}=(59+1)^{5}=777600000$. Since prime factorization of $777600000$ gives

$$777600000=2^{10}3^{5}5^{5}, p=10, q=5, r=5,$$

so $p+q+r=5+5+10=20$. $_\square$

As shown in the above example, when dealing with lots of numbers, it is sometimes helpful to substitute a number that seems to follow a certain pattern or have a repetitive structure, with a variable and simplify it as we would any other expression.

What is the value of $2014^{3}-2013\times 2014^{2}-2013^{2}\times 2014+2013^{3}$?

---

Let $b=2013$ and $a=2014$, then $$\begin{aligned} a^{3}-b\times a^{2}-b^{2}\times a+b^{3} &=a^{2}(a-b)-b^{2}(a-b)\\ &=(a+b)(a-b)(a-b)\\ &=(2014+2013)(1)(1)\\ &=4027. \ _\square \end{aligned}$$