Greetings, was going over some of my old notes the other day and came across something which I can't quite work it out in my head.....

the offending statement...

Code:

given k*a = k*b ( mod m ), if k and m are co-prime, then a = b ( mod m )

which is fair enough, but the example that is given confuses me somewhat...

Code:

20 = 40 (mod 10), dividing by 2 gives 10 = 20 (mod 10) which holds...
but dividing by 5 gives 4 = 8 (mod 10) which doesn't hold.

This would imply that gcd(2,10)=1, but gcd(5,10) != 1 so 5 and 10 are not co-prime....

10 = 5 * 2

5 = ( 2 * 2 ) + 1

2 = ( 2 * 1 )

10 = 2 * 5

2 = ( 2 * 1 )

But what I can't get in my head is...

by the definition of co-prime, two numbers m,n are said to be co-prime if they share no proper factors ( i.e gcd(m,n) = 1 ).

For 5 and 10, their greatest factor ( other than itselt 5 ) is 1, since all that go into 10 and 5 properly are 5 & 1, but under the same assumption couldn't you say this for 2 and 10, since the only numbers that go into 2 & 10, are 2 & 1.

This would make them both co-prime, yet this would imply that the 'offending statement' is not true....

I have a funny feeling I am missing something obvious here.... help would be appreciated...

Many thanks.