Giuga number
   HOME

TheInfoList



OR:

A Giuga number is a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
''n'' such that for each of its distinct
prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s ''p''''i'' we have p_i , \left( - 1\right), or equivalently such that for each of its distinct
prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s ''p''''i'' we have p_i^2 , (n - p_i). The Giuga numbers are named after the mathematician Giuseppe Giuga, and relate to his conjecture on primality.


Definitions

Alternative definition for a Giuga number due to Takashi Agoh is: a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
''n'' is a Giuga number
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
the congruence :nB_ \equiv -1 \pmod n holds true, where ''B'' is a
Bernoulli number In mathematics, the Bernoulli numbers are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in (and can be defined by) the Taylor series expansions of the tangent and hyperbolic tangent functions, ...
and \varphi(n) is
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
. An equivalent formulation due to Giuseppe Giuga is: a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
''n'' is a Giuga number if and only if the congruence :\sum_^ i^ \equiv -1 \pmod n and if and only if :\sum_ \frac - \prod_ \frac \in \mathbb. All known Giuga numbers ''n'' in fact satisfy the stronger condition :\sum_ \frac - \prod_ \frac = 1.


Examples

The sequence of Giuga numbers begins :30, 858, 1722, 66198, 2214408306, 24423128562, 432749205173838, … . For example, 30 is a Giuga number since its prime factors are 2, 3 and 5, and we can verify that * 30/2 - 1 = 14, which is divisible by 2, * 30/3 - 1 = 9, which is 3 squared, and * 30/5 - 1 = 5, the third prime factor itself.


Properties

The prime factors of a Giuga number must be distinct. If p^2 divides n, then it follows that - 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 integer In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-f ...
s 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
semiprime In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime nu ...
s cannot be Giuga numbers either. For if n=p_1p_2, with p_1 primes, then - 1 =p_1 - 1 , so p_2 will not divide - 1 , and thus n is not a Giuga number. All known Giuga numbers are even. If an odd Giuga number exists, it must be the product of at least 14
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s. It is not known if there are infinitely many Giuga numbers. It has been conjectured by Paolo P. Lava (2009) that Giuga numbers are the solutions of the differential equation ''n' = n+1'', where ''n' '' is the
arithmetic derivative In number theory, the Lagarias arithmetic derivative or number derivative is a function defined for integers, based on prime factorization, by analogy with the product rule for the derivative of a function that is used in mathematical analysis. T ...
of ''n''. (For square-free numbers n = \prod_i , n' = \sum_i \frac , so ''n' = n+1'' is just the last equation in the above section ''Definitions'', multiplied by ''n''.) José Mª Grau and Antonio Oller-Marcén have shown that an integer ''n'' is a Giuga number if and only if it satisfies ''n' = a n + 1'' for some integer ''a'' > 0, where ''n' '' is the
arithmetic derivative In number theory, the Lagarias arithmetic derivative or number derivative is a function defined for integers, based on prime factorization, by analogy with the product rule for the derivative of a function that is used in mathematical analysis. T ...
of ''n''. (Again, ''n' = a n + 1'' is identical to the third equation in ''Definitions'', multiplied by ''n''.)


See also

*
Carmichael number In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation: :b^n\equiv b\pmod for all integers b. The relation may also be expressed in the form: :b^\equiv 1\pmod. for all integers ...
*
Primary pseudoperfect number In mathematics, and particularly in number theory, ''N'' is a primary pseudoperfect number if it satisfies the Egyptian fraction equation :\frac + \sum_\frac = 1, where the sum is over only the prime divisors of ''N''. Properties Equivalently, ...


References

* * * {{Classes of natural numbers Integer sequences Unsolved problems in number theory