# Remarks on an interpolation between Wilson's theorem and Giuga's conjecture

Thomas Sauvaget

► To cite this version:

Thomas Sauvaget. Remarks on an interpolation between Wilson's theorem and Giuga's conjecture. 2019. hal-02373255v3

HAL Id: hal-02373255

https://hal.science/hal-02373255v3

Preprint submitted on 13 Mar 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
REMARKS ON AN INTERPOLATION BETWEEN WILSON'S
THEOREM AND GIUGA'S CONJECTURE

THOMAS SAUVAGET

ABSTRACT. A family of congruences interpolating between those of Wilson and Giuga is constructed. Several elementary results are presented, in order to present a possible approach to establishing Giuga's conjecture.

# 1. INTRODUCTION

Let $p$ be a prime, and $j$ a positive integer such that $1 \le j \le p-1$. Then
by Fermat's Little Theorem we have $j^{p-1} \equiv 1 \pmod p$. And thus $\sum_{j=1}^{p-1} j^{p-1} \equiv p-1 \equiv -1 \pmod p$, an observation of Sierpiński [7].

In 1950, Giuga [5] asked whether the converse holds, i.e. if any integer $n$ such that $\sum_{j=1}^{n-1} j^{n-1} \equiv -1 \pmod n$ is necessarily prime. He provided support for that conjecture by showing that any counterexample, i.e. any composite integer satisfying the congruence, is greater than $10^{1000}$. This lower bound was later improved many times over the ensuing decades, by numerical means : to $10^{1700}$ by Bedocchi [2], to $10^{13887}$ by Borwein, Borwein, Borwein & Girgensohn [3], and finally to $10^{19908}$ by Borwein, Maitland & Skerritt [4]. These works nevertheless have arithmetical limitations, in that the method used intrinsically cannot treat any number having more than 8,135 prime factors.

On the other hand, Tipu [13] proved by analytic means that for any real number $x$, the number of counterexamples to Giuga's conjecture $G(x) := \#\{n < x : n$ is composite and $\sum_{a=1}^{n-1} a^{n-1} \equiv -1 \pmod n\}$, if any, is at best of moderate growth: $G(x) \ll \sqrt{x} \log x$. This was later improved by Luca, Pomerance and Shparlinski [9] to $G(x) = o(\sqrt{x})$.

Agoh [1] showed in 1995 that conjecturing that $n$ is prime iff $nB_{n-1} \equiv -1 \pmod n$ (where the $(B_n)_{n \ge 0}$ are Bernoulli numbers, see e.g. Granville [6] and Sun [12]) is equivalent to Giuga's conjecture (see also Kellner [8]).

The paper is organized as follows. In the next section, we introduce a family of congruences that interpolates between Wilson's and Giuga's, and prove an important lemma. Then, in section 3, we show that the family of congruences can be rewritten using unsigned Stirling numbers of the first kind. Properties of those numbers observed numerically, combined with the important lemma, would then imply that odd squarefree composite integers cannot satisfy Giuga's congruence.

<footnote n="2010">2010 Mathematics Subject Classification. 11A41, 11A07.</footnote>

<footnote>Key words and phrases. Giuga's conjecture; primality.</footnote>

<footnote>This version of the manuscript takes into account helpful comments and encouragements pro-
vided by several referees of previous versions, to whom the author is very grateful. The author
also wishes to thank all those who contributed, directly or indirectly, to make Sage and its libraries
such a useful free software.</footnote>
Also, in an appendix, we present a combinatorial relation which might be of inde-
pendent interest (which arised in an earlier incorrect attempt at proving Giuga's
conjecture).

**Notations.** Let $\mathbb{N}_2 := \mathbb{N} - \{0,1\}$. The set of primes is denoted by $\mathcal{P} := \{2,3,5,7,11,\dots\}$. The double-brackets denote sets of consecutive integers: $\llbracket a;b \rrbracket := \{i \in \mathbb{N} | a \le i \le b\}$. Define also for each $k \in \mathbb{N}$ the functions $S_k : \mathbb{N} \to \mathbb{N}$ by $S_k(n) := \sum_{j=1}^{n-1} j^k$.

2. AN INTERPOLATION OF WILSON’S AND GIUGA’S CONGRUENCES

2.1. Basic definitions.

**Definition 2.1.** Let $f_W : \mathbb{N}_2 \mapsto \mathbb{N}$ be defined by $f_W(n) := 1 + (n-1)!$

Then Wilson's theorem can be recast as:

**Theorem 1.** $\forall n \in \mathbb{N}_2$ we have: $n \in \mathcal{P} \Leftrightarrow n \mid f_W(n)$.

**Remark 1.** Wilson's theorem allows to change the definition of primality, which is negative in nature (n is prime iff it is not the product of strictly smaller integers), into a positive one (n is prime iff it divides some specific larger integer). This crucial reversal is at the heart of the philosophy of this paper.

**Definition 2.2.** Let $f_G : \mathbb{N}_2 \mapsto \mathbb{N}$ be defined by $f_G(n) := 1 + S_{n-1}(n)$.

Then Giuga's conjecture is:

**Conjecture 1.** $\forall n \in \mathbb{N}_2$ we have: $n \in \mathcal{P} \Leftrightarrow n \mid f_G(n)$.

2.2. **An interpolation family.** We introduce the following integer-valued func-
tions.

**Definition 2.3.** Let $H_k : \mathbb{N}_2 \mapsto \mathbb{N}$ be defined by $H_k(n) := 1 + \sum_{i=1}^{n-1} \frac{(n+i-1-k)!}{i!} i^k$ for $k \in \llbracket 1; n-1 \rrbracket$

**Remark 2.** For any given $n \in \mathbb{N}_2$, we have that for any $k \in \llbracket 1; n-1 \rrbracket$ the function $H_k$ is integer-valued, since for each $i \in \llbracket 1; n-1 \rrbracket$ we have $i \le n + i - 1 - k$.

**Remark 3.** We directly obtain $H_{n-1} = f_G$. The relationship between $H_1$ and $f_W$ is described in the proof of the next lemma.

**Lemma 1.** $\forall n \in \mathbb{N}_2$ we have: $n \in \mathcal{P} \Leftrightarrow n \mid H_1(n)$.

*Proof.* Since by definition $H_1(n) = 1 + (n-1)! + \frac{n!}{2!} 2 + \frac{(n+1)!}{3!} 3 + \cdots + \frac{(2n-3)!}{(n-1)!} (n-1) = 1 + (n-1)! + n \left[ \frac{(n-1)!}{2!} 2 + \frac{(n+1)!}{3! n} 3 + \cdots + \frac{(2n-3)!}{(n)!} (n-1) \right] = 1 + (n-1)! \equiv f_W(n) \pmod{n}$. The term in the bracket is necessarily an integer since for any $j \in \llbracket 1, n-3 \rrbracket$ we have that $(n+j)! = \underbrace{1 \times 2 \times \cdots \times (j+2)}_{=(j+2)!} \times (j+3) \times \cdots \times n \times (n+1) \times \cdots \times (n+j),$

so this is simultaneously divisible by $(j+2)!$ and by $n$. The result then follows from
Wilson's theorem.
$\square$

Thus $H_1$ also characterizes the primes. To motivate the strategy employed in the
next sections, consider the residues of the values of $H_k(n)$ modulo $n$, for $k \in \llbracket 1; 34 \rrbracket$
and $n \in \llbracket 5; 35 \rrbracket$, which are provided in the following table:
REMARKS ON AN INTERPOLATION BETWEEN WILSON'S THEOREM AND GIUGA'S CONJECTURE

<figure><img src="image_2.png" /><figcaption>FIGURE 1. Residues of the values of $H_k(n)$ modulo $n$.</figcaption></figure>

On this very limited data set, the following observations can be made:

* for any $k \in [1; n-1]$, $H_k(n) \equiv 0 \pmod{n}$ for all $n$ prime

* for any $k \in [1; n-1]$, $H_k(n) \not\equiv 0 \pmod{n}$ for any composite $n$

* in the case $n$ composite, $H_k(n) \equiv 1 \pmod{n}$ for $k \le \frac{n}{2}$

The last point can be easily established beyond $n = 35$ for squarefree composites by the following lemma:

**Lemma 2.** Let $n \in \mathbb{N}_2$ be composite and squarefree. Then $H_k(n) \equiv 1 \pmod{n}$ for $k \le \frac{n}{2}$.

*Proof.* Given $n$ composite, let its prime factorization be $n = \prod_{j=1}^J q_j$, where $q_1 < \dots < q_J$ are distinct primes. We necessarily have that $2 \le q_1 < \dots < q_J \le \frac{n}{2}$.

Let $k \in [1; \lfloor \frac{n}{2} \rfloor]$. So, for each $i \in [1; n-1]$ we have $n+i-1-k \ge \lfloor \frac{n}{2} \rfloor + i-1 \ge q_J + i-1 \ge q_J > \dots > q_1$ ($\diamond$).

Recall the definition of $H_k(n)$. Since $\frac{(n+i-1-k)!}{i!}$ is a product of $n+i-1-k$ consecutive integers starting at $i+1$, each term $\frac{(n+i-1-k)!}{i!}i^k$ contains a product of $n+i-k$ consecutive integers starting at $i$.

So, given the inequalities ($\diamond$), we infer that for each $i \in [1; n-1]$, each of the $q_j$ is a factor of at least one of those consecutive integers, hence each term $\frac{(n+i-1-k)!}{i!}i^k$ is a multiple of $n$. So only the first term 1 in $H_k(n)$ remains modulo $n$. $\square$

Going beyond $k = \lfloor \frac{n}{2} \rfloor$ would require a more detailed analysis of the structure of those values of $H_k(n)$. But, given the first and second observations, it appears more straightforward, to make the following conjecture: it captures the primality condition (no composite is a false positive), while not entering into the arithmetical details of the values of the residues for $n$ composite.

**Conjecture 2.** For each $k \in \mathbb{N}_2$ we have: $[n \in \mathcal{P}, \text{ with } n \ge k+1] \Leftrightarrow n \mid H_k(n)$.

**Remark 4.** The case $k = n-1$ is Giuga's conjecture.

In the next section, we show how lemma 2 could make it impossible for odd squarefree composite integers to satisfy Giuga's congruence.
### 3. TOWARDS A PATH FOR THE PROOF OF GIUGA'S CONJECTURE

**3.1. The case of $n = p$ prime of conjecture 2.** We start with the following elementary lemma, whose proof is taken almost verbatim from Nicolas [10].

**Lemma 3.** Let $p$ be an odd prime. Then for any $k \in \mathbb{N}^*$ such that $\gcd(p-1, k) = 1$ we have $S_k(p) \equiv 0 \pmod{p}$.

*Proof.* Let $b$ be any number relatively prime to $p$. Recall that the numbers $b, 2b, 3b, 4b, \dots, (p-1)b$ are a reduced residue class modulo $p$.

It follows that $b^k + (2b)^k + (3b)^k + \dots + ((p-1)b)^k \equiv 1^k + 2^k + 3^k + \dots + (p-1)^k \pmod{p}$ ($\ast$). But $(ib)^k = b^k i^k$, so we can rewrite ($\ast$) as $(b^k - 1)(1^k + 2^k + 3^k + \dots + (p-1)^k) \equiv 0 \pmod{p}$ ($\ast\ast$).

Let $b$ have order $p-1$ modulo $p$. So we are letting $b$ be a primitive root of $p$. Since $p-1$ does not divide $k$, we have $b^k \not\equiv 1 \pmod{p}$. Then it follows from ($\ast$) that $1^k + 2^k + 3^k + \dots + (p-1)^k \equiv 0 \pmod{p}$. $\square$

Recall the following classical definitions.

**Definition 3.1.** The unsigned Stirling numbers of the first kind, $\begin{bmatrix} M \\ j \end{bmatrix}$, are the coefficients of the expansion of the rising factorial into powers: $\prod_{j=0}^{j=M-1} (x+j) = \sum_{j=0}^{j=M} \begin{bmatrix} M \\ j \end{bmatrix} x^j$. The Stirling numbers of the first kind, $s(M, j)$, are the coefficients of the expansion of the falling factorial into powers: $\prod_{j=0}^{j=M-1} (x-j) = \sum_{j=0}^{j=M} s(M, j)x^j$. We have $|s(M, j)| = \begin{bmatrix} M \\ j \end{bmatrix}$.

We can use this and lemma 3 to prove the following result, which is one direction of conjecture 2.

**Theorem 2.** For all odd prime $p$, and all $k \in [1; p-2]$ we have $H_k(p) \equiv 0 \pmod{p}$.

*Proof.* Indeed, for any $n$, prime or composite, we can expand $H_k(n)$ as function of $H_{n-1}(n)$, and $\{S_k(n), \dots, S_{n-2}(n)\}$, and $\{\begin{bmatrix} n-k \\ 1 \end{bmatrix}, \dots, \begin{bmatrix} n-k \\ n-k-1 \end{bmatrix}\}$:

$$ 
\begin{align*}
H_k(n) &= 1 + \sum_{i=1}^{n-1} \frac{(n+i-1-k)!}{i!} i^k \\
&= 1 + \sum_{i=1}^{n-1} (n+i-1-k)(n+i-2-k)\dots(1+i)i^k \\
&= 1 + \sum_{i=1}^{n-1} \left( \sum_{j=0}^{n-k} \begin{bmatrix} n-k \\ j \end{bmatrix} i^j \right) i^{k-1} \\
&= 1 + \sum_{i=1}^{n-1} \left( \begin{bmatrix} n-k \\ 0 \end{bmatrix} i^{k-1} + \dots + \begin{bmatrix} n-k \\ n-k \end{bmatrix} i^{n-1} \right)
\end{align*}
$$

This can be rearranged as:

$$ H_k(n) = H_{n-1}(n) + \begin{bmatrix} n-k \\ n-k-1 \end{bmatrix} S_{n-2}(n) + \dots + \begin{bmatrix} n-k \\ 1 \end{bmatrix} S_k(n) $$

$$ \text{since } \begin{bmatrix} n-k \\ 0 \end{bmatrix} = 0 \text{ and } \begin{bmatrix} n-k \\ n-k \end{bmatrix} = 1. $$

Now, for $n = p$ prime we mentioned at the beginning of this paper that $H_{p-1}(p) \equiv 0 \pmod{p}$. Combining this with lemma 3 finishes the proof. $\square$

We shall not attempt to prove conjecture 2 in this work. Let us only mention the following simpler conjecture based on numerical data.
**Conjecture 3.** For any odd squarefree composite $n = q_1 \cdots q_J$, one has $H_{n-q_j+1}(n) \equiv n+1 - q_1 \pmod{n}$.

**Remark 5.** This would be, for odd squarefree composites, the first "non-trivial value of $k$" i.e. for these $n$ one could show like in lemma 2 that $H_k(n) \equiv 1 \pmod{n}$ for $k < n - q_J + 1$, while for $k = n - q_J + 1$ one would have $H_k(n)$ different from either 0 or 1 modulo $n$.

**3.2. Steps towards Giuga's conjecture.** Recall from [3] that even, and non-squarefree, composite integers cannot satisfy Giuga's congruence. So in this section we consider only the case of odd squarefree integers, i.e. $n = q_1 \cdots q_J$ with $3 \le q_1 < \cdots < q_J \le \frac{n}{3}$.

The following elementary lemma allows to reduce the problem to the prime factors of $n$.

**Lemma 4.** Let $n = q_1 \cdots q_J$ be odd composite squarefree. Then for any number $M$ we have the equivalence:

$$M \equiv 0 \pmod{q_1 \cdots q_J} \iff \left\{ \begin{array}{ll} M \equiv 0 \pmod{q_1} \\ \vdots \\ M \equiv 0 \pmod{q_J} \end{array} \right.$$

*Proof.* This follows immediately by the Chinese Remainder Theorem. $\square$

We can apply this lemma in two special cases. Firstly, the condition $H_k(n) \equiv 0 \pmod{n}$ is equivalent to having

$$\left\{ \begin{array}{ll} H_k(n) \equiv 0 \pmod{q_1} \\ \vdots \\ H_k(n) \equiv 0 \pmod{q_J} \end{array} \right.$$

So to show $H_k(n) \neq 0 \pmod{n}$ it would suffice to show that for at least one $q_j$ we have $H_k(n) \neq 0 \pmod{q_j}$.

Secondly, the condition $H_k(n) \equiv 1 \pmod{n}$ is equivalent to having

$$\left\{ \begin{array}{ll} H_k(n) \equiv 1 \pmod{q_1} \\ \vdots \\ H_k(n) \equiv 1 \pmod{q_J} \end{array} \right.$$

So to show $H_k(n) \neq 1 \pmod{n}$ it would suffice to show that for at least one $q_j$ we have $H_k(n) \neq 1 \pmod{q_j}$.

Recall the following result on congruences for unsigned Stirling numbers of the first kind, which we take verbatim from Scott [11].

**Lemma 5.** $p$ is prime $\iff$ for all $k \in [2; p-1]$ we have $\begin{bmatrix} p \\ k \end{bmatrix} \equiv 0 \pmod{p}$.

*Proof.* Work in the polynomial ring $(\mathbb{Z}/p\mathbb{Z})[x]:$ in that ring $\prod_{i=0}^{p-1}(x-i) = x^p - x$, since both polynomials are monic of degree $p$ and have roots $0, \dots, p-1$.

Now just equate the coefficients to get the positive part of the result. For the negative result, suppose that $n$ is not prime, let $p$ be a prime dividing $n$, and let $m = \frac{n}{p}$. Then
$$ \prod_{i=0}^{n-1} (x-i) = \prod_{k=0}^{m-1} \prod_{\ell=0}^{p-1} (x-k\ell-p-\ell) = \prod_{k=0}^{m-1} \prod_{\ell=0}^{p-1} (x-\ell) = \left(\prod_{\ell=0}^{p-1} (x-\ell)\right)^m = (x^p-x)^m = x^m(x^{p-1}-1)^m $$

and it follows that $s(n, m) \equiv (-1)^m \not\equiv 0 \pmod{p}$. Since $\begin{bmatrix} n \\ m \end{bmatrix} = |s(n, m)|$ the claim follows. $\square$

The general expansion of theorem 2:

$$ H_k(n) = H_{n-1}(n) + \begin{bmatrix} n-k \\ n-k-1 \end{bmatrix} S_{n-2}(n) + \cdots + \begin{bmatrix} n-k \\ 1 \end{bmatrix} S_k(n) $$

becomes for $k = q_j$:

$$ H_{q_j}(n) = H_{n-1}(n) + \begin{bmatrix} n-q_j \\ n-q_j-1 \end{bmatrix} S_{n-2}(n) + \cdots + \begin{bmatrix} n-q_j \\ 1 \end{bmatrix} S_{q_j}(n) $$

So if we assume that $H_{n-1}(n) \equiv 0 \pmod{n}$, which implies $H_{n-1}(n) \equiv 0 \pmod{q_j}$, and combine this with our observation of section 1 that $H_k(n) \equiv 1 \pmod{n}$ for $k \le \frac{n}{3}$ (since $n$ is odd), so in particular $H_{q_j}(n) \equiv 1 \pmod{q_j}$, we get:

$$ 1 \equiv \begin{bmatrix} n-q_j \\ n-q_j-1 \end{bmatrix} S_{n-2}(n) + \cdots + \begin{bmatrix} n-q_j \\ 1 \end{bmatrix} S_{q_j}(n) \pmod{q_j} $$

**Remark 6.** Numerically, we observe that for the largest prime factor $q_K$ we always seem to have $\begin{bmatrix} n-q_K \\ n-q_K-1 \end{bmatrix} S_{n-2}(n) + \cdots + \begin{bmatrix} n-q_K \\ 1 \end{bmatrix} S_{q_K}(n) \equiv 0 \pmod{q_K}$. If one could prove this, a contradiction would follow, hence one would conclude that one cannot have $H_{n-1}(n) \equiv 0 \pmod{n}$, i.e. Giuga's conjecture is true. But the precise way in which that cancellation occurs modulo $q_K$ seems non-trivial, in particular most of the time several terms are non-zero. Note also that we cannot use lemma 5, at least not directly, since we are dealing with the composite $n-q_K$.

# 4. APPENDIX

In this appendix we present an earlier incorrect attempt of the author, stressing where the error lies. The author is very grateful for the input from multiple referees to finally help him understand the problem.

## 4.1. General properties.

**Lemma 6.** For each $(n, k) \in \mathbb{N}_2^2$ with $n \ge k + 1$, we have : $H_k(n) < H_{k-1}(n)$.

*Proof.* With those $n$ and $k$, since $\forall i \in \lfloor 1; n-1 \rfloor$ we have $\frac{(n+i-1-k)!}{i!}i^k = \frac{i}{n+i-1-k} \times \frac{(n+i-k)!}{i!}i^{k-1}$, we thus explicitely have $H_k(n) = 1 + \sum_{i=1}^{n-1} \frac{(n+i-1-k)!}{i!}i^k < 1 + \sum_{i=1}^{n-1} \frac{(n+i-k)!}{i!}i^{k-1} = H_{k-1}(n)$ $\square$

**Lemma 7.** For each $(n, k) \in \mathbb{N}_2^2$ with $n \ge k + 1$ we have :

$$ H_k(n) \equiv 1 + \sum_{i=1}^{k} \frac{(n+i-1-k)!}{i!} i^k \pmod{n} $$

*Proof.* Immediate. $\square$
4.2. **Passage from $H_k$ to $H_{k+1}$.** The following result can be established.

**Lemma 8.** For each $n \in \mathbb{N}_2$ and any $1 \le k \le n-2$ we have :

$$H_{k+1}(n) = H_k(n) - (n-k-1) \sum_{i=1}^{n-1} \frac{(n+i-2-k)!}{i!} i^k$$

*Proof.* We have $H_{k+1}(n) = 1 + \sum_{i=1}^{n-1} \frac{(n+i-(k+1)-1)!}{i!} i^{k+1} = 1 + \sum_{i=1}^{n-1} \frac{i}{n+i-k-1} \frac{(n+i-k-1)!}{i!} i^k$, so adding and subtracting $\sum_{i=1}^{n-1} \frac{n-k-1}{n+i-k-1} \frac{(n+i-k-1)!}{i!} i^k$ to that, one obtains the result. $\square$

The following functions will be useful.

**Definition 4.1.** Let $U_k : \mathbb{N}_2 \to \mathbb{N}$ be defined by

$$U_k(n) := \sum_{i=1}^{k+1} \frac{(n+i-2-k)!}{i!} i^k \quad \text{if } k \in [1; n-2]$$

**Remark 7.** For any given $n \in \mathbb{N}_2$ we have that for any $k \in [1; n-2]$ the quantity $U_k(n)$ is an integer, since for any $i \in [1; k+1]$ we have $i \le n+i-2-k$.

**Remark 8.** Since $\frac{(n+i-2-k)!}{i!} \equiv 0 \pmod{n}$ for $i \in [k+2; n-1]$, we have $H_{k+1}(n) - H_k(n) \equiv (k+1)U_k(n) \pmod{n}$.

**Lemma 9.** For any $n \in \mathbb{N}_2$ we have $U_1(n) \equiv 0 \pmod{n}$. In particular, $H_2$ also characterizes $\mathcal{P}$.

*Proof.* We have to show that for $n \ge 2$ we have $\frac{(n-2)!}{1!} 1^1 + \frac{(n-1)!}{2!} 2^1 \equiv 0 \pmod{n}$. This is true since it simplifies to showing $(n-2)! + (n-1)! \equiv 0 \pmod{n}$, i.e. showing that $(n-2)![1+(n-1)] \equiv 0 \pmod{n}$, which is true. So for $n \ge 2$ we have $H_2(n) \equiv H_1(n) \pmod{n}$, so lemma 1 implies that $H_2$ also characterizes the primes. $\square$

4.3. **A combinatorial relationship.** Let us now introduce the following sums.

**Definition 4.2.** For each $k \in \mathbb{N}^*$ let

$$V_k := \sum_{i=1}^{k} \left[ (-1)^{i-1} \binom{k+1}{i} i^k + (-1)^k \binom{k}{i} i^k \right]$$

**Theorem 3.** For each $k \in \mathbb{N}^*$ we have $V_k = (-1)^{k+1}$.

This will be proved as a result of the following two lemmas. The author is very grateful to the referee of a previous version of this work for providing this proof. This result might be of independent interest.

**Lemma 10.** For each $k \in \mathbb{N}^*$ we have $\sum_{i=0}^{k} \binom{k}{i} k^i = (k+1)^k$.

*Proof.* This follows immediately from the binomial theorem. $\square$

**Lemma 11.** For each $k \in \mathbb{N}^*$ we have $\sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i} i^k = 0$.

*Proof.* Defining for any function $f: \mathbb{Z} \to \mathbb{Z}$ the forward difference operator $\Delta$ by $\Delta f(j) := f(j+1) - f(j)$, we obtain by induction on $n$ that the $n$-fold iteration of $\Delta$ on $f$ is $\Delta^n f(j) = \sum_{i=0}^{n} (-1)^i \binom{n}{i} f(j+n-i)$.

For $n = k+1$ and the polynomial $f(j) = j^k$, since $f$ is of degree $k < n$ we thus have that $\Delta^n f(j)$ is identically zero. That is, we have $\sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i} (j+k+1-i)^k = 0$.
In particular, when evaluated at $j = -(k+1)$ this gives $\sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i} (-i)^k = (-1)^k \sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i} i^k = 0$, hence the result. $\square$

We now prove theorem 3. Let

$$A := \sum_{i=1}^{k} \binom{k}{i} k^i$$

and

$$B := \sum_{i=1}^{k} (-1)^i \binom{k+1}{i} i^k$$

Then, given the slightly different summation ranges than in the previous lemmas, we get $A = (k+1)^k - 1$ and $B = (-1)^k(k+1)^k$. So since $(-1)^k A + B = (-1)^{k+1}$ we obtain $V_k = (-1)^{k+1}$.

**4.4. The error in the current attempt.** Our aim was then to prove the following:

**Conjecture 4.** With the previous notations, we have for any $n \in \mathbb{N}_2$ and any $1 \le k \le n-2$ that $U_k(n) \equiv 0 \pmod{n}$.

Unfortunately it is not true, as was explained to us by (we now realise) several referees. Our aim was to proceed as follows.

The $i=1$ term of $U_k(n)$ is $(n-1-k)!$. Let us say that $(n-1-k)! \equiv a \pmod{n}$ for some $a \in [0; n-1]$. Then for any $j \in [1; k]$ we have by induction $(n-1-k+j)! \equiv a \times (n-k) \times \cdots \times (n-1-k+j) \equiv (-1)^j a \frac{k!}{(k-j)!} \pmod{n}$. So $a$ is in factor in each term of $U_k(n)$.

If $a=0$ then $U_k(n) \equiv 0 \pmod{n}$. If $a \ne 0$, then $U_k(n)$ can be factored by $a$, but that is as far as one can proceed. In particular, one **cannot** write (using the previous paragraph with $i=j+1$) that we have $U_k(n) = a \times \sum_{i=1}^{k+1} \frac{(-1)^{i-1}}{i!} \binom{k+1}{i} i^k = a \times \left( \sum_{i=1}^{k} \frac{1}{k+1} \binom{k+1}{i} (-1)^{i-1} i^k + (-1)^k \frac{(k+1)^k}{k+1} \right)$, due to the division by $i!$ (non-commutativity of two otherwise true congruences – this is nothing else than the fact that $H_k(n) \ne 0$ nor $1 \pmod{n}$ as seen in the numerical data).

Had that been the case, recalling that the term in parenthesis is an integer, and multiplying by the quantity $k+1$ (which is non-zero modulo $n$ since $1 \le k \le n-2$) we would have obtained $(k+1)U_k(n) = a \times \left( \sum_{i=1}^{k} \binom{k+1}{i} (-1)^{i-1} i^k + (-1)^k (k+1)^k \right)$. Expanding $(k+1)^k$ with the binomial theorem and simplifying, we notice that the resulting expression is 0 by theorem 3. So we would have necessarily had $U_k(n) \equiv 0 \pmod{n}$...

## REFERENCES

[1] T. Agoh, *On Giuga's conjecture*, Manuscripta Math. **87** (1995), 501–510.

[2] E. Bedocchi, *Nota ad una congettura sui numeri primi*, Riv. Mat. Univ. Parma (4) **11** (1985), 229–236.

[3] D. Borwein, J.M. Borwein, P.B. Borwein, and R. Girgensohn, *Giuga's conjecture on primality*, The American Mathematical Monthly **103** (1996), 40–50.

[4] D. Borwein, C. Maitland, and M. Skerritt, *Computation of an improved lower bound to Giuga's primality conjecture*, Integers **23** (2013), A67.

[5] G. Giuga, *Su una presumibile proprietà caratteristica dei numeri primi*, Ist. Lombardo Sci. Lett. Rend. Cl. Sci. Mat. Nat. (3). **14** (1950), 511–528.
REMARKS ON AN INTERPOLATION BETWEEN WILSON'S THEOREM AND GIUGA'S CONJECTURE

[6] A. Granville, *Arithmetic properties of binomial coefficients i: Binomial coefficients modulo prime powers*, Organic mathematics : proceedings of the organic mathematics workshop, december 12-14, 1995. simon fraser university, burnaby, british columbia, 2006. http://www.cecm.sfu.ca/organics/papers/granville/paper/binomial/html/binomial.html.

[7] R. K. Guy, *Unsolved problems in number theory (2nd edition)*, Springer, Berlin, 2004.

[8] B.C. Kellner, *The equivalence of Giuga's and Agoh's conjectures*, 2004. math/0409259.

[9] F. Luca, C. Pomerance, and I. Shparlinski, *On Giuga numbers*, Int. J. Mod. Math. **4** (2009), 13–18.

[10] A. Nicolas, *Sums of powers below a prime*, 2018. https://math.stackexchange.com/questions/433678/sums-of-powers-below-a-prime.

[11] Brian M. Scott, *Congruence for stirling number of first kind s(n, k) when n is prime*, 2018. https://math stackexchange com questions 1241649/congruence-for-stirling-number-of-first-kind-sn-k-when-n-is-prime.

[12] Z.-W. Sun, *Introduction to Bernoulli and Euler polynomials*, 2002. Lecture given in Taiwan http://maths.nju.edu.cn/zwsun/BerE.pdf.

[13] V. Tipu, *A note on Giuga's conjecture*, Canad. Math. Bull. **50** (2007), 158–160.
*E-mail address: thomasfsauvaget@gmail.com*