# Prime factorization of $9095625$ by hand

I'm interested to know if anyone knows of an efficient way to get the prime factorization of the following number by hand $9095625$.

• It certainly contains a 5 – Zelos Malum Sep 19 '16 at 3:26
• Just keep trying small prime factors, and, when you find them, divide by them to make the number smaller. For this particular number, you won't have to divide by anything larger than 7. – Greg Martin Sep 19 '16 at 3:28
• Also, the last 3 digits being divisible by 125 tells you it is divisible by 125. – SquirtleSquad Sep 19 '16 at 3:29
• The last 3 digits being divisible by 625 is not sufficient for the number to be divisible by 625, take 1625 for example. – SquirtleSquad Sep 19 '16 at 3:49
• If there is a unifying theme to these comments, it's that knowing your divisibility tricks will help you out in these kinds of problems. – Alfred Yerger Sep 19 '16 at 3:49

Some quick checks:

• The final digit of $9095625$ is $5$, so it is divisible by $5$. Repeatedly dividing by $5$ yields

$$9095625 = 5 \cdot 1819125 = 5^2 \cdot 363825 = 5^3 \cdot 72765 = 5^4 \cdot 14553$$

• The sum of the digits of $14553$ is $18$, so it is divisible by $9$. Repeatedly dividing by $3$ yields

$$14553 = 3 \cdot 4851 = 3^2 \cdot 1617 = 3^3 \cdot 539$$

• The next reasonable guess might be that $539$ is divisible by $7$... and indeed it is:

$$539 = 7 \cdot 77 = 7^2 \cdot 11$$

• ...and $11$ is prime, so we're done.

In summary: $$9095625 = 3^3 \cdot 5^4 \cdot 7^2 \cdot 11$$

• After factoring out 3**3, we are left with 539, Here we can take sum of the alternate digits. 5+9=14 & 3. Now taking difference between the two groups, we get 14-3=11. Hence the number is divisible by 11. By factoring out 11, we get 539=11 * 49. <p> Refer to summary of Divisibility rules – Wishwas Sep 19 '16 at 5:03

Since we're doing the prime factorization, you can just use the long division algorithm that you learned in grade school. Use the last digit as a clue for what to divide by. Remember that any number has a unique prime factorization, so always just divide by the smallest feasible prime.

In this case, we start by recognizing that the number is obviously divisible by $5$. Divide it by $5$, we get $1819125$.

Divide by $5$ again. We get $363825$.

And again. We get $72765$.

And again. We get $14553$. The sum of the digits here is $18$, which is divisible by $3$, so this number is also divisible by $3$. Let's divide by $3$. We get $4851$.

The sum of the digits of $4851$ is $18$ again, so let's divide by $3$ again. We get $1617$.

The sum of the digits of $1617$ is $15$, so we can go for one more round of dividing by $3$. We get $539$.

To move swiftly from this step, we use a less-well-known divisibility trick. Dividing by $7$, we get $77$.

Clearly the final prime factors of $77$ are $7$ and $11$. So there you go, the prime factorization is $3^3 \cdot 5^4 \cdot 7^2 \cdot 11$.

On a whole, I wouldn't worry too much about problems like these. Doing prime factorizations by hand is pretty tedious, and it requires knowing all kinds of divisibility tricks. To me, this is like learning parlor tricks. Real mathematical problems lie in other domains.

Also, regarding your first sentence: in the computability-theoretic view, there is no efficient algorithm for finding the prime factorization of an integer. Finding such an algorithm would almost certainly be the discovery of the century.

• Good approach. If one is given a problem like this and not allowed a calculator, you should be able to assume that all the prime factors (except maybe the last) are small, so divisibility checks and trial division should see you through. The hardest type I would think is fair is something like $2^4\cdot 3^4\cdot 13 \cdot 19\cdot 541=173180592$ You can get all the small factors by divisibility checks or trial division, then use Fermat's little theorem to show $541$ is prime. The upper limit of what should be tested by trial division is up for discussion. – Ross Millikan Sep 19 '16 at 3:54
• @RossMillikan: Do you really mean Fermat's little theorem? I believe that can never guarantee that a number is prime, because there are pseudoprimes. But in your example, of course, trial division through $\sqrt{541} < 24$ is enough. – Ravi Fernando Sep 19 '16 at 6:39

Last $4$ digits of the number, i.e. $5625$, is divisible by $625$ $\Longrightarrow$ $9095625$ is divisible by $625$( i.e., $5^4$), giving the quotient as $14553$.

The sum of alternate digits of $14553 (1-4+5-5+3)$ is $0$ $\Longrightarrow$ the number is divisible by $11$, giving the quotient as $1323$.

Sum of digits of $1323$ is $9$ $\Longrightarrow$ the number is divisible by $9$, giving the result as $147$.

Sum of $147$ $(1+4+7=12)$ is divisible by $3$ giving the quotient as $49$ which in turn is divisible by $7$.

Combining them all gives $9095625= 5^4.11.3^3.7^2$

Obviously it's divisible by 5 as it ends in 5. And as it ends in $625$ it is divisible by $5^3 =125$.

$[xxxxx625 =xxxxx000 +625 = xxxxx*1000 +625 =125 (xxxxx*8 +5)]$

[added Dec 23, 2016: Numbers ending with $k$ zeros are obviously divisible by $10^k$. As $10 = 2*5$ any number ending with $\frac 1{2^k}10^k = 5^k$ with the proper leading zeros will be divisible by $5^k$. So any number ending with $25$ is divisible but $25$. Any ending with $125$ is divisible by $125$ and numbers ending with $0625$ are divisible by $625$. This number ends with $625$ but not $0625$ so I can not claim it is divisible by $625$.]

[The leading zeros area necessary as the are argument is $xxx0625 = xxx*10000 + 625; 625|10000$ so $625|xxx0625$. If there is no leading zero $xxx625 = xxx*1000 + 625; 625\not \mid 1000$ so we can not make that argument.]

[ However numbers ending with $j*5^k; 0\le j < 2^k$ are also clearly divisible by $5^k$. Example: Numbers ending with $75$ are divisible by $25$ and numbers ending with $125, 375, 625,875$ are all divisible by $125$. I could have noted that $5625 = 9*625$ so the number is divisible by $625$ but recognizing $5625=9*5^4$ is not something that I think is reasonably obvious. Although I do think $625 = 5*5^3$ is.]

[Of course, once I recognize that the number is divisible by $5$, I could just keep dividing by $5$ until I couldn't any more. So if I had $4001953125$ I could simply recognize that $001953125 = 5^9$. Or that $3125=5*5^4$ or $125= 5^3$ or simple the thing is divisible by $5$ and repeat as necessary.]

So $9095625=125*(9095*8+5)$...

Well we can see that is divisible by a higher power of 5.

$9095625=5^4 (1819*8+1)$

We also see $9+0+9+5+6+2+5=36=4*9$ so we know $9$ is a factor.

$5^4 (1819*8 +1)=5^4 (9*202*8 +(8+1))=5^4*9*(202*8+1)=5^4*3^2 (1617)$

$1+6+1+7=15$ is a multiple of 3 (but not 9).

So $9095625=5^4*3^3 (539)$

Now we must factor $539$. I have only one trick left for determining if something is divisible by 11. $5+9 \ne 3$ so it is not divisible by 11.

My only trick now is casting out.

Is it divisible by 7? $539 - 700 =-161; 161-70=91;91-70=21=3*7$. So yes it is.

Actually I can do better. $539 -490=49$ so $539= 490+49=7*77$ and ... but I thought it wasn't divisible by 11!

Oh, wait, $5+9 =14 =3 +11$ so, yes, it was, after all. Oh well, we all make mistakes.

So $9095625 =5^4*3^3*7^2*11$

=====

Or how I'd really do it:

$9095625$ ends with 5.

$9095625\div 5 =9095625*2\div 10 =1819125$

$1819125*2\div 10 = 363825$

$363825*2\div 10= 72765$

$72765*2\div 10 = 14553$

$1+4+5+5+3=9+9$

$14553\div 9 = 1617$

$1+1+6+7=9+6$

$1617\div 3=539$

$539-49=490$

$539\div 7= 77=7*11$

So $9095625=5^4*3^3*7^2*11$