Give the equivalence classes of this relation

In summary, the equivalence classes of the relation aRb if and only if a^4 ≡ b^4 (mod 30) on the set {1, 2, 3, . . . , 15} can be found by using computer software or by hand, making use of a shortcut involving transitivity, reflexivity, and symmetry. The relation is an equivalence relation, and there are 137 ordered pairs in the relation.
  • #1
s3a
818
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!
 
Physics news on Phys.org
  • #2
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).
 
  • #3
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
Thanks guys! :)
 

1. What are equivalence classes in relation to scientific research?

Equivalence classes refer to a grouping of elements or objects in a relation that share a common property or characteristic. In scientific research, this can be used to classify data or subjects based on certain criteria.

2. How are equivalence classes determined in a relation?

Equivalence classes are determined by identifying elements in a relation that have the same value or satisfy the same condition. These elements are then grouped together to form an equivalence class.

3. What is the importance of identifying equivalence classes in a relation?

Identifying equivalence classes in a relation allows for better organization and understanding of data. It can also help in identifying patterns or trends within the data.

4. Can equivalence classes change over time in a relation?

Yes, equivalence classes can change over time as new data is added to the relation. This may result in the formation of new equivalence classes or the merging of existing ones.

5. How do equivalence classes impact statistical analysis in scientific research?

Equivalence classes can impact statistical analysis by providing a clearer understanding of the data and helping researchers to make more accurate conclusions. They can also be used in statistical tests, such as ANOVA, to compare groups within a relation.

Similar threads

Determine whether the integer 701 is prime by testing?
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....
    • Calculus and Beyond Homework Help
Replies
15
Views
2K
Find the correct value of the mean in the given problem
    • Calculus and Beyond Homework Help
Replies
4
Views
756
I What is the missing number in this number sequence pattern?
    • General Math
Replies
3
Views
459
Divisibility of Integers ## 176521221 ## & ## 149235678 ## by 9 & 11
    • Precalculus Mathematics Homework Help
Replies
9
Views
1K
Find the two points on the curve that share a tangent line
    • Calculus and Beyond Homework Help
Replies
9
Views
1K
I Solve the system of linear equations
    • Linear and Abstract Algebra
Replies
2
Views
390
MCNP Problem - Bad character in column 2
    • Nuclear Engineering
Replies
7
Views
2K
Bernoulli and Bayesian probabilities
    • Calculus and Beyond Homework Help
Replies
4
Views
1K
Unique factoring over E-Primes criteria
    • Calculus and Beyond Homework Help
Replies
7
Views
1K

Hot Threads

Recent Insights

Back
Top