Prime factorization of $9095625$ by hand

Question

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

Answer 1

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$$

Answer 2

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.

Answer 3

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$

Answer 4

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$