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 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 and if then

Re: How do you factor 10001 without calculator?