8
$\begingroup$

Why do all Giuga numbers have exactly one odd prime factor which is congruent to 1 (mod 4) , with all their other odd prime factors being congruent to 3 (mod 4) ?

only thirteen Giuga Numbers are known. They are: 30 = 2 · 3 · 5.

858 = 2 · 3 · 11 · 13,

1722 = 2 · 3 · 7 · 41.

66198 = 2 · 3 · 11 · 17 · 59.

2214408306 = 2 · 3 · 11 · 23 · 31 · 47057,

24423128562 = 2 · 3 · 7 · 43 · 3041 · 4447.

432749205173838 = 2 · 3 · 7 · 59 · 163 · 1381 · 775807,

14737133470010574 = 2 · 3 · 7 · 71 · 103 · 67213 · 713863,

550843391309130318 = 2 · 3 · 7 · 71 · 103 · 61559 · 29133437.

244197000982499715087866346 = 2 · 3 · 11 · 23 · 31 · 47137 · 28282147· 3892535183,

554079914617070801288578559178 = 2 · 3 · 11 · 23 · 31 · 47059 · 2259696349· 110725121051,

1910667181420507984555759916338506 = 2 · 3 · 7 · 43 · · · 1831 · 138683 · 2861051· 1456230512169437.

4200017949707747062038711509670656632404195753751630609228764416 142557211582098432545190323474818 = 2 · 3 · 11 · 23 .31 · 47059 · 2217342227· 1729101023519 · 8491659218261819498490029296021· 658254480569119734123541298976556403.

Primes which are congruent to 1 (mod 4 ) are in bold. Note that for each Giuga number there is exactly one odd prime factor which is congruent to 1 (mod 4). All the other prime factors are congruent to 3 (mod 4 ). Is this just a coincidence ? Or is there a number-theoretic reason for this ?

$\endgroup$
  • $\begingroup$ Nice question (+1) What is the definition of a Giuga number ? $\endgroup$ – Peter Aug 17 '17 at 21:49
  • 1
    $\begingroup$ A Giuga Number is a composite number n such that p divides n/p - 1 for every p, prime divisor of n. $\endgroup$ – Derek Aug 17 '17 at 21:56
  • $\begingroup$ Seems that all Giuga numbers are even and squarefree. It might be a good start to prove that. $\endgroup$ – Peter Aug 17 '17 at 21:58
  • 2
    $\begingroup$ @Peter the wikipedia article shows squarefree; even is a conjecture en.wikipedia.org/wiki/Giuga_number $\endgroup$ – Will Jagy Aug 17 '17 at 22:03
  • 1
    $\begingroup$ Far above Giuga's waters, With its waves of blue, Stands our noble Alma Mater, Glorious to view. $\endgroup$ – Will Jagy Aug 17 '17 at 22:21
2
$\begingroup$

Here is a partial answer. I can prove the following (except for one computation that I defer to Wikipedia for a reference).

  • If $n$ is a even Giuga number with $<59$ prime factors, then $n$ has an odd number of prime factors that are $1$ mod $4$.
  • If $n$ is an odd Giuga number, then $\omega(n) \equiv 2 \pmod 4$ and $\omega(n) \ge 14$.

This helps explain that some of the observations in the OP and comments could reasonably be attributed to "small number" phenomena, since the cost of searching for Giuga numbers tends to grow doubly-exponentially with the number of prime factors, so any Giuga number we have found will have a relatively small number of factors.

One major thing this answer doesn't explain: why exactly one prime factor? This pattern seems to hold out in the more general setting of Giuga sequences as studied by Brenton et al, though I wasn't able to find an exhaustive list beyond 7 or 8 terms. Maybe someone can find a simple refine that is able to improve "odd" to "congruent to $1$ mod $4$", or maybe there is a clever argument involving quadratic residues.

Proof: First observe that $p \mid \sum_{p\mid n} n/p - 1$ for all $p \mid n$. We already know $n$ is squarefree, so $n \mid \sum_{p\mid n} n/p - 1$, meaning that $(\sum_{p\mid n} 1/p) - 1/n$ is an integer. Since the sum of reciprocals of the first $58$ primes is a little under $2$, it is clear that any Giuga number with fewer than $59$ prime factors must satisfy:

$$\left(\sum_{p\mid n} 1/p\right) - 1/n= 1.$$

Suppose $n$ is even, with $r$ prime factors $p_1,\ldots,p_r$ congruent to $1$ mod $4$, and $s$ prime factors $q_1,\ldots,q_s$ congruent to $3$ mod $4$. Then the above equation, multiplied by $2$, is:

$$ 1 + \frac{2}{p_1} + \cdots + \frac{2}{p_r} + \frac{2}{q_1} + \cdots + \frac{2}{q_s} - \frac{1}{p_1\cdots p_r q_1 \cdots q_s} = 2. $$

The LHS is a $2$-adic integer, so we can look at it mod $4$ (equivalently, we clear out numerators, the computation is basically the same). Each $\frac{2}{p}$ term contributes a $2$, and a quick computation confirms that $p_1\cdots p_r q_1 \cdots q_s$ is congruent to $1 + 2s \pmod 4$. Therefore

$$ 1 + 2(r+s) - (1+2s) \equiv 2r \equiv 2 \pmod 4,$$

which is equivalent to $r$ being odd. This proves that there is at least one prime factor of the form $4k+1$. Note that the same calculation shows that if ever we found an even Giuga number with $(\sum_{p\mid n} 1/p) - 1/n = 2$, then it must have an even number of prime factors of the form $4k+1$, so it plausible that the initial conjecture in OP is false.

The case where $n$ is odd can be analyzed by the same methods as above, but the conclusion we can draw is that $r+s \equiv 2 \pmod 4$, so $\omega(n) \equiv 2 \pmod 4$. Furthermore, the reciprocal sum of the first $6$ odd primes is $<1$, so we must have $\omega(n) > 6$. The reciprocal sum of the first $10$ odd primes is only $\approx 1.0657$: this small amount of slack results in a short computer search which shows that there are no $10$-prime odd solutions, meaning that $\omega(n) \ge 14$ as claimed on Wikipedia.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.