### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CSCI 124 with Professor Vora at GW (8)

### View Full Document

## 34

## 0

## Popular in Course

## Popular in Department

This 4 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 34 views.

## Reviews for Class Note for CSCI 124 with Professor Vora at GW (8)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/07/15

CSCI 124224 Discrete Structures 11 GCD Poorvi L Vora Recall that we showed in the module on Groups that I has a multiplicative inverse modulo m if and only if 3 ab E Z sit or bm 1 In this module we see that this is related to a very familiar concept the GCD We also see how we may nd out if such a and b exist De nition The greatest common divisor of two positive integers m and n is the largest integer that divides both m and n It is denoted m n or gcdm In other words 7 91m yin g 7 m n 42gt zlm zln zlg Here all is notation for a divides b Recall that all b lea for some k E Z Examples 69 3 1236 12 59 1 De nition m and n are said to be relatively prime if m n 1 Theorem mn l ltgt 3 a I sit am 1m 1 Proof gt Suppose m n 1 Consider all integers of the form Am Bn for integers A and B Let g Aom Bon be the smallest such integer We show that g mn l and hence that So A0 b B0siti am 1m g 1 Consider any arbitrary integer z Am Bn Let T 1 Tem 9 That is TAmBning qi E Z A qu0m B i 4130 and T is also a combination of m and n However 9 is the smallest nonnegative integer of that form and T is smaller than 9 CSCI 124 and CSCI 224VoraGWU 2 Hence 7 0 glAer Bn VA B ylmygln Also I m zln zlA0m Ben 9 Hence mn gl 3aA0bB0 sitiambngl 4 Suppose 3 a 12 st am 1m 1 Then mm m myn n a 7217an a mm 1 1 Condition for the Existence of an Inverse in Zn The theorem above immediately provides a necessary and suf cient condition for the existence of inverses in Zm Corollary 1 E Zm is invertible ltgt L721 1 Proof From above theorem and the theorem in the module on groups the above corollary follows U Example How many elements in Z10 are invertible What are the invertible elements The invertible elements are those that are relatively prime to 10 These elements are l 3 7 9 The number of invert ible elements is 4 Example How many distinct keys for the af ne cipher exist over Z10 There are 4 invertible elements hence 4 values of a There are 10 values of 12 Hence there is a total of 40 possibilities for the key In the next section we describe an algorithm to determine the gcd of two given elements It can easily be used to determine if the value a of the af ne cipher is invertible over Zm 2 mn nm rem n The euclidean algorithm for the gcd of two elements is thought to be the oldest existing algorithm It is recursive It uses the following idea Theoremm n n m rem n CSCI 124 and CSCI 224VoraGWU Proof Let g m n and 7 m rem n then mTqmnqu E 713 Because 9 m n the following are known glm yin I m zln zlg 172 le yin yin ylm fmm 1 yly fmm 3 47 5 9 m T 3 The Euclidean Algorithm The euclidean algorithm is as follows gcdm n m gt n l a b I m n Initialize while I f 0 a b I b a Tem 12 retun1a Example Use the euclidean algorithm to determine gcd79 551 a b 551 79 a b 79 77 a b 77 2 a b 2 l a b l 0 TetuTnl Example Use the euclidean algorithm to determine gcd632 5056 ab 869632 ab 632237 ab 237158 ab 15879 ab 790 Tetu39rn79 1 2 3 4 5 In each recursion gcda b stays the same while a and b change Further at each step we decrease both a and b and neither is ever negative Hence the algorithm will end some time in fact in at most n steps Finally at the last but one CSCI 124 and CSCI 224VoIaGWU 4 recursion because a rem b is zero a is a multiple of b and hence gcda b b At the last recursion a b b 0 and the retunied value a is the correct god it is the value of b from the previous recursion Thus we now have a means of determining if a given element in Zm is invertible and hence can be used for the value of a in the af ne cipher However we need the value of a 1 for a decryption In the next section we study an extension of the euclidean GCD algorithm to nd the inverse of an invertible element in Zm

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.