### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Discrete Structures COT 3100C

University of Central Florida

GPA 3.74

### View Full Document

## 55

## 0

## Popular in Course

## Popular in Engineering and Tech

This 2 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 3100C at University of Central Florida taught by Shaojie Zhang in Fall. Since its upload, it has received 55 views. For similar materials see /class/227692/cot-3100c-university-of-central-florida in Engineering and Tech at University of Central Florida.

## Similar to COT 3100C at University of Central Florida

## Reviews for Introduction to Discrete Structures

### 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: 10/22/15

Modular Theorems 1 Let a b and c be a set of all integers a ab ac 9abc b ab 9abc for all integers c c ab bc 9 ac 2 The Division Algorithm Let a be an integer Then there are unique integers q and r with 05rltd such that adqr 3 Let a and b be integers and let m be a positive integer Then aEbmod m if and only ifa mod m b mo m 4 Let m be a positive integer The integers a and b are congruent to modu o m if and only ifthere is an integer k such that abkm 5 Let m be a positive integer f aEbmod m and cEdmod m then achdmod m and achdmod m aEb mod m mab Euclidean Algorithm 0 GCDsomeNum1 someNum2 o Whichever number is greater put it on the left hand side of the equation For the other number have it multiply as many times as it can into the greater number and add the remainder Ex GCD7 25 1st step 2573 4 Afterwards you want to shi everything tothe le Take the 7 and put it on the le hand side and multiply 4 into 7 as manytimes as it can without going over and add e remainder 2 d step 741 3 Just rinse and repeat from here until you get a remainder of zero Once you get to that point then the number added to zero is the GOD 3 d step 431 1 4m step 313 0 Modular De nitio 139 n If a and b are integers with a0 we say that a divides b ifthere is an intger c such that b ac When a divides b we say that a is a factor ofb and that b is a multiple ofa The notation ab denotes that a divides b We write a lb when a does not divide b m ab 9 abc ab bat b is equal to a times some num t b0at0 Therefore abc Premise ab ba a and b are some integers Therefore ab or a For ab abt For ba bas aast then divide both sides by a a0 1st with st1 or st1 Then go to the previous formulas Extended Euclidean Algorithm A er finding the GOD with the Euclidean Algorithm start by solving forthe remainder ofthe step next tothe last From the previous example it would be the 3 step 0 4311 o Solve for 1 1431 0 Next you want to go to the step before the one that was worked on and solve forthat remainder o For the example solve for 3 from the second step 2 step 7413 3741 0 Substitute the result into the 3 in the previous equation 31 0 1474 o 1431 0 Keep working your way up until you get an equation with your GCD equaling to your arguments amodm9 aq1mr Summations Prove by induction that 53quot2n 4quotn1 for n20 N0 3quot20 4quot01 5 9 55 Induction hygothesis Assume that for nk kEZ is follows 53quot2k 4quotk1 Induction steE Based on the lH we have to show that 53quot2k1 4quotk2 53quotk24quotk23quot2k 3A2 4quotk1 4 53quotk2 4quotk2 93quot2k 4quotk14 k4 4quotk14 53quot2k 43quot2k 4quotk1 53quot2k 45 someConstant 53quot2k 4someConstant POOF WW 9 0 9 2211 quot 3 ka 9 w 210 xk xlt1 9 1 ix 21kxk 1rlxl lt1 9 GCDA B LCMAB AB Set proof Oddpositive integers l 8 x 8 S 9 x 2 a S VxPx Therefore Pc Universal Instantiation Pl c for arbitray c Therefore VXP x Universal generalization 5le x Therefore Pc for some element C Existential instantiation Plc for some element C Therefore EIXPX Existential generalization us R11 1 and vemythat bath smes are equa1 mhes Assume P k is me Rewage 71m P1quot W111 k Ana DE tg vlargELjfr wk Pk1 MAW DE EFuHhe 1e11sme m1 addthe next 11eratmntetre x EAA x E a u matmn XEmama DeMn Ex Fertre 1e11 sme Pk12 Pk112 1lt1lt1 Aw m 39 quot EFurther1gHs1de1us1 pmg 1n k1 my every k ExFuHher1ng1de Pkkquot2 M A V H 1 Wm39 Inductive Ernnfs uaHy 42 Denquot nn nl imers n ee InnDistributive law lgzn39s Law Mnegminn sign an nfnegminn Sign P k1 k1 ENexHakethe su1u11un1urPk1u1 E12 r1gms1d2 arm quot quot39quotquot39quotquot equate 111 the Pku11hey1gms1de p1ustre1as11erm ertre Pk1 ertre 1e11 sme Ex Currsmertheexammesabuve 1mm m k1 1 e uahn the 1e11sme annclugs Smee we pruved trattre Eas1s arm W EA E U 0 E39fm f m quot52 quotquot 39quotquot due 1 mathemat1ca1 meuetmr M A X E EV X E 0 De nmnquot Mumquot Mnduh Em me 1x EAA x E a v x EAA x E 0 D39sllihulivelzw 1x E1An a 11 An 0 Dennninns nluninn and imerseeninn m 1 1 Anewquot Wig Wu 39quotJ are and Cam quotat are 5 a 2 as Permutations 1ryuu re prmrrg re1emerrts 21315171111131 171 19132331 rrem a set ufn e1emerrts rm duphcates 37 41 43 47 53 59 51 57 71 73 auewee arm emer DOES matter the 79 numberufways 1s 71 mt Ont4n ant 1m Utmr Ptr a My quot1 1 1t W m combmatuons 1ryuu re pmkmg r I 39l39 e1emerrts rrem a set at n e1emerrts rm duphcat re auuwed arm umer n n X DOESN T matter the number ufways1s 1 2 e 7quot 1 4 39 01m My 39 gtltM 4 1 W rtt out 1Iur nutmama Shaw sets def1n1te1y by1 5 arm st s m mm quotmm when s e 5 arm t e s 15 the set at pusmve U H 1rrtegers 1 e s gtamp Assumenr s 39 Easedum s armas 125nm app1y1rrg de mtmn er s Where s rr 1 r I to 1tru11uws s t 1 u 1 Eguwalence Relanons re1atmrr err a set A xlve 111 a R arer every a 1rr LetR ER1s r R 15 Irre exlve 111 a R arerrm a r R 15 symmetnc rrreRo oR arer everye arm Dm A be a re e 1rr A A r R 15 anttsymmetnc rrrrer every manna aandDmA eRoem aeR ransmve 111 rer every a 0 arm 0 1rreeRom DRCgtaRc x

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

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