### 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

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 3 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 20 views.

## Popular in Subject

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

### 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 124297 Discrete Structures 11 GCD Poorvi L Vora November 20 2006 Recall that we showed in the module on Groups that I has a multiplicative inverse modulo m if and only if 3 a b E Z sit or bm 1 In this module we see that this is related to a very familiar concept the GCD 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 glm 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 297VoraGWU 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 mnlm mnll mn 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 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 Zn 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 Proof Let g m n and 7 m rem n then mTqmnquZ 1 CSCI 124 and CSCI 297VoraGWU 3 Because 9 m n the following are known Him 9i 2 mm zln 3 269 lt3 1 2 e W 4 W yin ylm fmm 1 ylg fmm 3 5 47 5 9 7 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 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 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

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "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.