Equivalence Relations

Date: 02/10/2003 at 01:55:05
From: Minnow
Subject: Equivalence Relations

For integers m and n, define m~n if n|m^k and m|n^k for some positive 
integers j and k.

a) Prove that ~ is an equivalence relation on Z
b) Determine the equivalence classes of [1] [2] [6] and [12]
c) Give a characterization of the equivalence class [m]

Date: 02/10/2003 at 02:48:19
From: Doctor Jacques
Subject: Re: Equivalence Relations

Hi Minnow,

First, I want to make sure I understood the question correctly:

m ~ n iff we can find integers j and k such that m | n^j and n | m^k. 
(Note that you used k twice). I also assume that the integers j and k 
may depend on m and n. We could also say that m divides some power of 
n and n divides some power of m.

If this is not what you intend, please write back.

Part (a)
========

We must prove that ~ is an equivalence. As you say, we have three 
things to prove : reflexivity, symmetry, and transitivity.

The best thing to do is simply to write down explicitly what we want 
to prove.

Reflexivity
-----------

We must show that we can find j and k such that:

  m | m^j and m | m^k

This one is easy, any j and k > 0 will do.

Symmetry
--------

Assume that m | n^j and n | m^k.

We must find p, q such that

  n | m^p and m | n^q

This one is also easy, just take p = k and q = j

Transitivity
------------

Assume that:

  m | n^j and n | m^k
  n | p^r and p | n^s

We must find u and v such that:

  m | p^u  and p | m^v

I'll let you try this one, write back if you don't see it.

It is somewhat easier to tackle part (c) before part (b)

Part (c)
========

Assume that m ~ n, i.e.

  m | n^j and n | m^k

Consider a prime factor p of m. As m | n^j, this means that p | n^j, 
and therefore that p | n.
In a similar way, every prime factor of n divides m. This means that 
m and n have the same prime factors.

Conversely, assume that m and n have the same prime factors, and let 
p be one of such factors.
Assume that p^a | m and p^b | n, and that a and b are the highest 
exponents for which this is true, i.e.:

  m = p^a * m'
  n = p^b * n'

and p divides neither m' nor n'.

Assume first that m' = n' = 1, or that m = p^a and n = p^b.

We will have m | n^j iff p^a | (p^b)^j = p^(bj), i.e. if bj >= a. As 
a and b are at least 1, we can certainly find such a j. In a similar 
way, we will have n | m^k iff ak >= b, and we can also find such a k. 
To summarize, we must have:

  bj >= a
  ak >= b

Note that j and k are minimum values - any greater value will also do 
the job.

We have such a condition for each prime factor of m and n (those 
factors are the same, by hypothesis). It is therefore sufficient to 
take for j and k the least value that satisfies all these conditions, 
and this will ensure that m | n^j and n | m^k. We have thus proven 
that m ~ n.

In summary, m ~ n if and only if m and n have the same prime factors 
(possibly with different exponents).

Part (b)
========

Now that we know the meaning of "~", this should be easy...

Please do not hesitate to write back if you are still stuck.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/11/2003 at 22:54:06
From: Minnow
Subject: Equivalence Relations

I am still unable to see how (c) would work... Could you please 
explain it to me?

Date: 02/12/2003 at 02:41:47
From: Doctor Jacques
Subject: Re: Equivalence Relations

Hi Minnow, and thank you for writing again.

We want to show that equivalence classes are sets of numbers with the 
same prime factors (and different exponents for these factors).

Let the prime factorisations of m and n be:

  m = p_1^r_1 * p_2^r_2 * ...
  n = q_1^s_1 * q_2^s^2 * ...

We must show that m ~ n if and only if the p_i and q_j are the same 
set of numbers.

Assume first that m ~ n, and consider a prime factor p_i of m; we 
have p_i | m.

As there is a k such that m | n^k, p_i | n^k. Now, this implies that 
p_i | n, because, if p_i did not divide n, it could not divide n^k 
either. This shows that every prime factor of m is a prime factor of 
n (every p_i is among the q_j), and we can show in exactly the same 
way that every q_j is among the p_i. This means that the sets {p_i} 
and {q_j} are the same.

Conversely, assume that m and n have the same prime factors. We can 
rewrite the factorisations as:

  m = p_1^r_1 * p_2^r_2 * ...
  n = p_1^s_1 * p_2^s_2 * ...

We must show that m ~ n, i.e. that we can find j and k such that:

  m | n^j
  n | m^k

Consider a prime p_i. The condition m | n^j requires that:

  p_i^r_i | p_i^(j*s_i)

or

  j * s_i >= r_i.

As r_i >= 1, this will be true if and only if

  j >= j_i = ceil(s_i / r_i)

(this means the least integer such that j_i >= s_i/r_i).

We have such a condition for each prime factor p_i. If we take
j >= max (j_i), all these conditions will be satisfied, and we will 
have m | n^j.

In exactly the same way, we can find a k such that n | m^k, and we 
have thus shown that m ~ n.

As an example, let us prove that 24 ~ 18.

The prime factorisations are 24 = 2^3 * 3 and 18 = 2 * 3^2.

We must find j and k such that 24 | 18^j and 18 | 24 ^k.

  18^j = 2^j * 3^(2j)

In order to have 24 | 18^j, we must have:

  2^3 | 2^j, or j >= 3
  3 | 3^(2j), or j >= 1

Putting these conditions together, we find that it is enough to have 
j >= 3. Indeed, 18^3 = 5832 = 24 * 243.

In a similar way, in order to have 18 | 24^k, we must have:

  2 | 2^(3k), or k >= 1
  3^2 | 3^k, or k >= 2

and we see that we can take k >= 2. Indeed, 24^2 = 576 = 18 * 32.

As 24 | 18^3 and 18 | 24^2, we conclude that 24 ~ 18.

Note that, for example, 24 is not equivalent to 42, because no power 
of 24 can be divisible by 7, as 24 itself is not.

In summary, if the prime factoristation of m is:

  m = p_1^r_1 * p_2^r_2 *... * p_M^r_M

the equivalence class of m is the set of numbers:

  n = p_1^s_1 * p_2^s_2 * ... * p_M^s^M

where all the s_i are >= 1.

If we look now at part (b), we find:

[1] just contains the element 1.
[2] is the set of powers of 2 : {2, 4, 8, ...}
[6] = [12] is the set of numbers of the form 2^i*3^j, with i and j >=1

Extra credit
------------

We see that the gcd of all the numbers of an equivalence class is the 
number where all the exponents are 1. In the above example, all the 
numbers of the class [6] = [12] are multiples of 6; the converse is 
NOT true : 30 does not belong to the class.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/12/2003 at 14:09:56
From: Minnow
Subject: Equivalence Relations

Thank you so much for your prompt response... You have no idea how 
grateful I am that you are able to help me out...

Could you please help me with these equivalence classes? I am now 
understanding equivalence relations a lot better, thanks to you.

1. Let S be the set of all finite subsets of Z. Define a relation on 
   S by letting A~B if there is a bijection f: A-->B

I proved that this is an equivalence relation, but I cannot b) give a 
description of the equivalence class of {1,2,3}

2. Let S = R and say a~b if a-b is in Z

I once again proved that this is an equivalence relation, but I cannot 
describe the equivalence class. Would it be the set of all real 
numbers?

Thank you SO much.

Date: 02/13/2003 at 01:59:06
From: Doctor Jacques
Subject: Re: Equivalence Relations

Hi Minnow,

In general, you have to imagine an equivalence class as the set of 
elements equivalent to a given element.

1. There is a bijection between two finite sets if and only if they 
have the same number of elements - there are your equivalence classes.

2. A given real number a will be equivalent to x iff the difference
x-a is an integer. This means that a and x have the same integer part.

For example, we have
  2 ~ 5
  3.78 ~ 6.78
  (-3.2) ~ 5.8

Do you see the pattern ?

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/