# Give the equivalence classes of this relation

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

} 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!

Delta2
Homework Helper
Gold Member
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).

Fredrik
Staff Emeritus