Uncovering the Mystery of Numbers Divisible by 7

[matt grime]

as shmoe says, you do not "divide by 3 mod 9"

 

[gonzo]

Okay, thanks I think, though I would have liked a more direct answer. I am assuming you mean that division is always thought of as multiplication by the inverse instead, and since that inverse doesn't exist you are multiplying by something that doesn't exist, and so the whole thing is undefined. Which means it is like dividing by 0 in that sense.

Is this correct?

 

[shmoe]

yes, that's a fair summary.

 

[matt grime]

note that in the case of non-unit elements there may or may not be solutions to ax=b mod n, and let us assume b=/=0

suppose a is not invertible mod n, but that b is, with inverse c say, the a(xc)=1mod n, contradicting the assumption that a is not invertible.

so *if* there is a solution it is necessary that b is not invertible either. so for example

2x=5 mod 6 has no solutions

2x=4 mod 6 does have a solution though, but 2x=3 doesn't, so all other possibilties can arise.

to see what's going on it can somte times be useful to think of u=v mod n as saying v=mn+v for some integer m.

so, ax=b mod n says ax=mn+b for some m. rearranging ax-mn=b


of course hcf(a,n) divides the lhs [hightest common factor, so if there were a solution then it mustbe that the hcf divides the rhs, ie b.

this is why 2x=3 mod6 has no solution: hcf(2,6)=2 and 2 doesn't divide 3.

Can you see where that's going?


This also shows you that a number is invertibel mod n if and only if it is coprime with n.

If a is coprime with n, then by euclid's algorothm ap+nq=1 for some n and q, hence ap=1 mod n, that is p is the mutliplicative inverse of a.