On Giuga Numbers

In number theory, certain numbers are sometimes given special names if their prime factorisations have a special property. For an integer $n$, a divisor $d$ is called a proper divisor as long as $d < n$. Also $1$ is a proper divisor in this case. This gives us 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.


The Agoh-Giuga Conjecture which i discussed also here, is equivalent to the statement that there exists no number that is concurrently a Carmichael Number and a Giuga Number.

A Carmichael number must be odd and all known Giuga numbers are even. If you can prove that there do not exist an odd Giuga number then you also have settled the Agoh-Giuga Conjecture. Another way to characterize a Giuga number is, that $n$ is a Giuga number if and only if $$\sum_{p | n} \frac{1}{p} - \prod_{p | n} \frac{1}{p} \in \mathbb{N}$$ Based on this and some further reasoning you can bound the least number of prime factors for an odd Giuga number by $14$.

Giuga numbers have also some interesting property when using them in the Chinese remainder theorem. If you have a squarefree integer $n = p_1p_2\ldots p_m$ (a Giuga number must be squarefree), then $$R \equiv r_1\frac{n}{p_1}I_1 + r_2\frac{n}{p_2}I_2 +\ldots + r_m\frac{n}{p_m}I_m \pmod{n}$$ with $R$ being an integer $0 \leq R < n$ whereof $\frac{n}{p_i}I_i \equiv 1\pmod{p_i}$ and $R \equiv r_i \pmod{p_i}$. In case of a Giuga number we get $$R \equiv r_1\frac{n}{p_1} + r_2\frac{n}{p_2} +\ldots + r_m\frac{n}{p_m} \pmod{n}$$ Over the integers we get $$R =r_1\frac{n}{p_1} + r_2\frac{n}{p_2} +\ldots + r_m\frac{n}{p_m} - nk_R$$ or $$\frac{R}{n} =\frac{r_1}{p_1} + \frac{r_2}{p_2} +\ldots + \frac{r_m}{p_m} - k_R$$ with $0 \leq k_R < m$. Assume that wlog $p_1 < p_2 < \ldots < p_m$ and that set $R  = 1$. This yields $1 = r_1 = r_2 = \ldots = r_m$, hence $$\frac{1}{n} = \sum^m_{i=1} \frac{1}{p_i}  - k_R$$ or $$k_R  = \sum^m_{i=1} \frac{1}{p_i} - \prod^m_{i=1} \frac{1}{p_i} $$ which equals the characterization of the Giuga numbers shown above.

In the paper Giuga’s conjecture on primality the authors Borwein, Borwein, Borwein and Girgensohn [3] (yes, three times Borwein is correct) address a slightly generalization of a Giuga number, which they call Giuga sequence. A Giuga sequence is of the form $$[n_1,n_2,\ldots, n_m], n_i \in \mathbb{N}$$ and fulfills $$ \sum^m_{i=1} \frac{1}{n_i} - \prod^m_{i=1} \frac{1}{n_i} \in \mathbb{N} $$ So the difference is, that the $n_i$ have not to be prime numbers. We call the product $\prod^m_{i=1} n_i$ a Giuga squence number (If all $n_i \in \mathbb{P}$ it is a Giuga number). So all Giuga numbers are also Giuga sequence numbers but not the other way round. They showed that there are infinite many Giuga sequence numbers (in contrast to the open question if there are infinite Giuga numbers).

Theorem (Extension). Let $n = n_1n_2\ldots n_m$ be a Giuga sequence number. If you multiply $n$ by factors $\tilde{n}_1, \tilde{n}_2, \ldots, \tilde{n}_k$  you only can obtain a new Giuga sequence number if $$ \prod^k_{i=1}\tilde{n}_i \equiv 1 \pmod{n}$$

Proof. Since $n$ is a Giuga sequence number it is $$ \frac{n}{n_i} \equiv 1 \pmod{n_i}, 1 \leq i \leq m$$ And since $n\prod^k_{i=1}\tilde{n}_i =: \tilde{n}$ is again a Giuga sequence number, it is $$ \frac{\tilde{n}}{n_i} \equiv \frac{n\prod^k_{i=1}\tilde{n}_i}{n_i} \equiv \prod^k_{i=1}\tilde{n}_i \equiv 1 \pmod{n_i}, 1 \leq i \leq m$$. Using the Chinese remainder theorem, this yields $$\prod^k_{i=1}\tilde{n}_i \equiv 1 \pmod{n}$$ ⬛


Borwein et al also mentioned in their paper the following observation:

Assume that every Giuga sequence number $n = \prod^m_{i=1}n_i$ can be a divisor of another Giuga sequence number $\tilde{n} = n\prod^k_{j=1}\tilde{n}_i$, i.e. $n | \tilde{n}$. It is $$ \frac{1}{n_1} + \frac{1}{n_2} + \ldots + \frac{1}{n_m} - \frac{1}{n} = u \in \mathbb{N} $$ and  $$ \frac{1}{n} + \frac{1}{\tilde{n}_1} + \ldots + \frac{1}{\tilde{n}_k} - \frac{1}{\tilde{n}} = w \in \mathbb{N} $$ We substitute $1/n$ in the later with the former equation, hence $$ \frac{1}{n_1} + \frac{1}{n_2} + \ldots + \frac{1}{n_m} + \frac{1}{\tilde{n}_1} + \ldots + \frac{1}{\tilde{n}_k} - \frac{1}{\tilde{n}} = u+w \in \mathbb{N} $$ So $u+w $ is also a Giuga sequence number.

Note that this would increase the integer on the right side to some integer $>1$. From the point of view of $\tilde{n}$ one of its divisor is just splitted up into further divisors but the integer $\tilde{n}$ itself stays the same. From $n$'s point of view it gets extended with further divisors. According to the Extension Theorem this enforces that $\prod^k_{i=1} \tilde{n}_i \equiv 1\pmod{n}$, i.e., $\prod^k_{i=1} \tilde{n}_i = 1 + n\lambda$ with $\lambda \in \mathbb{N}_{> 0}$.  Hence we can write $\tilde{n} = n(1+n\lambda)$.

➤Arithmetic Derivative

Computing the derivative of a function in one or more variables is a standard method in mathematics. However, there is also a arithmetic derivative in number theory that involves the prime factors of the input integer.

Definition (Arithmetic derivative). Given an integer $n \in \mathbb{N}$ then its arithmetic derivative $n'$ is:

1. $n' = 1$ of $n$ is a prime number
2. $n' = (uv)' = u'v+uv'$ for $u,v \in \mathbb{N}$

Also the Leibnitz rule holds for the arithmetic derivative: $(n^e)' = en^{e-1}n'$ for $n \in \mathbb{N}$.The existence of an arithmetic derivative is relatively unknown but it is actually pretty useful and is able to restate the description of several problems in number theory. So for example for a semiprime $n = pq$ it is $n' = p+q$. If $n = p^2q^3uv$ with $p,q,u,v \in \mathbb{P}$ then
\begin{align}
n' & = 2pq^3uv + p^2(q^3uv)' \\
    & = 2pq^3uv + p^2(3q^2uv+q^3(uv)') \\
    & = 2pq^3uv + p^2(3q^2uv+q^3(u+v)') \\
    & = 2pq^3uv + 3p^2q^2uv+p^2q^3u+p^2q^3v \\
    & = \left(\frac{2}{p} + \frac{3}{q} + \frac{1}{u} + \frac{1}{v}\right)n
\end{align}
For me the most useful way to memorize the arithmetic derivative is, if $n = \prod^k_{i=1} p_i^{e_i}$ then we get $$n ' = n\sum^k_{i=1}\frac{e_i}{p_i}$$ Using this you can reformulate some famouse problems, e.g.:

Goldbach's Conjecture 
For every integer $n \in \mathbb{N}$, with $n>1$, there exists two prime numbers $p,q$ such that $p + q = 2n$.

Goldbach's Conjecture (arithmetic derivative)
For every integer $n \in \mathbb{N}$, with $n>1$, there exists an semiprime number $m$ such that $2n = m'$.

Or

Twin Prime Conjecture
There exists infinitely many prime numbers $p$ and $q$ such that $q-p = 2$.

Twin Prime Conjecture (arithmetic derivative)
There exits infinitely many integers of the form $n=2p$ with $p$ a prime number such that $n'' = 1$.

Note that the second derivative of an integer $n=2p$ is $n'' = (2+p)'$. And $(2+p)' = 1$ only if $2+p$ is a prime number itself, say $2+p=q$, hence $2 = q-p$. Another example is, that you can write the $\Phi$ function for an RSA number $N=pq$ as $\Phi(N) = N-N'+1$. Finally, also a Giuga number can also be described via the arithmetic derivative.

Giuga Number
A Giuga number is an integer $n$ such that $n' = an+1$ for some $a \in \mathbb{N}_{>0}$.

Note that is actually very easy to create an integer $n$ that is an almost Giuga number. With almost i mean the following. If $n = p_1p_2\ldots p_kQ = \tilde{n}Q$, with $p_i$ and $Q$ prime numbers, such that $p_i |n/p_i-1$ but $Q\nmid n/p_i-1$. So all but only one prime factor of $n$ is "correct". The sad new is, that $Q$ is very big, because it is the solution to the Chinese remainder result
$$ \frac{\tilde{n}}{p_i}Q \equiv 1\pmod{p_i} $$ (which has to be repeated with different primes if $Q$ is not prime). Hence $Q$ is of the size $~ \tilde{n}$ (but strictly smaller) so the chances that Q accidentally divides $\tilde{n}-1$ is negligible.

[1] W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 139: 703–722.
[2] Löh, G.; Niebuhr, W. (1996). "A new algorithm for constructing large Carmichael numbers" (PDF). Math. Comp. 65: 823–836
[3] Borwein, D.; Borwein, J. M.; Borwein, P. B.; Girgensohn, R. (1996). "Giuga's Conjecture on Primality" (PDF). American Mathematical Monthly. 103: 40–50