Number Theory: Which numbers 101010...0101 are prime I have this problem assigned for homework and I'm having some trouble with it. I'm in elementary number theory.
Set $M(k)=100^{k-1}+\dotsc +100+1$. Note that $M(k)$ has exactly $k$ ones.
For which $k$ is $M(k)$ a prime?
Hint: Set $R(k)=111\cdots 1$ with exactly $k$ ones and observe that $11\cdot M(k)=R(2k)=R(k)\cdot (10^k +1)$.
Thanks!
 A: Another hint: I suppose the hint is trying to say something like if you "factor out" (deconvolve) "101" you will be getting $\sum_i 10^{4i}$. Does this make more sense?

Also you can look at the recursive relation $a_{n+1} = 1+100a_{n-1}$ ( which is one way to build the sequence ), how will it alter modulo $k$?
Fun curiosity, if we build the matrix $${\bf A} = \left[\begin{array}{rr}1&1\\0&100\end{array}\right]$$ we can observe ${\bf A}^2 = \left[\begin{array}{rr}1&101\\0&10^4\end{array}\right] , {\bf A}^3 = \left[\begin{array}{rr}
1&10101\\0&10^6\end{array}\right]$ and so on. So this is a way to generate the sequence (upper right element).
A: Suppose $k \geq 4$. Note that 11 divides exactly one of the factors on the right.
If $k$ is even, $M(k)=\frac{R(k)}{11} \times (10^k+1)$ has at least two factors; make a similar argument when $k$ is odd.
A: Big Hints:
If $n$ is odd, then $10^n\equiv(-1)^n\equiv-1\pmod{11}$. Therefore, $11\mid10^n+1$. Thus,
$$
\begin{align}
\sum_{k=0}^{n-1}100^k
&=\frac{100^n-1}{99}\\
&=\frac{10^n-1}{9}\frac{10^n+1}{11}
\end{align}
$$

If $n$ is even, then $n=2m$. Therefore,
$$
\begin{align}
\sum_{k=0}^{n-1}100^k
&=\sum_{k=0}^{2m-1}100^k\\
&=\sum_{k=0}^{m-1}100^{2k}(100+1)\\
&=101\sum_{k=0}^{m-1}100^{2k}\\
\end{align}
$$
Or we can start as we did when $n$ was odd,
$$
\begin{align}
\sum_{k=0}^{n-1}100^k
&=\frac{100^n-1}{99}\\
&=\frac{10^n-1}{99}(10^n+1)\\
&=\frac{100^m-1}{99}(10^n+1)
\end{align}
$$
