Monday, October 23, 2017

On Giuga Numbers

In Number Theory it happens that certain numbers get special names if their prime factorizations have some special property. For an integer $n$ a divisor $d$ is called proper divisor as long as $d < n$. Also $1$ is a proper divisor in this case. Using this, we have the following examples:
  1. Prime Numbers: An integer $n$ with only one proper divisor.
  2. Perfect Numbers (also Deficient / Abundant Numbers): An integer $n$ such that the sum of all its proper divisors is equal to $n$. (Deficient $< n$; Abundant $> n$).
  3. Carmichael Numbers : An integer $n$ such that $(p-1) | (n/p-1)$ for each prime factor $p$ of $n$
  4. Giuga Numbers : An integer $n$ such that $p | (n/p-1)$ for each prime factor $p$ of $n$
To 1.) It is known since Euclid that there are infinite many prime numbers. 

To 2.) It is not known if there are infinite many perfect numbers nor is know if there exists a single odd perfect number since all currently known perfect numbers are even e.g., $6 = 1\cdot 2\cdot 3 = 1+2+3=6$ or $28 = 1\cdot 2^2\cdot 7 = 1 + 2 + 4 + 7 + 14 = 28$. The total number of known perfect numbers is 49.

To 3.) Carmichael numbers are often mentioned in relationship with primality testing. A Carmichael number is a composite number $n$ that passes every Fermat primality test as long as the chosen basis $b$ is co-prime to $n$. In particular, every Carmichael number must be odd. In 1994 Alford, Granville and Pomerance [1] proved that there exists infinitely many Carmichael numbers. There even exists an algorithm to construct new Carmichael numbers [2].

To 4.) The definition of a Giuga number is very similar to the one of a Carmichael number. However, the status quo is more similar to the perfect numbers. It is not known if there are infinitely many Giuga numbers and every known Giuga number is even (actually, in fact all known Giuga numbers are a multiple of $6$). E.g. $30 = 2\cdot 3\cdot 5$ because $$2 | \frac{30}{2}-1$$ $$3 | \frac{30}{3}-1$$ $$5 | \frac{30}{5}-1$$ Currently (2019) there are 13 known Giuga numbers.