A brief discussion of a proof using modulo

Though the proof below is correct, I now suspect this proof can be more easily written using the following fact:

(ab)mod n = [(a mod n)(b mod n)]mod n. I will add a proof of this at a later date (or try proving it yourself, it’s not too hard).

Older proof:

Let S be a set {0,1,2,3,...,n-1} and let a*b (a,b in S) be defined as a*b=(ab)(mod n) where ab is ordinary multiplication.

Prove (a*b)*c = a*(b*c)

Since a*b = (ab)(mod n) then (a*b)*c= ( (a*b)(mod n))*c = (( (a*b)(mod n))c)(mod n)

Let x= (ab)(mod n). Then n|x-ab or x-ab = kn => x=kn+ab

Now consider x*c = ((kn+ab)*c) =( (kn+ab)c) (mod n)=(abc+knc)(mod n) =(abc)(mod n)

Similarly (SHOW THIS), a*(b*c) = (abc)(mod n)

QED