How to prove the divisors of 15 form a Boolean algebra

Question

This from Exercise 3.1 in "A Beginner's Guide to Discrete Mathematics"

Let B be the set of all positive integer divisors of 15, that is B = {1, 3, 5, 15}. Prove that B forms a Boolean algebra with zero element 1 and unity element 15, provided operations are defined as follows: x+y is the least common multiple of x and y, xy is the greatest common divisor, and x' is the ordinary arithmetical quotient 15/x

I can see by simply calculating the HCF and LCM for pairs of 1 and 15 that the following will hold.

1+1=1 1+15=15 15+1=15 15+15=15

1*1=1 1*15=1 15*1=1 15*15=15

1'=15 15'=1

So, essentially, for the two elements mentioned I have the complete truth tables for OR, AND and negation. What I don't understand is what to do about the other elements {3,5}. Do I have to somehow prove that they are also subject to the axioms of Boolean algebra? Is there perhaps a more formal method of proof I should be using to answer this question?

Answer 1

Hint:

• Write numbers in the form $3^\alpha \cdot 5^\beta$, for $\alpha,\beta \in \{0,1\}$.
• Observe, that the divisors of $15$ written in the form $\langle\alpha,\beta\rangle$ are essentially elements of $\{0,1\} \times \{0,1\}$.
• The set of all binary vectors of some length (here two) forms a Boolean algebra with operations being component-wise minimum/conjunction and maximum/disjunction.

I hope this helps $\ddot\smile$

Answer 2

It's a general fact that $\mathbb{N}$ is a distributive lattice with respect to the “divisor of” order relation: $$ a\mid b\quad\text{if and only if}\quad b=ac\text{ for some $c$}. $$ The supremum and infimum of the pair $\{a,b\}$ are the least common multiple and the greatest common divisor, respectively.

Let's see distributivity: $$ a\land(b\lor c)=(a\land b)\lor (a\land c). $$ We can exclude the cases where one of the elements is $0$, since $$ 0\land(b\lor c)=b\lor c,\qquad (0\land b)\lor(0\land c)=b\lor c $$ and $$ a\land(0\lor c)=a\land 0=a,\qquad (a\land 0)\lor(a\land c)=a\lor(a\land c)=a. $$ So, assume none of the elements is $0$ and decompose $a$, $b$ and $c$ into products of primes. This allows to transfer computations to the minimum and maximum of pairs of natural numbers and this is easily seen to be distributive.

The set $D(n)$ of divisors of a given number $n\ne0$ thus form a distributive lattice which has a maximum, $n$, and a minimum $1$, because $1$ is the minimum in $(\mathbb{N},\,|\,)$.

When is this a Boolean algebra? Exactly when $n$ is square free, that is, no square of a prime number divides $n$. Indeed, in this case, for $a\in D(n)$ we can see that $n/a$ is a complement for $a$: $$ \gcd\left(a,\frac{n}{a}\right)=1,\qquad \operatorname{lcm}\left(a,\frac{n}{a}\right)=n, $$ On the other hand, if $p^2\mid n$ ($p$ a prime), $p$ can't have a complement in $D(n)$.