# Theorem on Giuga number

Giuga number : $n$ is a Giuga number $\iff$ For every prime factor $p$ of $n$ , $p | (\frac{n}{p}-1)$

How to prove the following theorem on Giuga numbers

$n$ is a giuga number $\iff$ $\sum_{i=1}^{n-1} i^{\phi(n)} \equiv -1 \mod {n}$

The $\Rightarrow$ part. For first, a giuga number must be squarefree, since, by assuming $p^2\mid n$, we have that $p$ divides two consecutive numbers, $\frac{n}{p}$ and $\frac{n}{p}-1$, that is clearly impossible. So we have: $$n = \prod_{i=1}^{k} p_i$$ that implies: $$\phi(n) = \prod_{i=1}^{k} (p_i-1).$$ By considering the sum $$\sum_{i=0}^{n-1}i^{\phi(n)}$$ $\pmod{p_i}$ we have that all the terms contribute with a $1$, except the multiples of $p_i$ that contribute with a zero. This gives: $$\sum_{i=0}^{n-1}i^{\phi(n)}\equiv n-\frac{n}{p_i}\equiv (n-1)\pmod{p_i}\tag{1}$$ that holds for any $i\in[1,k]$. The chinese theorem now give: $$\sum_{i=0}^{n-1}i^{\phi(n)}\equiv n-1\pmod{\prod_{i=1}^{k}p_i}$$ that is just: $$\sum_{i=0}^{n-1}i^{\phi(n)}\equiv -1\pmod{n}$$ as claimed. For the $\Leftarrow$ part, we have that the congruence $\!\!\!\pmod{n}$ implies the congruence $\!\!\!\pmod{p_i}$, hence $(1)$ must hold, so we must have: $$\frac{n}{p_i}\equiv 1\pmod{p_i}$$ that is equivalent to $p_i\mid\left(\frac{n}{p_i}-1\right).$