×

Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

Number Theory I

by: Mrs. Preston Lehner

14

0

4

Number Theory I MATH 475

Mrs. Preston Lehner
UM
GPA 3.87

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
4
WORDS
KARMA
25 ?

Popular in Mathematics (M)

This 4 page Class Notes was uploaded by Mrs. Preston Lehner on Thursday October 29, 2015. The Class Notes belongs to MATH 475 at University of Michigan taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/231491/math-475-university-of-michigan in Mathematics (M) at University of Michigan.

×

Reviews for Number Theory I

×

×

What is Karma?

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
MATH 475 EQUIVALENCE AND CONGRUENCE HANDOU39I HARM DERKSEN This handout is about equivalence relations We apply it to the congruence of integers The notion of an equivalence relation is very general and this makes it a bit abstract 1 EQUIVALENCE RELATIONS In mathematics we often use relations For example 3 is a relation between real numbers For every two real numbers a g b is a statement wich is either true or false Other relations on the real numbers are z gt and A relatian on a set S is de ned by its property that a N b is either true or false for all 11 E 3 Example 1 Let S be the set of all subsets of Z Then g is a relation on S If A B are elements of S then A and B are subsets of Z Now A g B means that A is a subset of B Example 2 Suppose S is a group set of people Then is a parent of is a relation on 3 Some relations are special They behave very similar to the 2 symbol These are equivalence relations De nition 1 A relation on S is called an equivalence relation if it satis es the following three conditions 1 a N a for all a E S re exive property 2 if a N b then b N a for all 16 E 3 symmetry 3 if a N b and b N c then a E c transitive property for all 16 0 E 3 Example 3 Suppose that S is any set A typical example of an equivalence relation is the relation z 1 a a surel 2 if a b then b a obviousl 3 if a b and b c then a c that s clearl Example 4 Suppose that R is the set of real numbers Let us check whether 3 is an equivalence relation 1 a g 1 OK 2 if a g b then b g 1 NOT OK because 1 g 2 but 2 g 1 Date Winter 2005 2 EQUIVALENCE AND CONGRUENCE 3 ifa bandb cthenagc OK Now 3 is NOT an equivalence relation because the second property is not satis ed Example 5 Consider the relation 35 on R Let us check whether it is an equiv alence relation 1 a 1 NOT OK because a a 2 if a 35 b then 6 1 OK 3 if a b and b c then a 0 NOT OK because 0 1 and 1 0 but not 0 0 Example 6 Let S be a group of people and consider the relation live in the same house as Let us check whether this is an equivalence relation 1 a lives in the same house 1 Sure every person lives in the same house himherself 2 If a lives in the same house b then b lives in the same house 1 OK 3 If a lives in the same house b and b lives in the same house c then a lives in the same house 0 OK This shows that lives in the same house as is an equivalence relation Example 7 Let S be a set of all subsets of 1 234 5 We that A E B is true for two sets A B E S if A and B have the same number of elements For example 12 2 23 and 1 2 5 are true but 12 2 123 is false We can check that E is an equivalence relation 1 A E A because every set has the same number of elements itself 2 If A E B then B E A Yes if A and B have the same number of elements then B and A have the same number of elements 3 If A 2 B and B 2 C then A 2 C Indeed if A and B have the same number of elements and B and C have the same number of elements then A and C have the same number of elements 2 EQUIVALENCE CLASSES Suppose that N is an equivalence relation on a set S For a E S we de ne the set of all i E S for which a N 6 Proposition 1 We have abltgtab Proof 2 Suppose that a N b We would like to show that Suppose that c E Then a N c From a N 6 follows b N a property Since 6 N a and a N c we have b N 0 property By de nition 6 N 0 implies that c E So we have shown that if c E a then c E This shows that is a subset of 6 Since 6 N a we see that b g by reversing the roles of a and b We now have shown that g b and b g But then the sets and b are equal PROBLEM SET 1 3 E Suppose that Since 6 E 6 property 1 we have b E Because b we also have b E But i E means by de nition that a N b II We call the equivalence class of 1 Proposition 2 If b then the sets and 6 d0 net have anything in common M f b W Proof Suppose that 0 b is not empty Assume that c E and c E From 0 E follows that a N c and Similarly from c E 6 follows that b But then Example 8 If we consider the equivalence relation quot on a set S then for all a E S This example is not so interesting Example 9 Suppose that S is a group of people and we consider the equivalence relation live in the same house as If a E S is one of the people then is the set of all people of 3 who live in the same house as a We may identify the equivalence classes in this case with the various houses Each house corresponds to an equivalence class Example 10 Let S be a set of all subsets of 1 2 3 4 We that A 2 B is true for two sets A B E S if A and B have the same number of elements There are exactly 5 equivalence classes namely W 0 MIN 1 2 3 4 Will H13 1 31 42 3g2i4g3g4 123 12 3 124 134 2 34 12 3 4 1234 3 CONGRUENCE De nition 2 We that a and b are congruent modulo m if m divides a b We will write a E b modm if a and b are congruent modulo m We now easily verify the three properties of an equivalence relation 1 a E a mod m because m 0 a a 2 If a E 6 mod m then b E a mod m Indeed if a E 6 mod m then m a b But then m a b b a SobEa mod m 3 If a E 6 mod m and b E 0 mod m then a E 0 mod m If a E 6 mod m and b E 0 mod m then m divides a b and b 0 But then m also divides a b b c a 0 Hence a E 0 mod m 4 EQUIVALENCE AND CONGRUENCE The equivalence class of a with respect to the equivalence relation E mod m will be denoted by We also call the congruence elass modulo m We have that Mm a 2ma maama2m amZ For example 0 4 2024 is the set of all even numbers The set 1 3 1135 consists of all odd numbers For any even number 71 we have 71 0 For any odd number 71 we have 72 1 This means that there are only 2 congruence classes modulo 2 Proposition 3 Suppose that m is a positive integer The congruence classes modulo m are exactly 0 1 m 1m Proof Suppose that a is an integer Then we can write a qm r with 0 3 r lt m Since m 1 r 1m we have that a E rm0dm and This shows that Who lllm l7n llm are all equivalence classes They are actually distinct suppose that for some i and j with 0 3 i lt m and 0 3 j lt m Then i E jmodm and m divides i j But m lt i j lt m We must have i j 0 or equivalently i j This shows that Who lllm l7n llm are distinct 1 The set of equivalence classes modulo m is often denoted by ZmZ or Zm So ZmZ HUD 1 m 1m has exactly m elements For example ZQZ 0212 evenodd 4 SUMS AND PRODUCTS ou may have heard sayings like odd plus odd is even or even times odd is even This means that the sum of two odd numbers is always and even number regardless what the two odd numbers are We can make an addition and a multiplication table even odd v even odd even even odd even even even odd odd even odd even odd

×

25 Karma

×

×

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

Jim McGreen Ohio University

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

Amaris Trozzo George Washington University

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

Jim McGreen Ohio University

Forbes

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

Become an Elite Notetaker and start selling your notes online!
×

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