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?
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.