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 a_{n} = 10001^{n} for all n $\displaystyle >=$ 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

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.

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 $\displaystyle a_0=1001$ and if $\displaystyle n\ge 1$ then $\displaystyle a_n=a_{n-1}+10^{-4(n+1)}$

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 a_{n} = 10001^{n} for all n $\displaystyle >=$ 1. . No!

Not true . . .. . $\displaystyle \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.

$\displaystyle \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}$

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

Want to try it again?