Give the equivalence classes of this relation

  • Thread starter s3a
  • Start date
  • #1
s3a
805
8

Homework Statement


Give the equivalence classes of the relation aRb if and only if a^4 ≡ b^4 (mod 30) on the set {1, 2, 3, . . . , 15}.

Homework Equations


Definition of modular arithmetic.

Definition of equivalence class.

The Attempt at a Solution


I can successfully do this problem using computer software, but I am supposed to be able to do it in a reasonable amount of time by hand, and I can't. My teacher said something about making use of a shortcut involving transitivity (and I'm assuming reflexivity and symmetry as well, since if I'm correct, the relation is supposed to be an equivalence relation), however I didn't grasp exactly what he meant.

Here is the code
Code:
import java.awt.Point;
import java.util.ArrayList;


public class ShortProgram {
   
   public static void findEquivalenceRelation() {
     
     ArrayList<Point> theRelation = new ArrayList<Point>();
     
     int counter = 0;
     
     for(int a = 1; a <= 15; a++) {
       
       for(int b = 1; b <= 15; b++) {
         
         if( (a*a*a*a - b*b*b*b) % 30 == 0) {
           
           System.out.println(a + "^4 - " + b + "^4 IS divisible by 30.");
           theRelation.add(new Point(a,b));
           
         } else {
           
           System.out.println(a + "^4 - " + b + "^4 is NOT divisible by 30.");
         }
         
         counter++;
       }
     }
     
     System.out.println("There were " + counter + " computations.");
     
     System.out.println();
     
     int amountOfOrderedPairs = 0;
     
     String str = "";
     
     for(int i = 0; i < theRelation.size() - 1; i++) {
       
       Point p = theRelation.get(i);
       
       amountOfOrderedPairs++;
       str += ( "(" + (int) p.getX() + "," + (int) p.getY() + "), " );
     }
     
     
       
     Point p = theRelation.get(theRelation.size() - 1);
     amountOfOrderedPairs++;
     str += ( "(" + (int) p.getX() + "," + (int) p.getY() + ")" );
     
     System.out.println("{" + str.trim() + "}");
     
     System.out.println("There are " + amountOfOrderedPairs + " ordered pairs in the relation.");
   }

   public static void main(String[] args) {
     
     ShortProgram.findEquivalenceRelation();
   }
}
and here is the output of that code

Code:
1^4 - 1^4 IS divisible by 30.
1^4 - 2^4 is NOT divisible by 30.
1^4 - 3^4 is NOT divisible by 30.
1^4 - 4^4 is NOT divisible by 30.
1^4 - 5^4 is NOT divisible by 30.
1^4 - 6^4 is NOT divisible by 30.
1^4 - 7^4 IS divisible by 30.
1^4 - 8^4 is NOT divisible by 30.
1^4 - 9^4 is NOT divisible by 30.
1^4 - 10^4 is NOT divisible by 30.
1^4 - 11^4 IS divisible by 30.
1^4 - 12^4 is NOT divisible by 30.
1^4 - 13^4 IS divisible by 30.
1^4 - 14^4 is NOT divisible by 30.
1^4 - 15^4 is NOT divisible by 30.
2^4 - 1^4 is NOT divisible by 30.
2^4 - 2^4 IS divisible by 30.
2^4 - 3^4 is NOT divisible by 30.
2^4 - 4^4 IS divisible by 30.
2^4 - 5^4 is NOT divisible by 30.
2^4 - 6^4 is NOT divisible by 30.
2^4 - 7^4 is NOT divisible by 30.
2^4 - 8^4 IS divisible by 30.
2^4 - 9^4 is NOT divisible by 30.
2^4 - 10^4 is NOT divisible by 30.
2^4 - 11^4 is NOT divisible by 30.
2^4 - 12^4 is NOT divisible by 30.
2^4 - 13^4 is NOT divisible by 30.
2^4 - 14^4 IS divisible by 30.
2^4 - 15^4 is NOT divisible by 30.
3^4 - 1^4 is NOT divisible by 30.
3^4 - 2^4 is NOT divisible by 30.
3^4 - 3^4 IS divisible by 30.
3^4 - 4^4 is NOT divisible by 30.
3^4 - 5^4 is NOT divisible by 30.
3^4 - 6^4 is NOT divisible by 30.
3^4 - 7^4 is NOT divisible by 30.
3^4 - 8^4 is NOT divisible by 30.
3^4 - 9^4 IS divisible by 30.
3^4 - 10^4 is NOT divisible by 30.
3^4 - 11^4 is NOT divisible by 30.
3^4 - 12^4 is NOT divisible by 30.
3^4 - 13^4 is NOT divisible by 30.
3^4 - 14^4 is NOT divisible by 30.
3^4 - 15^4 is NOT divisible by 30.
4^4 - 1^4 is NOT divisible by 30.
4^4 - 2^4 IS divisible by 30.
4^4 - 3^4 is NOT divisible by 30.
4^4 - 4^4 IS divisible by 30.
4^4 - 5^4 is NOT divisible by 30.
4^4 - 6^4 is NOT divisible by 30.
4^4 - 7^4 is NOT divisible by 30.
4^4 - 8^4 IS divisible by 30.
4^4 - 9^4 is NOT divisible by 30.
4^4 - 10^4 is NOT divisible by 30.
4^4 - 11^4 is NOT divisible by 30.
4^4 - 12^4 is NOT divisible by 30.
4^4 - 13^4 is NOT divisible by 30.
4^4 - 14^4 IS divisible by 30.
4^4 - 15^4 is NOT divisible by 30.
5^4 - 1^4 is NOT divisible by 30.
5^4 - 2^4 is NOT divisible by 30.
5^4 - 3^4 is NOT divisible by 30.
5^4 - 4^4 is NOT divisible by 30.
5^4 - 5^4 IS divisible by 30.
5^4 - 6^4 is NOT divisible by 30.
5^4 - 7^4 is NOT divisible by 30.
5^4 - 8^4 is NOT divisible by 30.
5^4 - 9^4 is NOT divisible by 30.
5^4 - 10^4 is NOT divisible by 30.
5^4 - 11^4 is NOT divisible by 30.
5^4 - 12^4 is NOT divisible by 30.
5^4 - 13^4 is NOT divisible by 30.
5^4 - 14^4 is NOT divisible by 30.
5^4 - 15^4 is NOT divisible by 30.
6^4 - 1^4 is NOT divisible by 30.
6^4 - 2^4 is NOT divisible by 30.
6^4 - 3^4 is NOT divisible by 30.
6^4 - 4^4 is NOT divisible by 30.
6^4 - 5^4 is NOT divisible by 30.
6^4 - 6^4 IS divisible by 30.
6^4 - 7^4 is NOT divisible by 30.
6^4 - 8^4 is NOT divisible by 30.
6^4 - 9^4 is NOT divisible by 30.
6^4 - 10^4 is NOT divisible by 30.
6^4 - 11^4 is NOT divisible by 30.
6^4 - 12^4 IS divisible by 30.
6^4 - 13^4 is NOT divisible by 30.
6^4 - 14^4 is NOT divisible by 30.
6^4 - 15^4 is NOT divisible by 30.
7^4 - 1^4 IS divisible by 30.
7^4 - 2^4 is NOT divisible by 30.
7^4 - 3^4 is NOT divisible by 30.
7^4 - 4^4 is NOT divisible by 30.
7^4 - 5^4 is NOT divisible by 30.
7^4 - 6^4 is NOT divisible by 30.
7^4 - 7^4 IS divisible by 30.
7^4 - 8^4 is NOT divisible by 30.
7^4 - 9^4 is NOT divisible by 30.
7^4 - 10^4 is NOT divisible by 30.
7^4 - 11^4 IS divisible by 30.
7^4 - 12^4 is NOT divisible by 30.
7^4 - 13^4 IS divisible by 30.
7^4 - 14^4 is NOT divisible by 30.
7^4 - 15^4 is NOT divisible by 30.
8^4 - 1^4 is NOT divisible by 30.
8^4 - 2^4 IS divisible by 30.
8^4 - 3^4 is NOT divisible by 30.
8^4 - 4^4 IS divisible by 30.
8^4 - 5^4 is NOT divisible by 30.
8^4 - 6^4 is NOT divisible by 30.
8^4 - 7^4 is NOT divisible by 30.
8^4 - 8^4 IS divisible by 30.
8^4 - 9^4 is NOT divisible by 30.
8^4 - 10^4 is NOT divisible by 30.
8^4 - 11^4 is NOT divisible by 30.
8^4 - 12^4 is NOT divisible by 30.
8^4 - 13^4 is NOT divisible by 30.
8^4 - 14^4 IS divisible by 30.
8^4 - 15^4 is NOT divisible by 30.
9^4 - 1^4 is NOT divisible by 30.
9^4 - 2^4 is NOT divisible by 30.
9^4 - 3^4 IS divisible by 30.
9^4 - 4^4 is NOT divisible by 30.
9^4 - 5^4 is NOT divisible by 30.
9^4 - 6^4 is NOT divisible by 30.
9^4 - 7^4 is NOT divisible by 30.
9^4 - 8^4 is NOT divisible by 30.
9^4 - 9^4 IS divisible by 30.
9^4 - 10^4 is NOT divisible by 30.
9^4 - 11^4 is NOT divisible by 30.
9^4 - 12^4 is NOT divisible by 30.
9^4 - 13^4 is NOT divisible by 30.
9^4 - 14^4 is NOT divisible by 30.
9^4 - 15^4 is NOT divisible by 30.
10^4 - 1^4 is NOT divisible by 30.
10^4 - 2^4 is NOT divisible by 30.
10^4 - 3^4 is NOT divisible by 30.
10^4 - 4^4 is NOT divisible by 30.
10^4 - 5^4 is NOT divisible by 30.
10^4 - 6^4 is NOT divisible by 30.
10^4 - 7^4 is NOT divisible by 30.
10^4 - 8^4 is NOT divisible by 30.
10^4 - 9^4 is NOT divisible by 30.
10^4 - 10^4 IS divisible by 30.
10^4 - 11^4 is NOT divisible by 30.
10^4 - 12^4 is NOT divisible by 30.
10^4 - 13^4 is NOT divisible by 30.
10^4 - 14^4 is NOT divisible by 30.
10^4 - 15^4 is NOT divisible by 30.
11^4 - 1^4 IS divisible by 30.
11^4 - 2^4 is NOT divisible by 30.
11^4 - 3^4 is NOT divisible by 30.
11^4 - 4^4 is NOT divisible by 30.
11^4 - 5^4 is NOT divisible by 30.
11^4 - 6^4 is NOT divisible by 30.
11^4 - 7^4 IS divisible by 30.
11^4 - 8^4 is NOT divisible by 30.
11^4 - 9^4 is NOT divisible by 30.
11^4 - 10^4 is NOT divisible by 30.
11^4 - 11^4 IS divisible by 30.
11^4 - 12^4 is NOT divisible by 30.
11^4 - 13^4 IS divisible by 30.
11^4 - 14^4 is NOT divisible by 30.
11^4 - 15^4 is NOT divisible by 30.
12^4 - 1^4 is NOT divisible by 30.
12^4 - 2^4 is NOT divisible by 30.
12^4 - 3^4 is NOT divisible by 30.
12^4 - 4^4 is NOT divisible by 30.
12^4 - 5^4 is NOT divisible by 30.
12^4 - 6^4 IS divisible by 30.
12^4 - 7^4 is NOT divisible by 30.
12^4 - 8^4 is NOT divisible by 30.
12^4 - 9^4 is NOT divisible by 30.
12^4 - 10^4 is NOT divisible by 30.
12^4 - 11^4 is NOT divisible by 30.
12^4 - 12^4 IS divisible by 30.
12^4 - 13^4 is NOT divisible by 30.
12^4 - 14^4 is NOT divisible by 30.
12^4 - 15^4 is NOT divisible by 30.
13^4 - 1^4 IS divisible by 30.
13^4 - 2^4 is NOT divisible by 30.
13^4 - 3^4 is NOT divisible by 30.
13^4 - 4^4 is NOT divisible by 30.
13^4 - 5^4 is NOT divisible by 30.
13^4 - 6^4 is NOT divisible by 30.
13^4 - 7^4 IS divisible by 30.
13^4 - 8^4 is NOT divisible by 30.
13^4 - 9^4 is NOT divisible by 30.
13^4 - 10^4 is NOT divisible by 30.
13^4 - 11^4 IS divisible by 30.
13^4 - 12^4 is NOT divisible by 30.
13^4 - 13^4 IS divisible by 30.
13^4 - 14^4 is NOT divisible by 30.
13^4 - 15^4 is NOT divisible by 30.
14^4 - 1^4 is NOT divisible by 30.
14^4 - 2^4 IS divisible by 30.
14^4 - 3^4 is NOT divisible by 30.
14^4 - 4^4 IS divisible by 30.
14^4 - 5^4 is NOT divisible by 30.
14^4 - 6^4 is NOT divisible by 30.
14^4 - 7^4 is NOT divisible by 30.
14^4 - 8^4 IS divisible by 30.
14^4 - 9^4 is NOT divisible by 30.
14^4 - 10^4 is NOT divisible by 30.
14^4 - 11^4 is NOT divisible by 30.
14^4 - 12^4 is NOT divisible by 30.
14^4 - 13^4 is NOT divisible by 30.
14^4 - 14^4 IS divisible by 30.
14^4 - 15^4 is NOT divisible by 30.
15^4 - 1^4 is NOT divisible by 30.
15^4 - 2^4 is NOT divisible by 30.
15^4 - 3^4 is NOT divisible by 30.
15^4 - 4^4 is NOT divisible by 30.
15^4 - 5^4 is NOT divisible by 30.
15^4 - 6^4 is NOT divisible by 30.
15^4 - 7^4 is NOT divisible by 30.
15^4 - 8^4 is NOT divisible by 30.
15^4 - 9^4 is NOT divisible by 30.
15^4 - 10^4 is NOT divisible by 30.
15^4 - 11^4 is NOT divisible by 30.
15^4 - 12^4 is NOT divisible by 30.
15^4 - 13^4 is NOT divisible by 30.
15^4 - 14^4 is NOT divisible by 30.
15^4 - 15^4 IS divisible by 30.
There were 225 computations.

{(1,1), (1,7), (1,11), (1,13), (2,2), (2,4), (2,8), (2,14), (3,3), (3,9), (4,2), (4,4), (4,8), (4,14), (5,5), (6,6), (6,12), (7,1), (7,7), (7,11), (7,13), (8,2), (8,4), (8,8), (8,14), (9,3), (9,9), (10,10), (11,1), (11,7), (11,11), (11,13), (12,6), (12,12), (13,1), (13,7), (13,11), (13,13), (14,2), (14,4), (14,8), (14,14), (15,15)}
There are 43 ordered pairs in the relation.
Then, after having found the equivalence relation, I would have to find the equivalence class of 1, [1], then the equivalence class of 2, [2], all the way to the equivalence class of 15, [15].

How can I do this in a faster way, without making use of a computer?

Any input would be GREATLY appreciated!
 

Answers and Replies

  • #2
Delta2
Homework Helper
Insights Author
Gold Member
3,533
1,360
There is something you obviously didnt take notice even when you made the program. That is when we find that an element a is equivalent to say elements b,c,d and e, then we can erase b,c,d and e from the queue and we ll do no calculations for them cause we already know that they belong in the equivalence class of a (because the equivalence relation is transitive and symmetric). Or to state it more accurate, the equivalence class of a is the same as that of b, when a and b are equivalent.

So for example you start with calculating by hand for 1, and you find that is equivalent to 7, 11, 13. This means that you wont have to do calculations for 7,11 and 13, so its like only 15-4=11 elements left to do calculations for. Then you go do calculations for 2 (which is still in the queue cause it isnt equivalent with 1) and you find 2 is equiv with 4 8 and 14, so you erase another 4 elements. So you see that after doing calculations only for the first two elements, you already have done calculations essentially for 8 elements in total. I think it should be obvious to you now how the calculations can be alot fewer than what you think they were and the whole process to terminate faster (both by hand and by program).
 
  • #3
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,851
413
Delta2 said what I was going to say, so I'll just add that it's a good exercise to prove as a theorem that every equivalence relation partitions the set in the sense that each element of the set belongs to exacly one equivalence class.
 
  • #4
s3a
805
8
Thanks guys! :)
 

Related Threads on Give the equivalence classes of this relation

  • Last Post
Replies
3
Views
1K
Replies
0
Views
1K
Replies
0
Views
1K
Replies
1
Views
789
Replies
2
Views
4K
  • Last Post
Replies
4
Views
1K
Replies
2
Views
409
  • Last Post
Replies
3
Views
968
  • Last Post
Replies
7
Views
3K
Top