Any ideas?
It might help to note that the numbers you are considering have the form $\displaystyle 10^n+1$. 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 $\displaystyle 10^n+1$ is prime, then $\displaystyle n$ must be of the form $\displaystyle 2^k$. I'm a bit too lazy to prove it right now.) Can part (b) even be fulfilled?
Haven't put too much thought into part b, but what I can tell you is a number of that form with an even number of zero's will always be divisible by $\displaystyle 11 $.
Divisibility rule - Wikipedia, the free encyclopedia
We're looking at $\displaystyle 10^a+1$. Suppose $\displaystyle a=2^ns $ where $\displaystyle s $ is odd.
$\displaystyle 10^a+1=\left(10^{2^n}\right)^s+1\equiv(-1)^s+1=0\bmod{(10^{2^n}+1)} $. Thus we see $\displaystyle 10^a+1 $ is composite for all $\displaystyle a $ such that $\displaystyle s\neq1 $.
So the only remaining case to show are numbers of the form $\displaystyle 10^{2^n}+1, \; n>3 $. I'll see what I can come up with.
I don't get it:
(1) Did you mean $\displaystyle \left(10^{2^n}\right)^s+1\equiv(-1)^s+1\!\!\!\pmod{10^{2^n}}$ ? This is absurd, and then looking at the extremes you get:
2) $\displaystyle 10^a+1=0\!\!\!\pmod{10^{2^n}}$ , which is also absurd...or, perhaps very probably, I misunderstood something.
Tonio
Ok, so the question is : for which $\displaystyle k$ is $\displaystyle 10^k + 1$ prime.
Theorem : if $\displaystyle p | 10^k + 1$, then $\displaystyle p | 10^{mk} + 1$ if $\displaystyle m$ is odd.
The proof is trivial, if $\displaystyle 10^k \equiv -1 \pmod{p} \ \implies \ 10^{mk} \equiv {(-1)}^m \pmod{p} \ \implies \ 10^{mk} + 1 \equiv 0 \pmod{p}$. This only works for odd $\displaystyle m$ due to the special status of square roots in a congruence ring.
Now, let $\displaystyle k = 1$ and $\displaystyle p = 10^1 + 1 = 11$ (since $\displaystyle 11$ is prime). Then $\displaystyle 11$ divides all numbers of the form $\displaystyle 10^m + 1$ where $\displaystyle m$ is odd. That is, 50% of all concerned numbers.
Then, let $\displaystyle k = 2$ and $\displaystyle p = 10^2 + 1 = 101$ (since $\displaystyle 101$ is prime). Then 101 divides all numbers of the form $\displaystyle 10^{2m}$ where $\displaystyle m$ is odd (2, 6, 10, ...).
So we're still missing the numbers of the form $\displaystyle 10^{2m} + 1$ with $\displaystyle m$ even. Let's look at $\displaystyle 10^{2m - 1} + 1$. This one's got to be composite (divisible by $\displaystyle 11$) since the exponent is odd.
This is as far as I can go yet. I'm missing numbers of the form $\displaystyle 10^{2m} + 1$ for $\displaystyle m$ even
Perhaps actually setting $\displaystyle 10^{2m} + 1$ with $\displaystyle m$ even, then :
$\displaystyle 10^{2m} \equiv -1 \pmod{p}$
$\displaystyle 2^{2m} \times 5^{2m} \equiv -1 \pmod{p}$
Then breaking the congruence :
$\displaystyle 2^{2m} \equiv \pm 1 \pmod{p}$ and $\displaystyle 5^{2m} \equiv \mp 1 \pmod{p}$
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.