Give the equivalence classes of this relation

[s3a]

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

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

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!

 

[Delta2]

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 won't 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 isn't 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 a lot fewer than what you think they were and the whole process to terminate faster (both by hand and by program).

 

[Fredrik]

Delta² 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.

 

[s3a]

Thanks guys! :)