### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Note 4 for MATH 300 at UMass

### View Full Document

## 13

## 0

## Popular in Course

## Popular in Department

This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Note 4 for MATH 300 at UMass

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

Math 300 Fall 2008 Note 4 Zhigang Han7 Urnass at Amherst 1 Congruences 11 Congruence Def 1 Let m be a xed positive integer7 011 6 Z If mla E b7 we say a is congruent to b modulo m 7 and write a E 1 mod m If m l a E b7 we say a is not congruent to b modulo m 7 and write LEI modm Rink aEb modmifandonlyifabkmforsomekEZ Eg 1 77E37 mod 107 and 7737410 Prop 1 Let a7 90 E Z Then i a E a mod m ii lfa E 1 mod m7 then b E a mod m iii If a E 1 mod m7 and b E 0 mod m7 then a E 0 mod m Prop 2 Let a E a mod m and b E 13 mod m Then i abEab mod m ii aEbEaEb mod m iii a I E 01 13 mod m Rink Using iii7 one can easily show that if a E 1 mod m7 then a E 1 mod m for all n E N Eg 3 Show that 32 E 2 mod 7 for all n E N Rink Another corollary is that if a E 1 mod m then ac E be mod m The converse however does not hold in general For instance 9 5 E 5 5 mod 10 but 9 E 5 mod 10 Module Cancellation law If ac E be mod m and gcdc m 1 then a E 1 mod m Eg2 95E55 mod4andgcd541soQE5 mod4 Prop 3 a E 1 mod m if and only if a and b have the same remainders when divided by m Rink This implies that every integer must be congruent precisely to one of012 mE 1 modulo m Eg 4 What day is 22008 days from today Tests for Divisibility i A number is divisible by 9 if and only ifthe sum of its digits is divisible by 9 ii A number is divisible by 3 if and only if the sum of its digits is divisible by 3 iii A number is divisible by 11 if and only if the alternating sum of its digits is divisible by 11 12 Equivalence Relations Def 1 A relation on a set A is a subset S of A x A We say a is related to b7 and write aRb7 if 11 6 S We say a is not related to b7 and write a 1 if 11 S Eg 1 Examples of Relations i Greater Than Let A R and Sab E R x R10 gt 1 Then aRb means a gt 1 ii Divisibility Let A Z and Sa7 b E Z x Z l a divides 1 Then aRb means all iii Equality Let A be any set7 and Saa la 6 A C A x A Then aRb means a 1 iv Congruence modulo m For 071 6 Z7 aRb when a E 1 mod m Def 2 Let R be a relation on a set A i R is symmetric if aRb implies 131 ii R is transitive if aRb and bRc implies aRc iii R is re exive if aRa for all a E A Def 3 An equivalence relation on a set A is a relation R which is symmetric7 transitive and re exive Rmk When R is an equivalence relation7 we also say a is equivalent to b if aRb Eg 2 iii and iv in Eg 1 are equivalence relations7 while and ii are not Eg 3 Let R be a relation on R such that aRb if and only if ail E Q Show that R is an equivalence relation Def 4 Let R be an equivalence relation on a set A The equivalence class of a7 denoted by a7 is the subset of A consisting of all elements in A that are equivalent to a That is7 a m E AlzRa The element a is called a representative of the equivalence class a Eg 4 Let R be the relation of congruence modulo 2 Then 0 95 9520 mod 2 7472024 1 95 9521 mod 2 7371135 2 95 9522 mod 2 7472024 In fact there are only two distinct equivalence classes even integers and odd integers Any even number is a representative of 0 and any odd number is a representative of And every integer lies in exactly one congruence class Prop 4 Let R be an equivalence relation on a set A If a b E A then i a E a ii a b if and only if aRb iii a O b 0 if and only if a 1 Rink This proposition says that two equivalence classes under any equiv alence relation R are either identical or disjoint and the set of equivalence classes gives a disjoint decomposition of A as A A1 U A2 U U Ak which is called a partition of A Eg 5 Let R be a relation on A 1 2 34 such that aRb if and only if a E 1 mod 2 Show that R is an equivalence relation Then there are two distinct equivalence classes 1 1 3 and 2 2 4 which gives a partition of A as A 13 U 24 13 Modulo Arithmetic Def 5 The congruence class modulo m of the integer a is the set of integers a zEZlmEa modm The set of congruence classes of integers under the congruence relation modulo m is called the set of integers modulo m and is denoted by Zm That is 2m 0 1H21 me 1 Def 6 Modular Arithmetic Let a b E Zm We de ne the addition and the multiplication on Zm by a b a b and a 1 ab Rmk Since these operations are de ned in terms of representatives we need to show that these operations are well de ned That is the de nition is independent of the choice of representatives Show it Rmk 1 The neutral element for in Zm is 0 in the sense that 0 a a 0 a for all a E Zm The neutral element for in Zm is 1 in the sense that 1 a a 0 a for all a E Zm Eg 6 Write the addition and multiplication table for Z4 and Z5 Def 7 Let a E Zm An element 1 E Zm is called an additive inverse or a negative of a if a b b a Rmk There exists a unique additive inverse for each a E Zm In fact the negative of a is 7a Def 8 Let a E Zm be a nonzero element An element 1 E Zm is called an multiplicative inverse or simply an inverse of a if a 1 1 a Rmk The multiplicative inverse does not necessarily exist For instance 2 E Z4 does not have an inverse Prop a E Zm has an inverse if and only if gcda m 1 The inverse is unique Cor Let p be a prime Then every nonzero element a E 217 has a unique inverse Rink To nd the inverse of a in 217 one needs to solve a This means ax E 1 mod 197 which is equivalent to axpy 1 The last equation can be solved by extended Euclidean algorithm Eg 7 Find the inverse of 4 in 213 Fermat7s little Theorem Let p be a prime which does not divide a E Z Then ap l E 1 mod p Cor 1 Let p be a prime Then a E a mod p for all a E Z Cor 2 Let p be a prime Then every nonzero element a 6 217 has an inverse Rink One can de ne the subtraction in Zm using the negative7 namely7 one de ne a minus 1 to be a plus the negative of Rink lfp is a prime7 one can de ne the division in 217 using the inverse7 namely7 one de ne a divide b to be a times the inverse of ln fact7 instead of calling it a division we often directly mention it as multipli cation by the inverse77 in advanced mathematics such as the group theory

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

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