Giuga number

In number theory, a Giuga number is a composite number $n$ such that for each of its distinct prime factors $p_{i}$ we have $p_{i}|\left({n \over p_{i}}-1\right)$ , or equivalently such that for each of its distinct prime factors p_i we have $p_{i}^{2}|(n-p_{i})$ . For example, 30 = 2 × 3 × 5 is a Giuga number since we can verify that:

30/2 − 1 = 14 = 2 × 7,
30/3 − 1 = 9 = 3², and
30/5 − 1 = 5.

The Giuga numbers are named after the mathematician Giuseppe Giuga, and relate to his conjecture on primality.

Alternative definition for a Giuga number due to Takashi Agoh is: a composite number n is a Giuga number if and only if the congruence

nB_{\varphi (n)}\equiv -1{\pmod {n}}

holds true, where B is a Bernoulli number and $\varphi (n)$ is Euler's totient function.

An equivalent formulation due to Giuseppe Giuga is: a composite number n is a Giuga number if and only if the congruence

\sum _{i=1}^{n-1}i^{\varphi (n)}\equiv -1{\pmod {n}}

and if and only if

\sum _{p|n}{\frac {1}{p}}-\prod _{p|n}{\frac {1}{p}}\in \mathbb {N} .

All known Giuga numbers n in fact satisfy the stronger condition

\sum _{p|n}{\frac {1}{p}}-\prod _{p|n}{\frac {1}{p}}=1.

List of numbers

Thirteen Giuga numbers are known. The list is complete up to the 12th term and for numbers with 8 or fewer prime factors, but it is unknown if there is a Giuga number between the 12th and 13th terms.^[1]

Rank	Number	Prime factorization
1	30	2 × 3 × 5
2	858	2 × 3 × 11 × 13
3	1722	2 × 3 × 7 × 41
4	66198	2 × 3 × 11 × 17 × 59
5	2214408306	2 × 3 × 11 × 23 × 31 × 47057
6	24423128562	2 × 3 × 7 × 43 × 3041 × 4447
7	432749205173838	2 × 3 × 7 × 59 × 163 × 1381 × 775807
8	14737133470010574	2 × 3 × 7 × 71 × 103 × 67213 × 713863
9	550843391309130318	2 × 3 × 7 × 71 × 103 × 61559 × 29133437
10	244197000982499715087866346	2 × 3 × 11 × 23 × 31 × 47137 × 28282147 × 3892535183
11	554079914617070801288578559178	2 × 3 × 11 × 23 × 31 × 47059 × 2259696349 × 110725121051
12	1910667181420507984555759916338506	2 × 3 × 7 × 43 × 1831 × 138683 × 2861051 × 1456230512169437
...
13?	42000179497077470620387115096706566324041957537516 30609228764416142557211582098432545190323474818	2 × 3 × 11 × 23 × 31 × 47059 × 2217342227 × 1729101023519 × 8491659218261819498490029296021 × 58254480569119734123541298976556403
...

Properties

The prime factors of a Giuga number must be distinct. If $p^{2}$ divides $n$ , then it follows that ${n \over p}-1=m-1$ , where $m=n/p$ is divisible by $p$ . Hence, $m-1$ would not be divisible by $p$ , and thus $n$ would not be a Giuga number.

Thus, only square-free integers can be Giuga numbers. For example, the factors of 60 are 2, 2, 3 and 5, and 60/2 - 1 = 29, which is not divisible by 2. Thus, 60 is not a Giuga number.

This rules out squares of primes, but semiprimes cannot be Giuga numbers either. For if $n=p_{1}p_{2}$ , with $p_{1}<p_{2}$ primes, then ${n \over p_{2}}-1=p_{1}-1<p_{2}$ , so $p_{2}$ will not divide ${n \over p_{2}}-1$ , and thus $n$ is not a Giuga number.

Unsolved problem in mathematics

Are there infinitely many Giuga numbers? Is there a composite Giuga number that is also a Carmichael number?

List of numbers

Properties

See also

References

Related Articles