There's Always One Isn't There

A number of people spotted that you cannot get a remainder of one if the two numbers you use have a common factor.

For example : 8 and 6 have 2 as a common factor.

Look at the multiples of 8 :

8, 16, 24, 32, 40, 48

And the remainders when we divide by 6 :

2, 4, 0, 2, 4, 0

Eight and six are both made from twos so taking away sixes is like taking away three twos from a collection of twos, and what's left over must be some twos! (or nothing at all)

OK, so if there's a common factor the remainder can never be one, but if the numbers don't have any common factor (coprime) does that mean there will always be a remainder of one somewhere ?

Dominic from St Paul's School says Yes :

If the numbers are a and b, and coprime, then ab is their lowest common multiple, the smallest multiple of a that is also a multiple of b.

The remainders, upon division by b, could be written $r_1, r_2, . . . . . , r_{b-1}$

Dominic is about to show that no two values from that set of remainders can be the same.

Just suppose two of the remainders, $r_k$ and $r_l$, were actually the same (with k< l, ie. k comes first).

Suppose that the remainder value when this happens is R then there is some integer value n

and another one, m, so that :

ka = nb + R and

la = mb + R

n is the number of times b goes into ka, and m is the number of times that b goes into la,

with R left as the remainder each time .

It follows, with that R the same in each expression, that la - ka = mb - nb

or (l - k) a = (m - n) b

and that would make (l - k)a divisible by b

However l - k is an integer value somewhere between 1 and b - 2 and we already know that ab is the smallest multiple of a that is divisible by b, so there is no l - k value to make (l - k)a divisible by b.

The conclusion is that no two remainders can be the same - they must all be different

And since there are b - 1 remainders, which have to take one of the values: 1,2,3...(b-1), and all be a different value, it follows that one of the remainders will be 1, which is what we wanted to prove.

Thank-you Dominic that's nice reasoning