Giuga Numbers - an introduction

A modular problem revisited aka Giuga numbers

I think this is quite interesting… I’ve been messing with this problem for a while. Eventually I found some more examples and this enabled me to track down work that others have done.

The original question was this:

Are there any odd numbers with factors a<b<c for which

ab = 1 mod c

ac = 1 mod b

bc = 1 mod a

Apparently these kinds of numbers are called Giuga Numbers. You can also define them thus:

If X is a Giuga number, then for any of its prime factors p

X/p – 1 = 0 mod p

(I already knew that an even Giuga number exists, 30, for which

2x3 = 1 mod 5

2x5 = 1 mod 3

3x5 = 1 mod 2)

Now, it’s fairly easy to prove that you can’t find an odd Giuga number with less than nine factors. (I’ll put my version of this proof at the end for anyone interested). But the question becomes more complicated for numbers with more factors, for instance is there an odd Giuga number abcdefghi for which

abcdefgh = 1 mod i

abcdefgi = 1 mod h

And so on.

I wanted to start by looking at how we can construct/discover a Giuga number, regardless of whether it is even or odd.

First, let’s start with the really trivial case of a Giuga number with two factors. And (for reasons which will become clear) let’s also look for numbers for which

a = -1 mod b

b = -1 mod a

Clearly this isn’t going to work for many numbers because where a < b, a = a mod b

The only cases where it does work are:

1. 2 – this is trivial but worth noting. If you allow the idea of “mod 1”, we can use a residue number system where the co-ordinates are mod 1 and mod 2 and we get

1 = 1 mod 2

2 = 1 mod 1

a+b = (0,1) + (1,0) = (1,1) = 3

ab = (0,1) x (1,0) = (0,0) = 2

2. The above is trivial but it leads to one more example which isn't a Giuga number, but which has a related form, 6 (2 x 3):

2 = -1 mod 3 = (0,-1)

3 = -1 mod 2 = (-1,0)

a+b = (-1,-1) = 5

ab = (0,0) = 6

From here, we can go on to construct a few examples of Giuga numbers.

Firstly, we already know that 30 is a Giuga number so let’s look at how it works, using the residue number system for mod (2,3,5):

2 = (0, -1, 2)

3 = (-1, 0, 3)

5 = (-1, -1, 0)

2x3 = (0,0,6) = (0,0,1)

2x5= (0,1,0)

3x5 = (1,0,0)

We’ve added c = 5 to the grid, and because ab = ± 1 mod c we end up with ± 1 in the appropriate position (in place of 6 in the co-ordinates for 2 x 3)

The next step is to see if we can repeat the trick using abc = ± 1 mod d.

It doesn’t work for 2x3x5x29 or 2x3x5x31 because we end up with an uneven mix of +1s and -1s (see Appendix 2 for the calculations).

So let’s take a step back and look at 2x3x7 = 42

2 = (0, -1, 2)

3 = (-1, 0, 3)

7 = (1, 1, 0)

2x3 = (0,0,6) = (0,0,-1)

2x7= (0,-1,0)

3x7 = (-1,0,0)

So ab = -1 mod c

ac = -1 mod b and

bc = -1 mod a

This isn’t a Giuga number – so let’s call it a primary pseudoperfect number (OK, I googled that – basically it means one where the factors X/p = -1 mod p for all the prime factors p of the composite X).

The interesting thing here is howwe can extend this using d, where abc = ± 1 mod d.

2x3x7x41 = 1722

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

7 = (1, 1, 0, 7)

41 = (-1,-1,-1,0)

2x3x7 = (0,0,0,42) = (0,0,0,1)

2x3x41 = (0,0,-6,0) = (0,0,1,0)

2x7x41 = (0,1,0,0)

3x5x41 = (1,0,0,0)

This works to produce a new Giuga number, because the +1s and -1s balance out (because the one negative result, -6, is nonetheless +1 in mod 7)

So 1722 is a Giuga number

(At this stage I cheated a bit by googling “30,1722” and found via the lovely OEIS - that what I was looking for was called a “Giuga number”. See Appendix 2 for more detail on the relationship between Giuga numbers and primary pseudoperfect numbers.)

As it happens, 858 is also a reasonably small Giuga number so let’s see how this one works.

2x3x11x13

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

11 = (-1,-1, 0, -2)

13 = (1, 1, 2, 0)

2x3x11 = (0,0,0,-12)

2x3x13 = (0,0,12,0)

2x11x13 = (0,1,0,0)

3x11x13 = (1,0,0,0)

In the next post I will give what I think it is a proof that all Giuga numbers are even

Appendix

Here’s the original proof of the original problem for three odd numbers - using a residue number system.

ab = (0,0,1) = abc/c

ac = (0,1,0) = abc /b

bc = (1,0,0) = abc/a

ab + ac + bc = (1,1,1) = ab +1 (or = 1 or a higher multiple of ab + 1)

ab + ac + bc = abc/a + abc/b + abc/c

So ab + ac + bc can’t add up to more than 1/3 + 1/5 + 1/7 = 70/105

RAA

This proof works up to eight factors as 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 + 1/23 < 1 but thereafter it fails.

You also can’t have an odd Giuga number with less than 1415 factors and an odd number of factors because all of abcdefg…etc are odd, so for an odd number of factors, the sum abcd + abce + abde + acde + bcde is odd and can’t be abcde+1.

This proof works up to 1415 factors because that is how many factors would be needed before this sum can equal 2abcde+1.

However if the proof in the next post works, neither of these proofs are needed.

Edit nb the next post is missing because there were some flaws, which I might or more likely might not be able to iron out.

Appendix 2

It also turns out that if a primary pseudoperfect number is one less than a prime then the product P(P+1) gives a new primary pseudoperfect number. However if a primary pseudoperfect number is one more than a prime then the product p(P-1) gives a Giuga number.

For instance we’ve seen that 42 x 41 = 1722. (Giuga)
And 42 x 43 = 1806 (Primary pseudoperfect)

47508 x 47507 = 2214408306 which is a Giuga number

Appendix 3

2 x 3 x 5 x 29 = 870

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

5 = (-1, -1, 0, 5)

29 = (-1,-1,-1,0)

2x3x5 = (0,0,0,30) = (0,0,0,1)

2x3x29 = (0,0,-6, 0) = (0,0,-1,0)

2x5x29 = (0,-1,0,0)

3x5x29 = (-1,0,0,0)

This doesn’t work because we have an uneven mix of +1 and -1s. The same problem applies to the next attempt:

2 x 3 x 5 x 31 = 930

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

5 = (-1, -1, 0, 5)

31 = (1, 1, 1,0)

2x3x5 = (0,0,0,30) = (0,0,0,-1)

2x3x31 = (0,0,6, 0) = (0,0,1,0)

2x5x31 = (0,1,0,0)

3x5x31 = (1,0,0,0)

2 = (0, -1, 2, 2)

3 = (-1, 0, 3, 3)

5 = (-1, -1, 0, 5)

29 = (-1,-1,-1,0)

2x3x5 = (0,0,0,30) = (0,0,0,1)

2x3x29 = (0,0,-6, 0) = (0,0,-1,0)

2x5x29 = (0,-1,0,0)

3x5x29 = (-1,0,0,0)