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:
- 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
- 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.
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)
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)
