Variations on Giuga Numbers and Giuga’s Congruence
A $k$ -strong Giuga number is a composite integer such that $∑_{j = 1}^{n − 1} j^{n − 1} ≡ − 1 (mod n)$. We consider the congruence $∑_{j = 1}^{n − 1} j^{k(n − 1)} ≡ − 1 (mod n)$ for each $k ϵ ℕ$ (thus extending Giuga’s ideas for $k = 1$). In particular, it is proved that a pair $(n, k)$ with comp...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2015
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/2091 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508019143475200 |
|---|---|
| author | Grau, José María Грау, Хосе Марія |
| author_facet | Grau, José María Грау, Хосе Марія |
| author_sort | Grau, José María |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T09:50:14Z |
| description | A $k$ -strong Giuga number is a composite integer such that $∑_{j = 1}^{n − 1} j^{n − 1} ≡ − 1 (mod n)$. We consider the congruence $∑_{j = 1}^{n − 1} j^{k(n − 1)} ≡ − 1 (mod n)$ for each $k ϵ ℕ$ (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)$. |
| first_indexed | 2026-03-24T02:18:33Z |
| format | Article |
| 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
|
| id | umjimathkievua-article-2091 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:18:33Z |
| publishDate | 2015 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/5a/0af4858a20b594fe2bb744553ac3fd5a.pdf |
| spelling | umjimathkievua-article-20912019-12-05T09:50:14Z Variations on Giuga Numbers and Giuga’s Congruence Variations on Giuga Numbers and Giuga’s Congruence Grau, José María Грау, Хосе Марія A $k$ -strong Giuga number is a composite integer such that $∑_{j = 1}^{n − 1} j^{n − 1} ≡ − 1 (mod n)$. We consider the congruence $∑_{j = 1}^{n − 1} j^{k(n − 1)} ≡ − 1 (mod n)$ for each $k ϵ ℕ$ (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$- сильне число Гюга - це складне ціле число таке, що $∑_{j = 1}^{n − 1} j^{n − 1} ≡ − 1 (mod n)$. Ми розглядаємо конгруенцію $∑_{j = 1}^{n − 1} j^{k(n − 1)} ≡ − 1 (mod n)$ для кожного $k ϵ ℕ$ (таким чином ми розширюємо ідєї Гюга на випадок $k = 1$). Як частинний випадок доведено, що пара $(n, k)$ зі складеним $n$ задовольняє цю конгруенцію тоді i тільки тоді, коли $n$ — число Гюга та $⋋(n) | k(n − 1)$. Крім того, встановлено деякі нові характеристики чисел Гюга та вивчено властивості чисел n, що задовольняють $⋋(n) | k(n − 1)$. Institute of Mathematics, NAS of Ukraine 2015-11-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2091 Ukrains’kyi Matematychnyi Zhurnal; Vol. 67 No. 11 (2015); 1573-1578 Український математичний журнал; Том 67 № 11 (2015); 1573-1578 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/2091/1197 https://umj.imath.kiev.ua/index.php/umj/article/view/2091/1198 Copyright (c) 2015 Grau José María |
| spellingShingle | Grau, José María Грау, Хосе Марія Variations on Giuga Numbers and Giuga’s Congruence |
| title | Variations on Giuga Numbers and Giuga’s Congruence |
| title_alt | 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_short | Variations on Giuga Numbers and Giuga’s Congruence |
| title_sort | variations on giuga numbers and giuga’s congruence |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2091 |
| work_keys_str_mv | AT graujosemaria variationsongiuganumbersandgiugascongruence AT grauhosemaríâ variationsongiuganumbersandgiugascongruence |