## Friday, 20 July 2012

### A modular problem

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.