This is something I already put up on My Math Forum.
Let a, b, c be three different prime numbers.
Is it possible that
ab = 1 mod c
ac = 1 mod b
bc = 1 mod a
This is clearly possible if one of the numbers is even as 30 is an example:
6 = 1 mod 5
10 = 1 mod 3
15 = 1 mod 2
But is it possible if they are all odd?
abc has three prime factors, a < b < c
Each number below abc has a unique set of modular residues for a, b, c which we will express as (x, y, z)
Assume
ab = 1 mod c
ac = 1 mod b
Start at (0, 0, 0) = 0
First we add (0, 0, 1) to get ab = 1 mod c = (0, 0, 1)
Then we add (0, 1, -1) to get to ac = 1 mod b = (0, 1, 0)
Now, assume we add (0, 1, 0) + (-1, -1, 0) = (-1, 0, 0)
If (-1, 0, 0)= bc then bc ≠ 1 mod a
We know that (-1, -1, 0) < bc because
(0, 0, 1) = ab
(-1, -1, 0) = (0, 0, 1) – 1 = ab - 1
ab < bc
Therefore (-1, -1, 0) < bc
Is it possible that (-1, 0, 0) ≠ bc?
To get to any other value of (x, 0, 0) we must add or subtract a multiple of bc from (-1, 0, 0)
We can’t subtract because (-1, 0, 0) < bc.
And (-1, 0, 0) + bc > bc.
Therefore (-1, 0, 0) = bc
Therefore bc ≠ 1 mod a
C.R.Greathouse helpfully pointed out that since I hadn't clearly specified that a, b, and c were odd that last bit didn't work - there's a bit more detail on how that can be cleaned up here.
What I really want is a more general version of this proof, that applies to numbers of more than three factors, as that would fit in with the other stuff I've been working on. I've made a start on this here.
No comments:
Post a Comment