\myheading{Integer factorization}

\leveldown{}

Natural number can be either prime or composite number.
Composite number is a number which can be breaked up by product of prime numbers.
Let's take 100.
It's not a prime number.

By the \textit{fundamental theorem of arithmetic},
any (composite) number can be represented as a product of prime numbers, in only one single way.

So the \textit{composite number} phrase means that the number is \textit{composed} of prime numbers.

Let's factor 100 in Wolfram Mathematica:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= FactorInteger[100]
Out[]= {{2, 2}, {5, 2}}
\end{lstlisting}

This mean that 100 can be constructed using 2 and 5 prime numbers ($2^2 \cdot 5^2$):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= 2^2*5^2
Out[]= 100
\end{lstlisting}

You can think about composite number as a rectangle of balls:

\begin{lstlisting}
oooo ... oo
oooo ... oo

...........

oooo ... oo
oooo ... oo
\end{lstlisting}

You know how many balls are here, but the problem is to get width and/or height.

\myheading{Using composite number as a container}

Even more than that, it's possible to encode some information in prime numbers using factoring.
Let's say, we would encode the ``Hello'' text string.
First, let's find ASCII codes of each character in the string:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= ToCharacterCode["Hello"]
Out[]= {72, 101, 108, 108, 111}
\end{lstlisting}

Let's find the first 5 prime numbers, each number for each character:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= Map[Prime[#] &, Range[5]]
Out[]= {2, 3, 5, 7, 11}
\end{lstlisting}

Build a huge number using prime numbers as bases and ASCII codes as exponents, then get a product of all them 
($2^{72} \cdot 3^{101} \cdot 5^{108} \cdot 7^{108} \cdot 11^{111}$):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = 2^72*3^101*5^108*7^108*11^111
Out[]= \
1649465578065933994718255257642275679479006861206428830641826551739434\
9344066214616222018844835866267141943107823334187149334898562231349428\
5708281252457614466981636618940129599457183300076472809826225406689893\
5837524252859632074600687844523389231265776082000229507684707641601562\
5000000000000000000000000000000000000000000000000000000000000000000000\
000
\end{lstlisting}

It's a big number, but Wolfram Mathematica is able to factor it back:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= FactorInteger[tmp]
Out[]= {{2, 72}, {3, 101}, {5, 108}, {7, 108}, {11, 111}}
\end{lstlisting}

A first number in each pair is prime number and the second is exponent.
Get the text string back:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= FromCharacterCode[Map[#[[2]] &, tmp]]
Out[]= "Hello"
\end{lstlisting}

That allows to have some fun.
Let's add exclamation point to the end of string by manipulating only the \textit{big number}.
ASCII code of exclamation point is 33. The next prime number after 11 is 13.
So add it (by multiplying by $13^{33}$):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = tmp*13^33
Out[]= \
9494539005656577744061615691556750598033024729435332190254469113536733\
9032823543118405499931761589928052797992206631285822671397023217541663\
5920521812548793623881568510051214975599793760307837993570818136014139\
9497958680836430182400405525832564875875193876694267121604212637095253\
0725145452728611417114734649658203125000000000000000000000000000000000\
000000000000000000000000000000000000000
\end{lstlisting}

So we got new number. Let's factor it back and decode:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= factored = FactorInteger[tmp]
Out[]= {{2, 72}, {3, 101}, {5, 108}, {7, 108}, {11, 111}, {13, 33}}

In[]:= FromCharacterCode[Map[#[[2]] &, factored]]
Out[]= "Hello!"
\end{lstlisting}

Wow, that works. Will it be possible to remove one 'l' character from the string at the third position?
The 'l' has the ASCII code of 108 and it is exponent for two prime numbers in our expression: 5 (first 'l') and 7 (second 'l').

To knock out the character, we divide the \textit{big number}
by the corresponding prime number with the exponent of 108 (divide by $5^{108}$):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = tmp/5^108
Out[]= \
3081154065769189664244341216329094565621009415122099836376732969546063\
1079164051611808432546107410277501678916823138724630810880390384343750\
1196528030610615786507542545262118293483878711112407171889948257893463\
8494741216231004109210436295299274515484540190050751059821909485854359\
9630924207126074604240892753608704

In[]:= factored = FactorInteger[tmp]
Out[]= {{2, 72}, {3, 101}, {7, 108}, {11, 111}, {13, 33}}

In[]:= FromCharacterCode[Map[#[[2]] &, factored]]
Out[]= "Helo!"
\end{lstlisting}

\myheading{Using composite number as a container (another example)}

Let's say, the initial \textit{container} number is 1.
Let's increment the number at the second position within it by multiplying by the first prime number (3):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = 1*3
Out[]= 3
\end{lstlisting}

Then let's set the number at fourth position to 123.
The fourth prime number is 7 (the percent sign in Mathematica denotes the last result):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = tmp*7^123
Out[]= 26557071110804040505330743411815438275701018334410643480070773\
5780279761186999642944265644421128096489029
\end{lstlisting}

Then let's set the number at fifth position to 456. The fifth prime number is 11:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = tmp*11^456
Out[]= 19917948660639605307938425372554395433764512138284060223646519\
1257621966825293455339751080188144910510813322192288287162176499976800\
9147068591160798243308591883294649069355015558472564457422829073938118\
4396204999051856879940101934339913600942451006747982291524910653185084\
4057972896537894301213735252418639782974592077393028390193060138936503\
0125465578958567377627063815620261557939484036628536230966158222960762\
8509899641574477547658142457598168497006309608599830554758951672484533\
9216105863754463712957143732563375990198901073698626584903164027850451\
8825659837114080589573087269
\end{lstlisting}

Then let's decrement the number at fourth position, the fourth prime number is 7:

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= tmp = tmp/7
Out[]= 28454212372342293297054893389363422048235017340405800319495027\
3225174238321847793342501543125921300729733317417554695945966428538287\
0210097987372568919012274118992355813364307940675092082032612962768740\
6280292855788366971343002763342733715632072866782831845035586647407263\
4368532709339849001733907503455199689963702967704326271704371627052147\
1607807969940810539467234022314659368484977195183623187094511747086804\
0728428059392110782368774939425954995723299440856900792512788103549334\
1737294091077805304224491046519108557427001533855180835575948611214931\
260808548159154369939012467
\end{lstlisting}

Let's factor the composite number and get all the numbers we set inside \textit{container} (1, 122, 456):

\begin{lstlisting}[caption=Wolfram Mathematica]
In[]:= FactorInteger[tmp]
Out[]= {{3, 1}, {7, 122}, {11, 456}}
\end{lstlisting}

So the resulting number has $3 \cdot 7^{122} \cdot 11^{456}$ form at the end.

This is somewhat wasteful way to store the numbers, but out of curiosity: 
since there are infinite number of prime numbers and so any number of infinitely big numbers can be \textit{stored}
within one (although huge) composite number.

\levelup{}