1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Give the equivalence classes of this relation

  1. Apr 10, 2015 #1

    s3a

    User Avatar

    1. The problem statement, all variables and given/known data
    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}.

    2. Relevant equations
    Definition of modular arithmetic.

    Definition of equivalence class.

    3. 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 (Text):

    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 (Text):

    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!
     
  2. jcsd
  3. Apr 10, 2015 #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 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).
     
  4. Apr 10, 2015 #3

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  5. Apr 11, 2015 #4

    s3a

    User Avatar

    Thanks guys! :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted