GATE CSE 1990 | Question: 17c

Question

Show that the elements of the lattice $(N, \leq)$, where $N$ is the set of positive intergers and $a \leq b$ if and only if $a$ divides $b$, satisfy the distributive property.

Answer 1

Distributive property is as follows:

$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$

For "divides by" lattice the meet $(\wedge)$ operation is $\gcd$ and the join $(\vee)$ operation is $lcm.$ So, we have to prove:$$ \gcd (a, lcm(b, c) )= lcm (\gcd(a,b), \gcd(a,c))$$ Forward Direction Proof:

Let $p$ be any prime factor of $ \gcd (a, lcm(b, c) )$ and $\alpha$ be the largest integer such that $p^\alpha$ divides $ \gcd (a, lcm(b, c) )$

$\implies p^\alpha$ divides $a$ and $p^\alpha$ divides $lcm(b, c).$

$\implies p^\alpha$ divides $a$ and $(p^\alpha$ divides $b$ OR $p^\alpha$ divides $c)$

$\implies (p^\alpha$ divides $a$ and $p^\alpha$ divides $b)$ OR  $(p^\alpha$ divides $a$ AND $p^\alpha$ divides $c)$

$\implies (p^\alpha$ divides $\gcd(a,b))$ OR  $(p^\alpha$ divides $\gcd(a,c))$

$\implies p^\alpha $ divides $ lcm (\gcd(a,b), \gcd(a,c))$

Reverse Direction Proof:

Let $p$ be any prime factor of $ lcm (\gcd(a,b), \gcd(a,c))$ and $\alpha$ be the largest integer such that $p^\alpha$ divides $\gcd(a,b)$ or $\gcd(a,c).$ So, $p^{\alpha}$ divides $a$ and either $b$ or $c$

$\implies p^\alpha$ divides both $a$ and $lcm(b,c).$

$\implies p^\alpha$ divides $\gcd(a, lcm(b,c))$

Hence, $ \gcd (a, lcm(b, c) )= lcm (\gcd(a,b), \gcd(a,c))$

Comments

u should include all elements of positive integers

---

you skipped elements 2 V 3 is 6 , it's set of all positive integer so u can't skip 6

---

Good Explanation sir !!

Answer 2

 we can take any example to show it distributive  and solve it. and we will find it is distributive

-----------------------------------------------------------------------------------------------------------------------

if N is square free number then it will be boolean algebra

Comments

Gurdeep Saini 

i think to dissatisfy we need only one counter and to satisfy we need to satify all conditions. 

---

@eyeamgj

Ye you are right but you can take any example and you will see it satisfy the property

---

OK THANKS