Article 12761 of sci.math:
Newsgroups: sci.math
From: jeanmarc@ecrc.de (Jean-Marc Andreoli)
Subject: Re: u(v^n)w prime puzzle
Reply-To: jeanmarc@ecrc.de
Organization: European Computer industry Research Centre GmbH.
Date: Wed, 19 Aug 1992 14:19:57 GMT
In article 14274@wri.com, roach@bikini.wri.com (Kelly Roach) writes:
>
>
>
> Prove or disprove: There are three non-empty
> strings of digits u,v,w such that all the
> numbers in
> L = {u(v^n)w | n is a natural number}
> = {uw, uvw, uvvw, uvvvw, uvvvvw, ...}
> are prime numbers.
>
>
> Time to say a few more words about my u(v^n)w prime
>puzzle which I posted yesterday. I am definitely not looking
>for any solutions involving u=v="0". Ordinary syntax only
>please. No leading zeros in u.
> Some interesting patterns:
>
> u="3",v="3",w="1"
> 31, 331, 3331, 33331, 333331, 3333331, 33333331
>
> u="1",v="36",w="1"
> 11, 1361, 136361, 13636361, 1363636361, 136363636361
>
> u="17",v="57",w="09"
> 1709, 175709, 17575709, 1757575709, 175757575709,
> 17575757575709, 1757575757575709, 175757575757575709
>
>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) ?
---
Jean-Marc Andreoli
---
Standard disclaimer.