Conference rusure::math

    Re .0, problem 2
    
>>    Find the lowest degree polynomial which reduces identically
>>    mod 100, i.e. f(n) = 0 mod (100) for all n.  What about for
>>    the Gaussian integers?  The Eisenstein integers?
    
    I think the polynomial has to have degree >= one when the coefficients
    are reduced mod 100, i.e., 100n is not the answer.
    
    I know that Gaussian integers are complex numbers of the form
    a + bi where both a and b are integers.  What are Eisenstein
    integers?
    
    Dan

>>    Find the lowest degree polynomial which reduces identically
>>    mod 100, i.e. f(n) = 0 mod (100) for all n.

	f(n) = 10*n^5 - 10*n = 10 * lcm (n^5-n, n^2-n)

    The lowest degree is 5, as can be seen from trying to fit a 4th
    degree polynomial to f(n) = 0 (mod 5).

    A better solution would find the lowest degree polynomial with a
    leading coefficient of 1.

    Hint:  What property does at least one of the numbers n and n+1
    have?  What does this imply about the product n(n+1)?

     Re: .3

>>    Hint:  What property does at least one of the numbers n and n+1
>>    have?  What does this imply about the product n(n+1)?

     One of n and n+1 is even, so n(n+1) is even, and so 50n(n+1)
     is always divisible by 100 for integral n.  This gives a
     solution of degree 2.

     Re: .2

>>    A better solution would find the lowest degree polynomial with a
>>    leading coefficient of 1.

        5     2
      (n  - n)  is a monic polynomial of degree 10 which is
     divisible by 100 for every integral n.

     n^5 - n is always even [it is the difference between two
     numbers which are either both even or both odd] and is
     always divisible by 5 [Fermat's little theorem: p divides
     n^p - n for all integral n if p is prime].  So n^5 - n is
     always divisible by 10 [this is all straight from .2 so far]
     and its square is always divisible by 100.

     Dan

    Thanks for the corrections.  In fitting f(n) to a 4th degree equation,
    I made the following mistake a few times:

	18 * c1 = 0 (mod 100)   =>   c1 = 0 (mod 100)

(3)	Prove that there exists some positive K such that for all
	n, K*P(n)*P(n+1) >= (P(n+2))^2, where P(n) is the nth prime
	number.


	For any prime p, there is another prime q with p < q < 2*p.

	Thus, P(n+2) < 2*P(n+1) < 4*P(n), and

		P(n)*P(n+1) > (P(n+2)/4)*(P(n+2)/2) = (P(n+2))^2 / 8. 

	Therefore, K = 8 gives the desired result.

     Re: .0, Problem 1.

>>   Find limit (Product(n=1,int(x)) P(n) )^(1/x),
>>        x-->inf
>>
>>   where P(n) is the nth prime number.

     Let k = int(x).  Then the requested limit is equal to

          limit (Product(n=1,...,k) P(n))^(1/k)
          k-->inf

     i.e., using real x vs. integral k does not matter.  Anyway,

          P(1) = 2 >= 1
          P(2) = 3 >= 2
              ...
          P(n)     >= n for all integers n >= 1.

     So Product(n=1,...,k) P(n) >= Product(n=1,...,k) n = k!

     By Stirling's approximation,

          k! = (approx.) sqrt(2 * pi * k) * (k/e)^k

     So Product(n=1,...,k) P(n) >= (approx.) sqrt(2 * pi * k) * (k/e)^k

        Product(n=1,...,k) P(n) >= (k/e)^k      [at least for large k]

       (Product(n=1,...,k) P(n))^(1/k) >= k/e   [at least for large k]

     So (Product(n=1,...,int(x)) P(n))^(1/x) increases without
     bound as x increases without bound.

     Dan

                       -< What are Eisenstein integers? >-

    I believe they are numbers of the form n + w*m, where w is a
    primitive cube root of unity, that is a root of x^2+x+1 = 0,
    and n and m are integers.

    Gaussian integers have w a root of x^2+1 = 0.

    - Jim

     Problem 2, Gaussian integers version:

     Since we don't know a priori that Fermat's little theorem
     [if p is a prime and a is an integer, p divides a^p - a]
     applies to the Gaussian integers, and since 2 = (1+i)(1-i)
     and 5 = (2+i)(2-i) aren't Gaussian integer primes anyway,
     this one is a little harder.

     If x = a+bi, then x^2 = (a^2 - b^2) + 2abi, and x^2-x is not
     necessarily divisible by 2: x^2 - x = (a^2 - b^2 - a) + (2ab
     - b)i is not divisible by 2 if a is even and b is odd.  But
     I noticed that the imaginary part is even, and one of the
     real part or the real part minus one will be even, so that
     (x^2)(x^2 - 1) will always by divisible by 2.  [Remember these
     are Gaussian integers that I am talking about.]  Another way to
     do it is (x)(x - 1)(x - i)(x - 1 - i) because one of those
     four factors must be divisible by 2.

     So 50(x^2)(x^2 - 1) is a fourth degree polynomial that is
     always divisible by 100 when x is a Gaussian integer.

     Now for the monic polynomial part.  I fortunately noticed
     this about 5 [and in general any regular prime of the form
     4k+1]:

          (a + bi)^p - (a + bi) = (a^p - a) + (b^p - b)i + pM

     where pM is a sum of terms each containing a binomial
     coefficient that is divisible by p.  Note that since p=4k+1,
     i^p = i was used in the above.  So x^5 - x is always
     divisible by 5 among the Gaussian integers.  So a monic
     polynomial that is always divisible by 100 would be the
     square of the least common multiple of (x^2)(x^2 - 1) and
     (x^5 - x).  Since the first is x * x * (x^2 - 1) and the
     second is x * (x^2 - 1) * (x^2 + 1), this is

     [(x^2)(x^2 - 1)(x^2 + 1)]^2  = (x^6 - x^2)^2

     a monic polynomial of degree 12 that always divisible by 100
     when x is a Gaussian integer.

     Is there room for improvement here?  My lcm of a 4th-degree
     and a 5th-degree polynomial went up in degree to six.  Can
     that extra degree be removed, or must a totally different
     approach be taken?

     Dan