### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete and Foundational Mathematics I MATH 187

BSU

GPA 3.72

### View Full Document

## 7

## 0

## Popular in Course

## Popular in Mathematics (M)

This 8 page Class Notes was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Class Notes belongs to MATH 187 at Boise State University taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/218009/math-187-boise-state-university in Mathematics (M) at Boise State University.

## Popular in Mathematics (M)

## Reviews for Discrete and Foundational Mathematics I

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

Notes on Modular Exponentiation and Euler Function WITH ASSIGNMENT Dr Holmes April 127 2007 There are problems to be turned in all starred at the end of this docu ment 1 Modular Exponentiation Basic Fact 13 E amongmodn you can replace the base in an exponen tiation by its remainder mod n if you are working in mod n arithmetic But 13 is not necessarily congruent to ammo modulo n for example7 3 is equivalent to 13 in mod 10 arithmetic7 but 73 343 is not equivalent to 713 96889010407 the rst is equivalent to 3 mod 10 while the second is equivalent to 7 Repeated Squaring A technique which allows e icient computation of powers in modular arithmetic though not nearly as e icient as the method using Euler7s function below is the method of repeated squaring To compute a3 modn7 note that the exponent m is either even or odd If m 2k is even7 then 13 12c ak2 compute 1k then square it If m 2k 1 is odd7 then 13 1219 12c a ak2 1 Either way7 we compute the square of amquot2 and multiply by am d2 the latter being either 1 or a We give an example Compute 7330 mod 13 The powers of 7 that we need to compute are obtained by dividing 330 by 2 repreatedly throwing away remainders 330716578274172010757271 71 7 mod 13 72774910mod13 757227102711 mod 13 710 752 112 121 4 mod 13 720 7102 42 16 3 mod 13 741720273276311 mod 13 782 7412 112 121 4 mod 13 7165 7822 7 42 7 8 mod 13 7330 71652 82 64 12 mod 13 so the answer is 12 To compute 7330 the naive way would take 329 multiplications in general7 13 would take m 7 1 multiplications The method of repeated squaring takes roughly speaking 1 or 2 multiplications for each power of two below m the number of multiplications needed is at most 2 Tlog21 Here we needed 11 multiplications 2 Euler s Function For any positive integer n we de ne Mn as the number of positive integers a lt n such that a is relatively prime to 72 First Fact Mp p 7 1 if p is a prime In this case7 the positive integers less than p which are relatively prime to p are all of them 17 27 7p 7 1 are a total of p 7 1 positive integers less than p which are relatively prime to p Second Fact Mp p 7 p 1 for p a prime There are p 7 1 positive integers less than p Of these7 only the multiples of p are not relatively prime to p 7 and there are p 1 7 1 of these So there are 1 7 1 7 p 1 7 1 p 7 p 1 positive integers less than p which are relatively prime to p Third Fact If m and n are relatively prime7 then mn There are exactly as many natural numbers less than mm as there are systems of equations m amodm m bmodn with 0 S a lt m and 0 S b lt 717 because by the Chinese Remainder Theorem each of these mn equations has a unique solution mod mn A solution to one of these equations is relatively prime to 77m just in case a is relatively prime to m and b is relatively prime to n This means that there are Mm possible choices of a and Mn possible choices of b that work7 and thus there are m n positive integers less than mm 0 is not a possible choice which are relatively prime to 77m All of this only works if gcdm7n 1 if m and n are relatively prime Computing Euler s Function If we know the prime factorization of n we can compute Because we know how to compute Euler7s function for powers of primes7 and because the powers of different primes are relatively prime to each other7 we can take the values of Euler7s function at the prime powers in the factorization of n and multiply these together We give examples 5 4 5 is a prime7 so we just subtract 1 02 lt22 3 22 lt3gt lt22 e 21 lt3 71gt 4 200 23 52 23 7 22 52 7 51 4 20 80 90 23252713273157130 3 Modular Exponentiation using Euler s Func tion The big theorem of which we will probably only prove the special case with n a prime number is zmod aw E a gtmodn This follows from the fact that 1 E 1modn so 19 aq f m a gtq 1f 1 1 1f M where q mdivg n and r xmod We can replace the base of an exponentiation in mod n arithmetic with its remainder on division by 717 and we can replace the exponent with its remainder on division by This is much more effective than repeated squaring though we might also use repeated squaring if Mn is very large We also might have to use repeated squaring if we do not know the prime factorization of 717 since our ability to compute Mn depends on being able to factor 72 Example of calculation of a power by this method Compute 124354253523415675437654 mod 18 2518 lt2 32 lt2 711327 31gt 6 1243542535mod18 7 23415675437654 mod6 2 so 124354253523415675437654 72 49 13 mod 18 4 Exercises H Compute 71115 mod 11 by the method of repeated squaring N Compute the following values of the Euler function 37 0237 457 144 1437 M300 03 Compute 71115 mod11 same as rst problem using the Euler function to reduce the exponent 4 Compute 3424741467 mod 33 by whatever method or combination of meth ods works Notes and Exercises on Boolean Algebra Dr Holmes June 12 2006 1 Boolean Expressions from Truth Tables From the truth table for any operation on truth values we can read out an expression for that operation using 7 V7 For example7 a sz can be expressed as xAyA zV sAyAzV zy zv x y z This expression is a disjunction or sentence of conjunctions and sentences each of which is a conjunction of letters and negations of letters representing a row of the truth table If there are no rows in the truth table which are true7 the expression z s will represent it It should be clear that this will work for truth tables for expressions with any number of letters Exercise Write out an expression in V A n for the operation on three propositions represented by this truth table a w FF Exercise Construct a truth table for the operation represented by x a y y a 2 then derive an equivalent expression in V A n from the truth table 2 Algebraic Notation An expression in V A n can be written in an algebraic style Write z Ay as zy z Vy as x y and s as E Negations of complicated expressions like x y will not be written using overlines Write T as 1 and F as 0 in algebraic notation A selection of the algebra rules we saw in section 6 can be used to reduce any expression to a form like the ones we derived from truth tables An expression is said to be in disjunctive normal form just in case it is a disjunction of conjunctions of single letters and negations of single letters The expressions derived from truth tables have the additional character istic that every conjunction contains each letter or its negation just once The following rules will help us to reduce expressions to disjunctive nor mal forrn Distributive laws My z xy x2 and x yz x2 yz Use these to eliminate conjunctions involving disjunctions deMorgan7s laws xy y z y y Applying these rules repeatedly will convert any expression into a dis junction of conjunctions of letters and their negations or into a conjunction of letters and their negations7 or into a single letter or the negation of a single letter If any conjunction includes a letter z and also includes E it can be written mfg where y may be a complicated expression which will simplify to 0 false We have a rule z 0 now show 0y 0 to nish the demonstration 0y yijy yzj here the rule yy y is used 0 Now 0 can be eliminated as a term in a disjunction because we have a rule 0 z z already Applying these rules can give one more possible expression as a nal form which we accept as DNF 0 Of course any repeated expression in a disjunction or conjunction can be eliminated using idempotent laws xm z z x Example convert x V y V z z y to DNE ln algebraic notation7 this is x y y g x 17 y yzj 2 217 here I used the distributive law repeatedly just as in ordinary algebra7 not writing every step 0 mj yT 0 2T z zijyf zizg Exercise Convert x V y V 2 z y to DNE 3 Other Rules We can turn a DNF expression into an expression like those derived from truth tables by making sure that all the conjunctions contain the same letters To add a letter say y to a conjunction represented by m use the rule z zy m justi ed by the proof z x1 zy 17 xy m Emrcz39se Try converting the expressions from the previous example and exercise into forms from which truth tables can be read I give the proofs of the Absorption Laws from the class example7 though you will not be asked to use these First Absorption Law z zy z Proof z zyx xyy x zy zyx yz zy Exercise Justify each step in this proof using algebraic rules from the book or from this document Second Absorption Law z Ey z y Proof z y y x xy Ey xy 17 Ey eliminate repeated 961 z 2y Exercise Justify each step in this proof using algebraic rules from the book or from this document

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

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