- #1

- 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();
}
}
```

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

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

Any input would be GREATLY appreciated!