It might help to note that the numbers you are considering have the form . Can you see how to use that to factor 1001?
I tried to search for additional primes in this sequence and could not find any. (I believe that if a number of the form is prime, then must be of the form . I'm a bit too lazy to prove it right now.) Can part (b) even be fulfilled?
So can anyone do part b)?
For what it's worth, I've used PARI/GP to test numbers of the form 10^n+1 from n = 3 up to n = 6000 without finding any primes. To my knowledge, PARI's isprime() is deterministic rather than probabilistic.
What about 100501???
We're looking at . Suppose where is odd.
. Thus we see is composite for all such that .
So the only remaining case to show are numbers of the form . I'll see what I can come up with.
So, is there any definitive way of solving/proving part b)?
I can see that...if you have any more ideas, please post them up! I would really like to know how to solve this question!
Ok, so the question is : for which is prime.
Theorem : if , then if is odd.
The proof is trivial, if . This only works for odd due to the special status of square roots in a congruence ring.
Now, let and (since is prime). Then divides all numbers of the form where is odd. That is, 50% of all concerned numbers.
Then, let and (since is prime). Then 101 divides all numbers of the form where is odd (2, 6, 10, ...).
So we're still missing the numbers of the form with even. Let's look at . This one's got to be composite (divisible by ) since the exponent is odd.
This is as far as I can go yet. I'm missing numbers of the form for even :(
Perhaps actually setting with even, then :
Then breaking the congruence :
And working with both : we've got some kind of Mersenne number on one side, and the other one's got to be composite (divisible by 2). These are just ideas, I don't even know if it's valid to break up a congruence in such a way.