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 ?
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.