>Below each line giving u,v,w values appear a lot of prime
>numbers. These patterns do eventually fail:
>
> 333333331 = 17*19607843
> 13636363636361 = 17*1321*5693*106661
> 17575757575757575709 = 232433*75616446785773
>
>The question is, are there any {u,v,w} examples which do
>not fail? That always give prime numbers?
> I know the solution to this puzzle. I think the
>solution can be understood fairly easily by anyone that
>has had a first course in number theory. See if you
>can discover it.
>
Let x_n be the number u(v^n)w.
Let r be the number of digits in v and z be the sequence of r zeros.
x_{n+1} = uv ........... vvw
<-- n times -->
10^r x_n = uv ........... vwz
<-- n times -->
Notice that the sequences vw and wz at the end of each number have the same length
hence x_{n+1} - 10^r x_n = (vw - wz)
More generally, we have x_{n+1} = a x_n + b
and we have to prove that such a sequence is either constant or contains at least one composite, for any integral values of x_0,a,b (with a>1).
This is a well known result, but, just in case, here is a proof.
If (a x_0 + b = x_0), then all the term in the sequence are equal to x_0. This is obviously not the case in the proposed sequence u(v^n)w. Now, if not(a x_0 + b = x_0), then the sequence is monotone and we can assume without loss of generality that it is positive increasing (that's the case of the proposed sequence).
Assume that x_n contains only (positive) primes.
Let p be a prime such that neither p|a nor p|a-1
Since not(p|a-1), there exists c such that (a-1) c = 1 (mod p)
hence a c = c+1 (mod p) and a b c = b + b c (mod p)
x_{n+1} + b c = a x_n + b + b c = a x_n + a b c (mod p)
hence x_{n+1} + b c = a(x_n + b c) (mod p)
and, for all k
x_{n+k} + b c = a^k (x_n + b c) (mod p)
For k = p-1, by Fermat's theorem and not(p|a), we have a^k = 1 (p)
Hence x_{n+p-1} = x_n (mod p)
Hence, not(x_n = p) otherwise x_{n+p-1} which is strictly greater that x_n
would be divisible by x_n and wouldn't be prime.
Therefore,
for all p, if p prime and not(p|a) and not(p|a-1) then for all n not(x_n=p)
which is equivalent to
for all p, if p prime and (exists n, p=x_n) then p|a or p|a-1
By hypothesis, x_n is prime for all n. Hence
for all n, x_n|a or x_n|a-1
and the sequence cannot be ever increasing, a contradiction.
QED
Now, I propose the following question:
Is it true that any sequence x_{n+1} = a x_n + b is either constant or contains *infinitely many* composite ? *almost only* composite (i.e. it contains only a finite number of primes) ?
