# [seqfan] Re: On equivalence of congruences

jean-paul allouche jean-paul.allouche at imj-prg.fr
Sun Jul 29 21:11:03 CEST 2018

Hi here is a brief sketch of a proof which (I hope) would work.

First k^{p-1} == 1 if n not == 0 mod p and 0 otherwise.
Hence the sum 1^{p-1} + ... + n^{p-1} is congruent to
n - [n/p] mod p (here [x] stands for the integer part of x).
Thus the sum is congruent to n mod p if and only if [n/p]
is zero mod p. This is easily shown to be equivalent to
there exists a \geq 0 and r \in [0,p-1] such that n = a p^2 + r.

Now binomial(n+p,p) = (n+1)(n+2)...(n+p)/p!
Let j be the integer in [1,p] such that n+j is divisible by p.
Then binomial(n+p,p) = \prod_{k /= j} (n+k) . (n+j)/(p(p-1)!)
== - \prod_{k /= j} (n+k) ((n+j)/p) mod p (use Wilson).
I think that the product is also -1 mod p (kind of Wilson).
So that binom(n+p,p) ==1 mod p if and only if (n+j)/p is
congruent to 1 mod p, which is equivalent to saying that the
remainder of the division of n by p^2 belongs to [0, p-1].

Is this convincing?
best
jp

Le 28/07/2018 à 08:17, Tomasz Ordowski a écrit :
> Dear SeqFan,
>
> Conjecture:
>
> For a prime p;
> 1^(p-1)+2^(p-1)+...+n^(p-1) == n (mod p)
> if and only if
> binomial(n+p,p) == 1 (mod p).
>
> I am asking for proof or counterexample.
>
> Cf. https://oeis.org/A133907
>
> ? a(n) is the smallest prime p such that
> 1^(p-1)+2^(p-1)+...+n^(p-1) == n (mod p).
>
> Best regards,
>
> Thomas
> _________
> For n = p-1, binomial(2p-1,p) == 1 (mod p^3) with p>3.
>
> https://en.wikipedia.org/wiki/Wolstenholme%27s_theorem
>
> https://en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture
>
>
>
>