Factoring numbers I was given the following problem:
Prove that 767, 76767, 7676767 ... are all composite.
Making a sequence $a(n)$ = {767, 76767, 7676767, ...} you can show that $a(3k+1)$ is divisble by 13, $a(3k+2)$ is divisible by 3, and $a(3k+3)$ is divisible by 7, for $k$ = 0, 1, 2, ...
Then, I gave the same question but for the following:
Prove that 343, 34343, 3434343, ... are all composite.
Prove that 717, 71717, 7171717, ... are all composite.
I wasn't able to use the same method that I used above. Any help with this?
 A: Let's look at how the method works for the example sequence.
The sequence $a_n$ is generated by the recurrence $a_{n+1}=100a_n+67$. Applying this three times, we get:
$$a_{n+3}=100(100(100a_{n} + 67)+67)+67=10^6a_n+676767$$
(Which really we could also have realized intuitively) The prime factors of $676767$ are $3, 7, 13, 37$ and $67$, and it so happens that each of $a_0, a_1$ and $a_2$ are divisible by one of those numbers. This is enough to start an induction showing what's asked in the problem statement. Indeed, if $a_n$ is divisible by a prime factor of $676767$, then $10^6a_n+676767$ is clearly also divisible by it.
Set up a similar recurrence relation for the other problems. Note that in the example problem, the choice of $3$ (you look at the effect of applying the recurrence function $3$ times) is somewhat arbitrary - it just happens to work. There's no guarantee that $3$ will work for the other examples. So look at what happens when you apply the recurrence $k$ times. You'll get a relation of the form:
$$a_{n+k}=10^{2k}a_n+c$$
You'll need a $k$ such that the numbers $a_0, a_1, ... a_{k-1}$ all have common factors with $c$. Note that of course both $c$ and the $a_i$ will have very specific, easily predictable forms, which might help the analysis.
