Conference rusure::math

    FYI,
    the book that mentioned the above, is called "Mathematics: the new
    golden age" by Keith Devlin. ,1988, 280 pages, cost $8.95. a very good 
    book, contents are :
    1. prime numbers, factoring and secret codes.
    2. sets, infinity and the undecidable.
    3. number systems and the class number problem
    4. beauty from chaos.
    5. simple groups
    6. hilbert tenth problem
    7. the four-colour problem
    8. fermat's last theorem
    9. hard problems about complex numbers <-- here is a very good outline
       of the riemman hypothesis, i dont understand it yet, but according
       to the auther, it is one of the most important unsolved problems in
       mathematics ! that is a good challange , anyone wants a PhD thesis
       topic? here is one !
    10. knots and other topolgical matters
    11. efficency of algorithms.
    
    /Nasser
    

    Publisher ? ISBN number ?
    
    Thanks
    CJ

    re .0
    
    For completeness... there are no primes in that range.
    
    Since N! = 1 * 2 * 3 * ... * N,
    
    k | N! for k = 2,...,N
    
    so k | N! + k for k = 2,...,N
    
    so N! + k is not prime for k = 2,...,N
    
    
    And a follow up question...what about N! + 1
    Is it always prime? never prime? Is there some pattern?

N!+1 can't always be prime.


"proof"

	It is impossible to find a closed form f(N) which is prime for all
	N.  If N!+1 were always prime, this would be violated.

Not to mention the fact that 5! is 5*4*3*2=120, and 121 is divisible by 11.
So, as long as 11 can be proved to be unequal to 1 (left to reader)...

> 	It is impossible to find a closed form f(N) which is prime for all
> 	N.  

But can you prove that?

-Jonathan

In fact there is a simple formula that always generates primes, of the form
[n**A] - i.e. it has been proved (by Selberg, I think) that there exists a
real constant A such that the integer part of n to the A is always prime 
for integer n > 2.
[I am recalling this from 30 years back, and the details are fuzzy. I think
someone established 2<A<3, but I may be wrong. I haven't seen anything about 
approximations to A.] 

Osman's comment is correct about polynomials with integer coefficients:
there is no p(n) that produces primes for all values of n.

I also saw recently an infinite matrix whose elements are generated by a
simple formula in {x,y}, and a simple function P, such that if n is in the
matrix then P(n) is composite, and if n is not in the matrix then P(n) is
prime. I will try to reproduce it here, if I can find it; I think it was in
a recent JRM. 

    
    Could it be true, that if N+1 is prime, then N!+1 is divisible
    by N+1 ?

>    Could it be true, that if N+1 is prime, then N!+1 is divisible
>    by N+1 ?

Yes. This is called Wilson's theorem, which is actually more general:

	If *and only if* N+1 is prime, then N!+1 is divisible by N+1.

so this is a test (albeit expensive) for primality. A proof can be found in 
most Num Thy texts.

>.4
>	It is impossible to find a closed form f(N) which is prime for all
>	N.  If N!+1 were always prime, this would be violated.

>.6
>Osman's comment is correct about polynomials with integer coefficients:
>there is no p(n) that produces primes for all values of n.

	f(N) = p(n) = 17

:-)
Dan

    re .various
    
    So far we have
    
    N!+1 is prime for the special cases N=1,2
    
    N!+1 is divisible by N+1 when N+1 is prime (and so N!+1 is not prime)
    
    
    N!+1 is not divisible by N+1 when N+1 is not prime
    This leaves open the question as to whether N!+1 is prime when N+1 is
    not prime. Any takers?

    soeone asked about the book info:
    publisher is pelican, ISBN # 0-14-022728-8
    got my copy from Barnes and Nobel in nashua. you could order one from
    there too.
    /nasser

    ref  <<< Note 1515.10 by ELIS::GARSON "V+F = E+2" >>>
    >This leaves open the question as to whether N!+1 is prime when N+1 is
    >not prime. Any takers?
    
    proof by producing one counter example
    ---------------------------------------
    N= 5, N+1= 6 , not prime
    
    N! = 120, N!+1 = 121 , but 121 not prime (121 is divided by 11 with no
    reminder)

re .8
    >Yes. This is called Wilson's theorem, which is actually more general:
    >	If *and only if* N+1 is prime, then N!+1 is divisible by N+1.

Suppose that N+1 | N!+1

Let z | N+1, therefore

Case A). z = N+1
Case B). z < N+1

     z | N+1  and  N+1 | N!+1   =>   z | N!+1
    but z < N+1   =>   z <= N   =>   z | N!
    therefore z | 1
    so z = 1

Combining A) and B)

z | N+1 => z = N+1 or z = 1, so by definition N+1 is prime

re .8
    
    >Yes. This is called Wilson's theorem, which is actually more general:
    >	If *and only if* N+1 is prime, then N!+1 is divisible by N+1.

Let p = N+1 and suppose that p is prime.

Consider (p-1)! (mod p)

(p-1)! = (2*...*(p-2))*(p-1)

For p=2 or p=3, (2*...*(p-2)) is degenerate, otherwise for p prime, p > 3,
and hence p odd, there are always an even number of 'terms' in (2*...*(p-2)).
I claim that in this case for p prime these 2k 'terms' can be paired off into
k pairs such that the product within each pair is 1 (mod p). This is easy but
tedious so I show it separately below. Thus (2*...*(p-2)) = 1 (mod p).

Therefore (p-1)! = p-1 (mod p)
so (p-1)! + 1 = 0 (mod p)
so p | (p-1)! + 1

i.e. N+1 | N!+1 when N+1 is prime

------------------------------------------
Let p be prime, I claim that for all x (1<=x<=p-1) there exists a unique y
(1<=y<=p-1) such that xy = 1 (mod p) and I claim that x� = 1 (mod p) =>
x = 1 or x = (p-1).

Let xy = xy' (mod p)
so p | xy-xy'
so p | x(y-y')
so p | x  or  p | y-y' (since p is prime)
but 1<=x<p so p | x is impossible
so p | y-y'
but 0<=y-y'<=p-2 so p | y-y' is impossible except for y-y'=0
so y=y'

Existence and Uniqueness:

Consider the p-1 products x.1, x.2, ..., x.(p-1) all mod p. By the previous
result these products must all be distinct. The possible values of the products
are the p values 0,...,p-1

But xy <> 0 (mod p) for any y, otherwise
xy = 0 (mod p)   =>   p | xy   =>   p | x  or  p | y which is not possible
since 1<=x<p and 1<=y<p

Thus the (p-1) products must all be distinct and drawn from the (p-1) values
1,...,p-1. Thus each value 1,...,p-1 occurs once and only once among the p-1
products. Thus one and only one of them is such that xy = 1 (mod p).

Proof of x� = 1 (mod p) => x = 1 or x = (p-1)

x� = 1 (mod p) => x� - 1 = 0 (mod p) => p | x� - 1 => p | (x-1)(x+1)
so p | x-1  or  p | x+1 (since p is prime)
As 1<=x<=p-1, 0<=x-1<=p-2 and 2<=x+1<=p
so  p | x-1 => x-1 = 0 i.e. x = 1
and p | x+1 => x+1 = p i.e. x = p-1
    
    (This statement is needed so that when we pair the 'terms' we know
     that none would pair with itself.)

    i'd like to know if this is a theory or a hypothesis ?
    
           PI(x) LOG(x)
          ------------- = 1 ,   when x grows very large
                x
    
    Where PI(x) is the number of primes not exceeding x.
    
    i wanted to know if we know the above is known to be true or is still 
    need to be proved?
    
    thanks,
    /nasser
            
    
    

    It looks right - there are some even sharper estimates on the
    distribution of primes that are amazingly accurate.  The simplest
    is a logarithmic integral (that I don't recall off the top of my head)
    but correction terms can be added to get an even better fit.  These
    go back to Gauss & Legendre, but were first proven in the late
    19'th century.  Riemann originated the most accurate estimates.

    The simplest proof I know of uses complex analysis, but there is an
    "Elementary" proof by Selberg.

    If you look in Hans Reisel's book on prime numbers he discusses
    these approximations, as well as some amazing algorithms that will
    actually *count* the primes within an interval and not just approximate
    their density.

    Selberg's proof is in Hua's book on number theory.  It's many pages...

    - Jim

I thought the "elementary" proof was by Selberg and Erdos.

I believe it was proven much earlier that if the limit
exists, then it must be one.  The harder part was showing
that the limit does indeed exist.  I don't remember who
gave the first (nonelementary) proof.

I *think* that "elementary" in this context means can be
done within first order Peano Arithmetic in the language
{0,successor,+,*}.

Dan

    .16
    
    Just in case someone looks for the book, his name is Riesel.