From: kevin2003@delphi.com (Kevin Brown)
Newsgroups: sci.math
Subject: Re: Number Theory Problem
Date: 21 Aug 1994 07:13:43 GMT
LK = Logan J. Kleinwaks
LK> Here's the problem: Prove the sum of k! from k=0 to p-1 is not
LK> congruent to 0 mod p for all positive odd primes p.
JS = Jonathan Stadler
JS> I haven't given this too much thought, but the first thing that
JS> came to my mind is... for example
JS> 0! + 1! + 2! + 3! + 4! + 5! + 6!=
JS> 1 + (1 + 2(1 + 3(1 + 4(1 + 5(1 + 6)))))
RS=Robert D. Silverman
RS> Hint:
RS> p-1! + p-2! + p-3! + ... 0! =
RS>
RS> p!(1/p) + p!(1/(p(p-1))) + p!(1/(p(p-1)(p-2)) + .... =
RS>
RS> p!(1/p) [1 + 1/(p-1) + 1/(p-1)(p-2) + .....]
RS>
RS> Now look at the proof for Wolstenholme's Theorem.
KF = Kurt Foster
KF> I confess I don't see it. Wolstenholme's Theorem is that sum(1/k),
KF> k = 1 to p-1, is p times a p-integer for all odd primes p, and
KF> p^2 times a p-integer for odd primes >= 5. Now sum(k!), k = 1 to p-1
KF> (mod p) is 0 for p = 3, 3 for p = 5, and 5 for p = 7. It is 0 for
KF> p = 11 and 13, but not for p = 17.
KF>
KF> Another possible approach is to consider the polynomial
KF>
KF> f(p;x) = x + 1!x^2 + 2!x^3 +...+ (p-1)!x^p
KF>
KF> over the field of p elements. One has x + x^2 * f'(p;x) = f(x).
KF> The question can be cast as follows. Let
KF>
KF> F(p;x) = x + 1!x^2 + 2!x^3 + ad infinitum,
KF>
KF> in the p-adic rationals, the completion of the algebraic closure, or
KF> some algebraic extension of the completion of the p-adic rationals.
KF> Then the series for F(p;x) converges for |x|_p =< 1 (in fact <
KF> p^(1/(p-1))) (p-adic valuation). The original question then is
KF> equivalent to showing that F(p;1) is a p-adic unit for every odd
KF> prime p.
EC = Edwin Clark
EC> I don't see how to settle your problem. But I think it has a very good
EC> chance of being true. In fact, consider the following:
EC>
EC> Conjecture: For "most" functions f: {0,1,2,. . . } -> {0,1,2,. . . }.
EC> there exists a number N(f) such that if n > N(f) then
EC> f(0) + f(1) + . . . + f(n-1) mod n is not equal to 0.
EC>
EC> "Proof": for a random sequence f(0), f(1), . . . , f(n-1) the
EC> probability of
EC> f(0) + f(1) + . . . + f(n-1) being 0 mod n is 1/n.
EC>
EC> Moral: for a given function that is the least bit random, say
EC> f(k) = k!, numerical computations will very likely support the
EC> conjecture.
LP = Laura Helen
LP> Does the silence mean that no-one has a proof, or does someone have a
LP> proof and is being quiet? I tried for primes up to 300,000 with no
LP> counterexamples.
I suspect no one has a proof. For any integer n the "left factorial
function" is defined as !n = 0!+1!+2!+...+(n-1)!. The conjecture
that n does not divide !n for any n>2 was listed as B44 in R. Guy's
"Unsolved Problems in Number Theory" back in 1981. Note that the
conjecture is for all integers n, not just primes.
There is an even stronger conjecture, that the greatest common divisor of
!n and n! is 2. Wagstaff verified this for all n < 50000.
Wagstaff also noted that !n - 1 is divisible by 3 for n>2, by 9 for n>5,
and by 99 for n>10.
There's also a conjecture on the sums of the first k factorials with
alternating signs (whether such a sum is a prime infinitely often).
There are lots of interesting properties about factorials, especially
modulo primes. For example, (k-1)! times (p-k)! is congruent to (-1)^k,
so the terms of !p come in "inverse pairs". But this doesn't seem to
help settle the problem.
I wonder if [!n (mod n)]/n would make a good generator of "random numbers"
from 0 to 1.
==============================================================================
From: laurahel@news.delphi.com (LAURAHELEN@DELPHI.COM)
Newsgroups: sci.math
Subject: Re: Number Theory Problem
Date: 21 Aug 1994 15:43:47 -0000
The original question:
Is 0! + 1! + ... + (p-1)! divisible by p, for p any odd prime?
kevin2003@delphi.com (Kevin Brown) writes:
>I suspect no one has a proof. For any integer n the "left factorial
>function" is defined as !n = 0!+1!+2!+...+(n-1)!. The conjecture
>that n does not divide !n for any n>2 was listed as B44 in R. Guy's
>"Unsolved Problems in Number Theory" back in 1981. Note that the
>conjecture is for all integers n, not just primes.
yes, that's equivalent to the conjecture about just primes.
>There is an even stronger conjecture, that the greatest common divisor of
>!n and n! is 2. Wagstaff verified this for all n < 50000.
I conjectured (which was uncomfortable before breakfast) that for n>3,
!n/2 has no divisors .le. n. true up to n=17. This looks the same
as the conjecture you mentioned, but I think it's equivalent to saying,
!p is not divisible by p, for p an odd prime.
Suppose you know that !p is not 0 mod p for any odd prime. Prove that
for n > 3, !n/2 has no factors .le. n. It's true for n = 4. Suppose true
for some n>4.
!(n+1)/2 = !n/2 + n!/2
n!/2 = 0 mod k, k = 2,3,...,n
By induction !n/2 is not 0 mod k, k = 2,3,...,n
So !(n+1)/2 is not 0 mod k for k = 2,3,...,n.
It remains to show that !(n+1)/2 is not divisible by n+1. If n+1
is non-prime then we already showed it. If n+1 is a prime then by the
conjecture !(n+1) is not 0 mod n+1, so !(n+1)/2 is not 0 mod n+1.
So that would prove it.
Laura
==============================================================================
From: kfoster@rmii.com (Kurt Foster)
Newsgroups: sci.math
Subject: Re: Number Theory Problem
Date: 21 Aug 1994 19:06:51 GMT
Kevin Brown (kevin2003@delphi.com) wrote:
: LP = Laura Helen
: LP> Does the silence mean that no-one has a proof, or does someone have a
: LP> proof and is being quiet? I tried for primes up to 300,000 with no
: LP> counterexamples.
: I suspect no one has a proof. For any integer n the "left factorial
: function" is defined as !n = 0!+1!+2!+...+(n-1)!. The conjecture
: that n does not divide !n for any n>2 was listed as B44 in R. Guy's
: "Unsolved Problems in Number Theory" back in 1981. Note that the
: conjecture is for all integers n, not just primes.
: There is an even stronger conjecture, that the greatest common divisor of
: !n and n! is 2. Wagstaff verified this for all n < 50000.
It is almost trivial to observe that !n is congruent to 2 mod 8 when
n > 3, and that !n is congruent to !p mod p for every prime p =< n. Thus
the greatest common factor of n! and !n is 2, provided p does not divide
!p for any odd p =< n. If the bound 50000 in the above is correct, then
Lisa Helen has superseded Professor Wagstaff's result.
The p-adic formulation involving
f(p;x) = sum( (k-1)!*x^k), k = positive integer
gives a restatement involving a p-adic function satisfying a simple
differential equation, x + x^2 * f'(p;x) = f(p;x), and f'(0) = 1. The
idea of this was to provide another set of clubs to hit the problem with.
==============================================================================
From: kfoster@rmii.com (Kurt Foster)
Newsgroups: sci.math
Subject: Re: Number Theory Problem
Date: 21 Aug 1994 19:11:15 GMT
Kurt Foster (kfoster@rmii.com) wrote:
: If the bound 50000 in the above is correct, then
: Lisa Helen has superseded Professor Wagstaff's result.
^^^^
Forgive me, Laura!
==============================================================================
From: gerry@macadam.mpce.mq.edu.au (Gerry Myerson)
Newsgroups: sci.math
Subject: Re: Number Theory Problem
Date: 21 Aug 1994 20:10:59 -0500
In article <9408210312591.kevin2003.DLITE@delphi.com>, kevin2003@delphi.com
(Kevin Brown) wrote:
=>
=> I suspect no one has a proof. For any integer n the "left factorial
=> function" is defined as !n = 0!+1!+2!+...+(n-1)!. The conjecture
=> that n does not divide !n for any n>2 was listed as B44 in R. Guy's
=> "Unsolved Problems in Number Theory" back in 1981. Note that the
=> conjecture is for all integers n, not just primes.
A more recent reference is Z. Mijajlovic, On some formulas involving !n
and the verification of the !n-hypothesis by use of computers, Publ.
Inst. Math. (Beograd) (N. S.) 47 (61) (1990) 24--32; MR 92d:11134.
In a draft copy of the 2nd edition of Guy's book, he says, "In a
91-03-21 letter, Reg. Bond offers an as yet unpublished proof of the
conjecture."
Gerry Myerson