NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/math/10478

Internet Message Format | 1992-08-21 | 3.2 KB

Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!samsung!balrog!web.ctron.com!wilson
From: [e-mail]
Newsgroups: sci.math
Subject: Re: u(v^n)w prime puzzle (SPOILER)
Message-ID: <[e-mail]>
Date: 21 Aug 92 15:11:07 GMT
Sender: [e-mail]
Reply-To: [e-mail] ()
Organization: Cabletron Systems INc.
Lines: 105
Nntp-Posting-Host: web
Originator: wilson@web



    Let B >= 2.  For string s over the base-B digits, let val(s) be the
    integer value of s as a base-B numeral (if s is the empty string,
    val(s) = 0).

    Choose strings u, v, and w of base-B digits, and for integer n >= 0,
    let

                     n
    f(n) = val(uv w)

    Since val(s) >= 0 for all s, f(n) >= 0 for all n.  We wish to show
    the either f(n) is a constant function of n, or that some f(n) is
    composite.

    It is not hard to show that there exist nonnegative integers a, b, c
    such that a >= 0, b >= 0, and

    f(n) =    a        if n = 0
        b*f(n-1)+c    if n > 0.

    (The values of a, b, and c in terms of u, v, and w are left to the
    interested reader).

    If b = 0, or if b = 1 and c = 0, f(n) is constant.

    Otherwise, f(n) is increasing in n, and we wish to show that
    some f(n) is not prime.  Suppose, then, that all f(n) are prime.

    Since f(n) increases in n, choose n with f(n) > b.  Since f(n) is
    prime, we have (b, f(n)) = 1.  Let p = f(n).

    Now observe the residues of the infinite sequence f(n), f(n+1), ...
    mod p.  Because of the recurrence f(n) = b*f(n-1)+c, and the number
    of residues mod p is finite, the sequence of residues eventually
    becomes cyclic.

    Suppose the residue cycle starts at f(n+j), j >= 1.  Clearly, the
    cycle has some length k <= p.  Since f(n+j) is in the cycle, we have

    f(n+j) == f(n+j+k) (mod p)

    However, f(n+j-1) is not in the cycle, so

    f(n+j-1) ~== f(n+j+k-1) (mod p)

    Because (b, p) == 1

    b*f(n+j-1)+c ~== b*f(n+j+k-1)+c (mod p)

    and by the recursion for f(n),

    f(n+j) ~== f(n+j+k) (mod p)

    a contradiction.  We must therefore conclude that j = 0, and the
    cycle starts at f(n), so that

    f(n) == f(n+k) (mod p).

    But f(n) = p, so

    f(n+k) == 0 (mod p).

    also, f(n) is increasing, so f(n+k) > f(n) = p.  This means that
    f(n+k) is a composite multiple of p, as required.

        -------<>------

    Let us look at an example.  Let B = 10, u = "1", v = "36", w = "1".
    We then have

    f(0) = 11
    f(1) = 1361
    f(2) = 136361
    f(3) = 13636361
    f(4) = 1363636361
    ...

    all primes so far.  How do we locate the composite?

    First, we find the recursion

    f(0) = 11
    f(n) = 100 f(n-1) + 261

    (a = 11, b = 100, c = 261)

    Now, we choose n so that (f(n), b) = 1.  In this case, n = 0, and
    f(n) = 11 works fine.  Let p = f(n) = 11.

    Next, look at the residues of f(n), f(n+1), ... mod 11.  They are

    n            0  1  2  3  4  5  6  7  8  9 10 11
    f(n) (mod 11)    0  8  5  2 10  7  4  1  9  6  3  0

    At n = 11, we see that f(n) == 0 (mod 11), as guaranteed by the
    theorem, and so 11 | f(11).  Since f(n) increases, f(11) > 11,
    so f(11) is composite.

--
David W. Wilson ([e-mail])

Disclaimer: "Truth is just truth...You can't have opinions about truth."
- Peter Schikele, introduction to P.D.Q. Bach's oratorio "The Seasonings."