Group: Proving ‘Weapon’ = Euclidean Division Algorithm

Euclidean Division Algorithm:

m= qn + r  ; 0 ≤ r < n; (m, n, q, r) in Z

Apply:
Cyclic group of order n:
a^n = e
Take any m, prove it is still within the cyclic group:
a^m = a^{qn+r} =a^{qn}.a^r =(a^n)^{q}.a^r = e^q.a^r = e.a^r =a^r [QED]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s