(r·s)mod n =((r mod n)·(s mod n))mod n gilt

Question

ich soll (r·s)mod n =((r mod n)·(s mod n))mod n zeigen.

Meine Idee:

r = p mod n

s = q mod n. Dabei sei 0<=p,q<n aus diesem Grund kann r und s geschrieben werden als r = a*n + p und s =b*n + q

(r*s) mod n = ((a*n + p) mod n* (b*n + q) mod n) mod n =(abn² + a*nq+ b*np +pq) mod n = pq mod n

Ich wollt fragen, ob das so okay ist. Nur find ich, dass ich das besser mit dem mod n (also im Term) zeigen muss.

Answer 1

r = p mod n dann gibt es ein a sodass r-p=an oder r=p+an

s = q mod n. dann gibt es ein b sodass s-q=bn oder s=q+bn

rs=abn² + a*nq+ b*np +pq=pq+ (abn + a*q+ b*p)·n

Also alles richtg.

Comments

Erstmal danke.

Aber ich dacht eher, dass ich eher das (a mod n * b mod n) mod n zeigen muss, deshalb fand ich meins nicht so korrekt:/