Variations on Giuga Numbers and Giuga’s Congruence
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут математики НАН України
2015
|
| Назва видання: | Український математичний журнал |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/165917 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Variations on Giuga Numbers and Giuga’s Congruence / J.-M. Grau, A.M. Oller-Marcén // Український математичний журнал. — 2015. — Т. 67, № 11. — С. 1573–1578. — Бібліогр.: 18 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-165917 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1659172020-02-18T01:27:31Z Variations on Giuga Numbers and Giuga’s Congruence Grau, J.-M. Oller-Marcén, A.M. Короткі повідомлення 2015 Article Variations on Giuga Numbers and Giuga’s Congruence / J.-M. Grau, A.M. Oller-Marcén // Український математичний журнал. — 2015. — Т. 67, № 11. — С. 1573–1578. — Бібліогр.: 18 назв. — англ. 1027-3190 http://dspace.nbuv.gov.ua/handle/123456789/165917 512.5 en Український математичний журнал Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Короткі повідомлення Короткі повідомлення |
| spellingShingle |
Короткі повідомлення Короткі повідомлення Grau, J.-M. Oller-Marcén, A.M. Variations on Giuga Numbers and Giuga’s Congruence Український математичний журнал |
| format |
Article |
| author |
Grau, J.-M. Oller-Marcén, A.M. |
| author_facet |
Grau, J.-M. Oller-Marcén, A.M. |
| author_sort |
Grau, J.-M. |
| title |
Variations on Giuga Numbers and Giuga’s Congruence |
| title_short |
Variations on Giuga Numbers and Giuga’s Congruence |
| title_full |
Variations on Giuga Numbers and Giuga’s Congruence |
| title_fullStr |
Variations on Giuga Numbers and Giuga’s Congruence |
| title_full_unstemmed |
Variations on Giuga Numbers and Giuga’s Congruence |
| title_sort |
variations on giuga numbers and giuga’s congruence |
| publisher |
Інститут математики НАН України |
| publishDate |
2015 |
| topic_facet |
Короткі повідомлення |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/165917 |
| citation_txt |
Variations on Giuga Numbers and Giuga’s Congruence / J.-M. Grau, A.M. Oller-Marcén // Український математичний журнал. — 2015. — Т. 67, № 11. — С. 1573–1578. — Бібліогр.: 18 назв. — англ. |
| series |
Український математичний журнал |
| work_keys_str_mv |
AT graujm variationsongiuganumbersandgiugascongruence AT ollermarcenam variationsongiuganumbersandgiugascongruence |
| first_indexed |
2025-07-14T20:22:35Z |
| last_indexed |
2025-07-14T20:22:35Z |
| _version_ |
1837655189036728320 |
| fulltext |
UDC 512.5
José Marı́a Grau (Univ. de Oviedo, Spain),
A. M. Oller-Marcén (Centro Univ. de la Defensa, Zaragoza, Spain)
VARIATIONS ON GIUGA NUMBERS AND GIUGA’S CONGRUENCE
ВАРIАЦIЇ ЧИСЕЛ ТА КОНГРУЕНЦIЇ ГЮГА
A k-strong Giuga number is a composite integer such that
∑n−1
j=1
jn−1 ≡ −1 (mod n). We consider the congruence∑n−1
j=1
jk(n−1) ≡ −1 (mod n) for each k ∈ N (thus extending Giuga’s ideas for k = 1). In particular, it is proved
that a pair (n, k) with composite n satisfies this congruence if and only if n is a Giuga number and λ(n) | k(n − 1). In
passing, we establish some new characterizations of Giuga numbers and study some properties of the numbers n satisfying
λ(n) | k(n− 1).
k-Сильне число Гюга — це складене цiле число таке, що
∑n−1
j=1
jn−1 ≡ −1 (mod n). Ми розглядаємо конгруенцiю∑n−1
j=1
jk(n−1) ≡ −1 (mod n) для кожного k ∈ N (таким чином ми розширюємо iдеї Гюга на випадок k = 1).
Як частинний випадок доведено, що пара (n, k) зi складеним n задовольняє цю конгруенцiю тодi i тiльки тодi,
коли n — число Гюга та λ(n) | k(n− 1). Крiм того, встановлено деякi новi характеристики чисел Гюга та вивчено
властивостi чисел n, що задовольняють λ(n) | k(n− 1).
1. Preliminaries. The starting point of this paper is the following definition.
Definition 1. i) A Giuga number is a composite integer n such that p | (n/p− 1) for every p,
prime divisor of n.
ii) A strong Giuga number is a composite integer n such that p(p− 1) | (n/p− 1) for every p,
prime divisor of n.
Strong Giuga numbers are counterexamples to Giuga’s conjecture [8]; i.e., they are composite
integers such that
n−1∑
j=1
jn−1 ≡ −1 (mod n). (1)
There are several equivalent ways to define Giuga numbers [1, 5, 8, 10]. In particular we focus
on the following characterization of Giuga numbers [5, p. 41] that, in some sense, is analogue to the
one given in (1) for strong Giuga numbers.
Proposition 1. Let n be an integer. Then n is a Giuga number if and only if
n−1∑
j=1
jφ(n) ≡ −1 (mod n),
where φ is Euler’s totient function.
Clearly strong Giuga numbers are also Giuga numbers and, in fact, using the so-called Korselt’s
criterion [14] it can be seen that:
Proposition 2. An integer n is a strong Giuga number if and only if it is both a Giuga and a
Carmichael number.
c© JOSÉ MARÍA GRAU, A. M. OLLER-MARCÉN, 2015
ISSN 1027-3190. Укр. мат. журн., 2015, т. 67, № 11 1573
1574 JOSÉ MARÍA GRAU, A. M. OLLER-MARCÉN
Much work has been done regarding these numbers [1, 3, 10, 13, 16, 17] and several generaliza-
tions and/or variations are possible [6, 9]. In this paper some new characterizations of Giuga numbers
will be established. This characterizations will lead to a generalization of both strong Giuga numbers
and Carmichael numbers.
2. New characterizations of Giuga numbers. This section is devoted to give a familiy of
characterizations of Giuga numbers that include Proposition 1. The following lemma will be our
main tool.
Lemma 1. For every natural numbers A, B and N we have that
N−1∑
j=1
jAλ(N) ≡
N−1∑
j=1
jBφ(N) (mod N).
Proof. Put N = 2apr11 . . . prss with pi distinct odd primes. Choose i ∈ {1, . . . , s}. We have that
N−1∑
j=1
jAλ(N) ≡ N
prii
p
ri
i −1∑
j=1
jAλ(N) (mod prii ),
N−1∑
j=1
jBφ(N) ≡ N
prii
p
ri
i −1∑
j=1
jBφ(N) (mod prii ).
Now, since both Aλ(N), Bφ(N) ≥ ri, we get
p
ri
i −1∑
j=1
jAλ(N) =
∑
1≤j≤prii −1
(pi,j)=1
jAλ(N) +
∑
1≤j≤prii −1
pi|j
jAλ(N) ≡ φ(prii ) + 0 (mod prii ),
p
ri
i −1∑
j=1
jBφ(N) =
∑
1≤j≤prii −1
(pi,j)=1
jBφ(N) +
∑
1≤j≤prii −1
pi|j
jAλ(N) ≡ φ(prii ) + 0 (mod prii ).
Consequently,
N−1∑
j=1
jAλ(N) ≡
N−1∑
j=1
jBφ(N) (mod prii ) for every i = 1, . . . , s.
Clearly if N is odd the proof is complete. If n is even we have that
N−1∑
j=1
jAλ(N) ≡ N
2a
2a−1∑
j=1
jAλ(N) ≡ N
2a
∑
1≤j≤2a−1
j even
jAλ(N) + 2a−1
(mod 2a),
N−1∑
j=1
≡ N
2a
∑
1≤j≤2a−1
j even
jBφ(N) + 2a−1
(mod 2a).
ISSN 1027-3190. Укр. мат. журн., 2015, т. 67, № 11
VARIATIONS ON GIUGA NUMBERS AND GIUGA’S CONGRUENCE 1575
Now, if a = 1, 2 or 3 it can be easily verified that∑
1≤j≤2a−1
j even
jAλ(N) ≡
∑
1≤j≤2a−1
j even
jBφ(N) (mod 2a).
On the other hand, if a ≥ 4 we have that φ(N) ≥ λ(N) ≥ a and, consequently, jAλ(N) ≡ jBφ(N) ≡ 0
(mod 2a) for every 1 ≤ j ≤ 2a−1 even. Thus
N−1∑
j=1
jAλ(N) ≡
N−1∑
j=1
jBφ(N) (mod 2a).
Lemma 1 is proved.
The following result extends Proposition 1. In particular it shows that we can replace Euler’s
totient function φ(n) by Carmichael’s function λ(n) or by any multiple of φ(n) or λ(n).
Proposition 3. Let n be any composite integer. Then the following are equivalent:
i) n is a Giuga number;
ii) for every positive integer K,
∑n−1
j=1
jKλ(n) ≡
∑n−1
j=1
jKφ(n) ≡ −1 (mod n);
iii) there exists a positive integer K such that
∑n−1
j=1
jKλ(n) ≡
∑n−1
j=1
jKφ(n) ≡ −1 (mod n).
Remark 1. If n is a Carmichael number, then λ(n)|(n− 1). If we put k =
n− 1
λ(n)
, then we have
S :=
n−1∑
j=1
jn−1 =
n−1∑
j=1
jkλ(n).
If, in addition, n is a Giuga number, we can apply Lemma 1 with A = k and B = 1 to get S ≡ −1
(mod n). Hence, we have a new proof of Proposition 2 which avoids the use of Korselt’s criterion
replacing it by Carmichael’s criterion [7].
3. k-strong Giuga numbers and k-Carmichael numbers. As a clear consequence of Proposi-
tion 3 we have the following result.
Corollary 1. Let n be a strong Giuga number. Then
n−1∑
j=1
jk(n−1) ≡ −1 (mod n)
for every positive integer k.
Proof. If n is a strong Giuga number, then it is both a Carmichael and a Giuga number. Being
a Carmichael number, we have that λ(n) | (n− 1), so if
k(n− 1)
λ(n)
= k′ ∈ N we get
S :=
n−1∑
j=1
jk(n−1) =
n−1∑
j=1
j
kλ(n)
(n−1)
λ(n) =
n−1∑
j=1
jk
′λ(n),
and, since n is a Giuga number, it is enough to apply Corollary 1 and Proposition 3 to get S ≡ −1
(mod n).
Corollary 1 is proved.
This result motivates the definitions below. In some sense we are stratifying strong Giuga numbers
and Carmichael numbers. A similar idea was used in [11] in the context of Lehmer numbers [15].
ISSN 1027-3190. Укр. мат. журн., 2015, т. 67, № 11
1576 JOSÉ MARÍA GRAU, A. M. OLLER-MARCÉN
Definition 2. Let k ∈ N.
i) A composite number n is a k-strong Giuga number if
n−1∑
j=1
jk(n−1) ≡ −1 (mod n).
ii) An integer n is a k-Carmichael number if λ(n) divides k(n− 1).
Remark 2. Observe that for k = 1 we recover the classical Carmichael and strong Giuga numbes.
It is well-known that Carmichael numbers are square-free. This is no longer true for k-Carmichael
numbers with k > 1. Nevertheless we have the following result.
Proposition 4. Let n be a square-free positive composite integer and let k ∈ N. The following
are equivalent:
i) n is a k-Carmichael number,
ii) for every prime divisor p of n, p− 1 divides k(n− 1),
iii) for every integer a, akn ≡ ak (mod n).
Proof. If n is a square-free k-Carmichael number, then λ(n) = lcm{p− 1 | p divides n} divides
k(n− 1). This proves that i) implies ii).
Now, if p− 1 divides k(n− 1) for every prime divisor p of n and given any integer a, it follows
that ak(n−1) ≡ 1 (mod p) for every prime divisor p of n such that p does not divide a. If p divides
a the same congruence follows trivially and this proves that ii) implies iii).
Finally, to see that iii) implies i) it is enough to consider an integer a coprime to n.
Proposition 4 is proved.
We are now in the condition give an analogue of Proposition 2.
Theorem 1. Let n be a composite integer. Then n is a k-strong Giuga number if and only if n
is both a Giuga number and a k-Carmichael number.
Proof. Assume that n is a Giuga number and a k-Carmichael number. Since λ(n) divides
k(n− 1) we have that
n−1∑
j=1
jk(n−1) =
n−1∑
j=1
jk
′λ(n) ≡ −1
due to Proposition 3.
Conversely, assume that n is a k-strong Giuga number, i.e.,
∑n−1
j=1
jk(n−1) ≡ −1 (mod n).
As a consequence (see [18], Theorem 2.3) we have that p − 1 divides k (n/p− 1) , that p divides
n/p− 1 for every p, prime divisor of n and, moreover, that n is square-free. Since n is square-free,
λ(n) = lcm{p − 1 | p prime dividing n}. Thus, λ(n) divides k(n − 1) and n is a k-Carmichael
number. To get that n is also a Giuga number, due to Proposition 2, it is enough to apply Lemma 1
with B = 1 and A =
k(n− 1)
λ(n)
.
Theorem 1 is proved.
Associated to the idea of k-strong Giuga numbers, let us define the following sets:
Gk := {n ∈ N | n is k-strong Giuga number},
Kn := {k ∈ N | n is k-strong Giuga number}.
ISSN 1027-3190. Укр. мат. журн., 2015, т. 67, № 11
VARIATIONS ON GIUGA NUMBERS AND GIUGA’S CONGRUENCE 1577
Taking into account that the condition λ(n) | k(n − 1) is equivalent to
λ(n)
gcd(λ(n), n− 1)
∣∣∣ k,
Theorem 1 gives a complete description of the set Kn for every n as stated in the following corollary.
Corollary 2. Let n be any composite positive integer. Then
Kn =
{
t · λ(n)
gcd(λ(n), n− 1)
∣∣∣ t ∈ N
}
, if n is a Giuga number,
∅, otherwise.
Moreover, since it is clear that n ∈ Gk if and only if k ∈ Kn we also have the following result.
Corollary 3. Gk is nonempty if and only if λ(n) divides k(n− 1) for some Giuga number n.
This last result can be used to find values of k such that Gk is nonempty. To do so, we evaluate
kn :=
λ(n)
gcd(λ(n), n− 1)
for every of the thirteen known Giuga numbers g1, . . . , g13 (see A007850 in
the On-line Encyclopedia of Integer Sequences). Thus, we will have thirteen values of k for which
Gtk is known to be nonempty for any t:
kg1 = 4,
kg2 = 60,
kg3 = 120,
kg4 = 2320,
kg5 = 1552848,
kg6 = 10080,
kg7 = 139714902540,
kg8 = 93294624780,
kg9 = 228657996794220,
kg10 = 4756736241732916394976,
kg11 = 20024071474861042488900,
kg12 = 2176937111336664570375832140,
kg13 = 15366743578393906356665002406454800354974137359272
445859047945613961394951904884493965220.
For these values and t = 1 one gets:
Gkg1 = {g1, . . . },
Gkg2 = {g1, g2, . . . },
Gkg3 = {g1, g2, g3, . . . },
Gkg4 = {g1, g4, . . . },
ISSN 1027-3190. Укр. мат. журн., 2015, т. 67, № 11
1578 JOSÉ MARÍA GRAU, A. M. OLLER-MARCÉN
Gkg5 = {g1, g5, . . . },
Gkg6 = {g1, g2, g6, . . . },
Gkg7 = {g1, g7, . . . },
Gkg8 = {g1, g2, g8, . . . },
Gkg9 = {g1, g2, g9, . . . },
Gkg10 = {g1, g10, . . . },
Gkg11 = {g1, g11, . . . },
Gkg12 = {g1, g2, g12, . . . },
Gkg13 = {g1, g2, g13, . . . }.
Finally observe that, with this notation, Giuga’s conjecture can be stated as G1 = ∅.
1. Takashi Agoh. On Giuga’s conjecture // Manuscr. Math. – 1995. – 87, № 4. – P. 501 – 510.
2. William D. Banks, C. Wesley Nevans, Carl Pomerance. A remark on Giuga’s conjecture and Lehmer’s totient problem
// Alban. J. Math. – 2009. – 3, № 2. – P. 81 – 85.
3. Edmondo Bedocchi. Note on a conjecture about prime numbers // Riv. mat. Univ. Parma. – 1985. – 11, № 4. –
P. 229 – 236.
4. Beeger N. G. W. H. On composite numbers n for which an−1 ≡ (modn) for every a prime to n // Scr. Math. –
1950. – 16. – P. 133 – 135.
5. Borwein D., Borwein J. M., Borwein P. B., Girgensohn R. Giuga’s conjecture on primality // Amer. Math. Mon. –
1996. – 103, № 1. – P. 40 – 50.
6. Borwein J. M., Wong E. A survey of results relating to Giuga’s conjecture on primality // Adv. Math. Sci.: CRM’s
25 years (Montreal, PQ, 1994). – Providence, RI: Amer. Math. Soc., 1997. – 11. – P. 13 – 27.
7. Carmichael R. D. On composite numbers P which satisfy the Fermat congruence aP−1 ≡ 1modP // Amer. Math.
Mon. – 1912. – 19, № 2. – P. 22 – 27.
8. Giuseppe Giuga. Su una presumibile proprietá caratteristica dei numeri primi // Ist. Lombardo Sci. Lett. Rend. Cl.
Sci. Mat. Nat. – 1950. – 14/83, № 3. – P. 511 – 528.
9. José Marı́a Grau, Florian Luca, Antonio M. Oller-Marcén. On a variant of Giuga numbers // Acta Math. Sinica. –
2011. – 28, № 4. – P. 653 – 660.
10. José Marı́a Grau, Antonio M. Oller-Marcén. Giuga numbers and the arithmetic derivative // J. Integer Sequences. –
2012. – 15, № 4. – Article 12.4.1.
11. José Marı́a Grau, Antonio M. Oller-Marcén. On k-Lehmer numbers // Integers. – 2012. – 12, № 5. – P. 1081 – 1089.
12. Glyn Harman. On the number of Carmichael numbers up to x // Bull. London Math. Soc. – 2005. – 37, № 5. –
P. 641 – 650.
13. Bernd C. Kellner. The equivalence of giuga’s and agoh’s conjectures // arXiv:math/0409259v1 [math.NT].
14. Alwin R. Korselt. Problè me chinois // Interméd. math. – 1996. – 6. – P. 142 – 143.
15. Lehmer D. H. On Euler’s totient function // Bull. Amer. Math. Soc. – 1932. – 38, № 10. – P. 745 – 751.
16. Florian Luca, Carl Pomerance, Igor Shparlinski. On Giuga numbers // Int. J. Mod. Math. – 2009. – 4, № 1. –
P. 13 – 18.
17. Vicentiu Tipu. A note on Giuga’s conjecture // Can. Math. Bull. – 2007. – 50, № 1. – P. 158 – 160.
18. Erick Wong. Computations on normal families of primes: M. Sc. Thesis. – Simon Fraser Univ., 1997.
Received 20.11.13
ISSN 1027-3190. Укр. мат. журн., 2015, т. 67, № 11
|