3
$\begingroup$

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} $

$\endgroup$
2
$\begingroup$

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).$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.