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