### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Int Discrete Strctrs MATH 455

UMass

GPA 3.55

### View Full Document

## 15

## 0

## Popular in Course

## Popular in Mathematics (M)

This 4 page Class Notes was uploaded by Reuben Hudson DDS on Friday October 30, 2015. The Class Notes belongs to MATH 455 at University of Massachusetts taught by Murray Eisenberg in Fall. Since its upload, it has received 15 views. For similar materials see /class/232218/math-455-university-of-massachusetts in Mathematics (M) at University of Massachusetts.

## Reviews for Int Discrete Strctrs

### 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/30/15

Math 455 0 April 4 2009 Fermat7s Little Theorem For the RSA encryption system we shall need the following result Theorem 1 Fermat7s Little Theorem Letp be a prime Then for each integer a not divisible by p 01771 E1 mod p Proof Let a be an integer for which pia For eachj 12p7 1 let rj ja modp sothat Ogr ltp that is Ogr 1971 We are going to prove that r1 r2 rp1 is a permutation of 1 2 p7 1 For each j 123 p 71 we have ja i 0 mod p why that is 77 7 0 Thus r1r2 rp1 all belong to the set 1 23 p 71 Next if1 j k p71 withj 7 k then 77 7 77 Why Thus T1 72 rp1 is a set ofp 7 1 numbers that is a subset of the set 1 2 3 p 7 1 Hence these two sets are the same 71rgrp1123p71 Since both sets have p 7 1 elements then r1r2rp1 is a permutation of 12p71 In other words each of the p 7 1 numbers a 2a 3a p 7 1a is congruent modulo pto exactly one of thep7 1 numbers 1 23p7 1 Hence a2a3ap71a El23p71 modp In other words 29 MW 30971 mod p Now each of the factors 1 2 3 p71 of p7 1 is relatively prime to p and so by the Congruence Cancellation Law may be cancelled from both sides of After the cancellations what remains is 01771 E1 mod p as desired 1 The following corollary is in fact equivalent to Fermat s Little Theorem Corollary 1 Letp be a prime The for every integer a a E a mod p Fermat s Little Theorem may be used to calculate ef ciently modulo a prime powers of an integer not divisible by the prime Example 1 Calculate 2345 mod 11 ef ciently using Fermat s Little Theorem Solution The number 2 is not divisible by the prime 11 so 210 E 1 mod 11 by Fermat s Little Theorem By the division algorithm 34534105 Since 2345 234105 21034 25 then 2345 E 134 25 E 1 32 E 10 mod 11 Thus 2345 mod 11 10 The result actually needed for RSA encryption is the following corollary to Fer mat s Little Theorem Corollary 2 Euler7s Corollary Letp and q be distinct primes Then for each integer a not divisible by eitherp or q awiwq l E 1 mod pq Proof This is an exercise D Both Fermat s Little Theorem and Euler s Corollary are special cases of a more general result To formulate the generalization we need the following de nition De nition 1 Euler7s phi function 1 N a N is de ned by the rule that for each positive integer n gtn k 1 g k lt n and k is relatively prime to n For example lt2gt 1 1 lt3gt m 2 lt4gt L3 2 gt6 15 2 and gt12 15711 4 Then the generalization is as follows Theorem 2 Euler7s Theorem Let in be an integer with m gt 1 Then for each integer a that is relatively prime to m a ltmgt E 1 mod m We will not prove Euler s Theorem here because we do not need it Fermat s Little Theorem is a special case of Euler s Theorem because for a prime p Euler s phi function takes the value gtp p7 1 Note that for a prime p saying that an integer a is relatively prime to p is equivalent to saying that p does not divide a Euler s Corollary is also a special case of Euler s Theorem because for distinct primes p and q Euler s phi function takes the value gtp q p 7 1q 7 1 Copyright 2009 by Murray Eisenherg All rights reserved Notes on counting nite sets Murray Eisenberg February 267 2009 Contents 0 Introduction 1 What is a nite set 2 Counting unions and cartesian products 21 Sum rules i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 22 Product rules ordered selection With independent choices i i i i i i i i i i i 23 Generalized product rules ordered selection With dependent choices i i i i i 24 InclusionExclusion Principle i i i i i i i i i i i i i i i i i i i i i i i i i i i 3 The Pigeonhole Principle 31 The basic Pigeonhole Principle i i i i i i i i i i i i i i i i i i i i i i i i i i 32 The Generalized Pigeonhole Principle i i i i i i i i i i i i i i i i i i i i i i 4 Counting subsets unordered selection with no repetitions 5 Sets of functions between nite sets 51 Permutations i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 52 Injections i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 53 Derangements i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 6 Indistinguishable objects 61 MISSISSIPPI models i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 62 Starsandbars models i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 63 Xs and Wedges models i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 7 Partitions 7 1 Surjections i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i Copyright 200372009 by Murray Eisenbergi All rights reserved

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

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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