Associated Topics || Dr. Math Home || Search Dr. Math

### Relations and Equivalence Classes

```
Date: 01/10/99 at 11:04:19
From: Emma Warren
Subject: Relations and Equivalence classes

Hi Dr. Math,

I'm hoping you can help me again. The question is:

The following relations are defined on the set of integers

1) a~b if and only if a^2-b^2 is divisible by 5
2) a~b if and only if a+2b is divisible by 3

Show that each of these is an equivalence relation, and determine
the equivalence classes under each relation.

I know that for the relation to be an equivalence relation it must be
reflexive, symmetric, and transitive.

The second relation seems fairly easy and precise. Here's how I tried
it:

Reflexive test:

Is a~a for all a in the set of integers?
a~a if and only if a+2a is divisible by 3
Since a+2a = 3a is divisible by 3, the relationship is reflexive.

Symmetric test;

If a~b, then a+2b is divisible by 3. So a+2b = 3N (where N is in
the set of integers). Thus a = 3N - 2b. So:

b+2a = b+2(3N-2b)
= b+6N-4b
= 6N-3b
= 3(2N-b)  - this is divisible by 3

So, b+2a is divisible by 3. Thus b~a and the relation is symmetric.

Transitive test:

If a~b and b~c, then:

a+2b = 3N  (where N is in the set of integers)
b+2c = 3M  (where M is in the set of integers)

a+3b+2c = 3N+3M
a+2c = 3N+3M-3b
a+2c = 3(N+m-b)  - this is divisible by 3
So, a+2c is divisible by 3. Thus a~c and the relation is
transitive.

The relation has all three properties and so is an equivalence
relation.

I'm having trouble with the second one though. I hope you can clear up
the way in which I have to do these sorts of questions.

Thanks again,
Emma
```

```
Date: 01/11/99 at 14:25:53
From: Doctor Teeple
Subject: Re: Relations and Equivalence classes

Hi Emma,

Thanks for writing to Dr. Math.

You did a fabulous job of proving the second equivalence relation! You
have the right idea, and the first equivalence relation is very
similar. I'll give you some hints about what will happen as you try to
prove the three requirements. Bear with me if you've already gotten
them:

Reflexivity:
Is 0 divisible by 5? You can think of it this way - what do you get
when you divide 0 by 5? Is there a remainder? No. So yes, 0 is
divisible by 5. This may seem like cheating because you can replace the
5 by any number in the previous questions, but all that says is that 0
is divisible by any number.

Symmetry:
When you prove symmetry, you assume that a^2 - b^2 is divisible by 5.
What do you get when you factor out a negative? If a number is
divisible by 5, is its negative divisible by 5?

Transitivity:
From your assumptions, you know that a^2 - b^2 and b^2 - c^2 are
divisible by 5. When you add two numbers divisible by 5, is the sum
divisible by 5? Try it with a few numbers if you're not sure.

To find the equivalence classes, you want to get an idea of which
numbers are equivalent to each other. The best way to find this out is
to just do some examples. I'll help with the first one. Keeping in mind
that a~b if and only if a^2-b^2 is divisible by 5, try listing the
squares and then subtracting. First, here are the squares of the first
few digits:

1   4   9   16   25   36   49   64   81   100   121   144 ...

If b = 1, and a = 2, 3, 4, 5, 6, . . ., here are a^2 - b^2:

a    | 2   3    4    5    6    7    8    9   10    11    12
a^2 - b^2 | 3   8   15   24   35   48   63   80   99   120   143 ...

By looking for those that are divisible by 5, we see that 1 is
equivalent to 4, 6, 9, and 11. Thus, one equivalence class consists of
at least 1, 4, 6, 9, and 11. There are more, and we'll look for the
general pattern a little later on.

If b = 2, and a = 3, 4, 5, 6, 7, ..., we get for a^2 - b^2:

5   12   21   32   45   60   77   96   117   140 ...

From this we see that 2 is equivalent to 3, 7, 8, and 12. So another
equivalence class contains 2, 3, 7, 8, 12, . . . .

So far we have the following two equivalence classes:

1, 4, 6, 9, 11, . . .
2, 3, 7, 8, 12, . . .

Which numbers are we missing? The multiples of 5. Does it make sense
that the multiples of 5 will be in their own equivalence relation? Try
squaring and subtracting them to see that you will get a multiple of 5.
Among the three classes, we've accounted for all of the integers.

Now, what is the pattern of the other two equivalence classes? To see
it, try this method. Write down the integers from 1 to 16. Draw a box
around the multiples of 5 and circle all those that are in the first
equivalence class above (i.e.: all those equivalent to 1). Look how the
circled ones and the non-circled ones relate to the multiples of 5. You
should have something like:

circle plain plain circle box

and the pattern repeats. This may seem simplistic but it's a good way
to see what's going on.

More technically (which you can skip if you only need the above or
haven't studied modular aritmetic), we're looking for integers whose
squares are equivalent to mod 5. (I'll use = for equivalence). So:

a^2 = b^2 (mod 5)

The circled ones are those where:

a^2 = b^2 = 1 (mod 5)

that is, if you square them and divide by 5, you get a remainder of 1.

The plain ones are those where:

a^2 = b^2 = 4 (mod 5)

And the boxed ones are those where:

a^2 = b^2 = 0 (mod 5)

So in each case, a^2 - b^2 = 0 (mod 5), which means a^2 - b^2 is a
multiple of 5.

Basically, the above is a complicated way of saying try a few numbers
to see what will be equivalent. That's the most direct way of looking
for the equivalence classes. Note that while I didn't address negative
numbers, they should also be included.

If you didn't understand any of the above or need help on anything
else, please write back. Good luck!

- Doctor Teeple, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search