# How do you factor 10001 without calculator?

Printable View

• December 2nd 2013, 05:43 PM
willy0625
How do you factor 10001 without calculator?
This Olympiad questions states:

[Show that every term of the sequence 10001, 100010001, 1000100010001, ... is composite.]

Well, I figured out this sequence is generalised as an = 10001n for all n $>=$ 1.
After actually doing this division in Excel(I know... I cheated), I found out the prime factorisation of 10001 = 73*137, hence proving the claim.
If I had no access to Excel, how would you have come up with this factorisation. Any results we can make use of to get the prime factorisation?

Thanks
• December 2nd 2013, 05:56 PM
chiro
Re: How do you factor 10001 without calculator?
Hey willy0625.

I vaguely remember results regarding 1 (mod 4) and 3 (mod 4) for prime-ness and composite numbers. Maybe you could search for those results and see if they apply in your situation.
• December 2nd 2013, 06:02 PM
Plato
Re: How do you factor 10001 without calculator?
Quote:

Originally Posted by willy0625
This Olympiad questions states:

[Show that every term of the sequence 10001, 100010001, 1000100010001, ... is composite.]

Note that $a_0=1001$ and if $n\ge 1$ then $a_n=a_{n-1}+10^{-4(n+1)}$
• December 3rd 2013, 11:20 AM
Soroban
Re: How do you factor 10001 without calculator?
Hello, willy0625!

Quote:

Show that every term of the sequence 10001, 100010001, 1000100010001, ... is composite.

Well, I figured out this sequence is generalised as an = 10001n for all n $>=$ 1. . No!

Not true . . .. . $\begin{array}{c}10001^2 \:=\:{\bf1}000{\bf2}000{\bf1} \\ 10001^3 \:=\:{\bf1}000{\bf3}000{\bf3}000{\bf1} \\ 10001^4 \:=\:{\bf1}000{\bf4}000{\bf6}000{\bf4}000{\bf1} \end{array}$ . . . . Note the "binomial" pattern.

$\begin{array}{cccccc}\text{We have:} & a_1 &=& 10001 &=& 10^4 + 1 \\ & a_2 &=&100010001 &=& 10^8 + 10^4 + 1 \\ & a_3 &=&1000100010001 &=& 10^{12} + 10^8 + 10^4 + 1 \\ & \vdots && \vdots && \vdots \\ & a_n &=& 1000100010001...0001 &=& 10^{4n} + 10^{4(n-1)} + \cdots + 10^8 + 10^4+1 \end{array}$

$\text{That is: }\:a_n \;=\;\sum^n_{k=0}10^{4k}$

Want to try it again?