I'm getting back into basic proofs after a long hiatus, and I know something has to be wrong with the following logic but I'm not sure what.

Elements of arithmetic progressions can be expressed as:

$a_n = a_0 + nd_a$

Where $a_n$ is the $n$th element of the progression and $d_a$ is the constnt difference or 'step.' Note that typically it's written with $(n - 1)d_b$ and indexed from 1 but as a programmer I find that silly. Now, Bezout's identity states any linear combination is equal to a multiple of the gcd of the two numbers being combined, so it follows that:

$a_0 + nd_a = gcd(a_0, d_a) * k$

Where $k$ is used to represent some satisfying multiple. We can rewrite this as an assertion about divisibility:

$gcd(a_0, d_a) \mid a_0 + nd_a$

Then since you can reverse any divisibility formula and swap $lcm$ for $gcd$:

$a_0 + nd_a \mid lcm(a_0, d_a)$

But I know this can't be true based on a simple counter example. Consider the progression that starts at 3 and increments by 4: $3, 7, 11, ...$

Our formula states that all numbers in the progression have to divide $lcm(3, 4) = 12$, which is not true for 7 or 11. There needs to be a growing coefficient for the lcm, but I'm not sure where it would have come in. An assumption in the proof for being able to swap lcm/gcd in divisibility formulas that I'm breaking?

  • 3
    $\begingroup$ No, you simply cannot "reverse any divisibility formula and swap lcm for gcd". Do you have any exact theorem stating something like that? Does it behave well with $\forall$ and $\exists $ around? $\endgroup$ – Hagen von Eitzen Oct 13 '12 at 19:05
  • $\begingroup$ I'm going based on it saying that in the Lattice Theoretic section in the Wikipedia article on Least Common Multiple, link: en.wikipedia.org/wiki/Least_common_multiple#Lattice-theoretic . Wouldn't be the first time Wikipedia was wrong but I'm guessing I'm misinterpreting it somehow. $\endgroup$ – Joseph Garvin Oct 13 '12 at 19:17
  • $\begingroup$ The elements of an arithmetic progression with common difference other than zero eventually increase in absolute value beyond any finite limit. The idea that they are all factors of some finite number is therefore mistaken. There is an incorrect assumption in the question. $\endgroup$ – Mark Bennet Oct 13 '12 at 19:45
  • $\begingroup$ @MarkBennet: As I stated, I know the conclusion is wrong, my question is what is the incorrect assumption I've made? Hagen suggests it's the application of the gcd/lcm divisibility swap, but I'd like to know the limits then of when I can and can't use it. $\endgroup$ – Joseph Garvin Oct 13 '12 at 20:05
  • $\begingroup$ I think the limit is "don't use it if you don't understand it" - but there are some constructive suggestions about to promote understanding. $\endgroup$ – Mark Bennet Oct 13 '12 at 20:12

You’re looking at this statement in the Wikipedia article:

If a formula involving integer variables, $\mathbf{gcd}$, $\mathbf{lcm}$, $\le$ and $\ge$ is true, then the formula obtained by switching $\mathbf{gcd}$ with $\mathbf{lcm}$ and switching $\ge$ with $\le$ is also true. (Remember $\le$ is defined as divides).

As you suspected, the problem is with your interpretation, though the statement could certainly be improved, by making clear just what kinds of formula are involved.

First, to see that the obvious, naïve interpretation can’t be right, consider the statement $$\gcd(2,3)\mid n$$ (where I use the usual symbol for divides). This is clearly true for every integer $n$. Now look at what you get when you replace $\gcd$ by $\text{lcm}$ and turn the divisibility relation around: $$n\mid\operatorname{lcm}(2,3)\;,$$ which is clearly false for every $n>6$.

The word formula in the quotation isn’t intended to refer to statements about specific integers. Rather, it’s intended to refer to general statements about divisibility of integers, $\gcd$, and $\text{lcm}$ that are translations of general lattice identities involving the lattice order, meets, and joins into the specific setting of the integer divisibility lattice. The laws that follow the quotation in the article are examples of this type of statement, provided that you realize that they’re intended to be understood as universally quantified statements. For instance, the absorption laws should read

$$\forall a,b\in\Bbb N\Big(\operatorname{lcm}\big(a,\gcd(a,b)\big)=a\Big)\tag{1}$$

and its dual

$$\forall a,b\in\Bbb N\Big(\gcd\big(a,\operatorname{lcm}(a,b)\big)=a\Big)\;.\tag{2}$$

These are merely the statement for this specific lattice of the general lattice properties

$$\forall a,b\in L\Big(a\lor(a\land b)=a\Big)\tag{3}$$ and its dual $$\forall a,b\in L\Big(a\land(a\lor b)=a\Big)\;,\tag{4}$$ where $L$ is the lattice in question.

In the lattice whose elements are subsets of some set $X$, with order relation $\subseteq$ and $\cap$ and $\cup$ for meet and join, respectively, they translate to

$$\forall A,B\in\wp(X)\Big(A\cup(A\cap B)=A\Big)\tag{5}$$ and $$\forall A,B\in\wp(X)\Big(A\cap(A\cup B)=A\Big)\;.\tag{6}$$

The dual absorption laws $(1)$ and $(2)$, and the dual absorption laws $(5)$ and $(6)$, are the statements of the general lattice-theoretic dual absorption laws $(3)$ and $(4)$ specialized to the divisibility lattice and a power set lattice, respectively. But even when specialized to the particular settings, they are still general structural statements reflecting general lattice-theoretic facts, not specific statements about specific elements of specific lattices.

  • $\begingroup$ Ah, so the problem isn't that they don't work with ∀ and ∃, it's that they only work with ∀ and ∃. $\endgroup$ – Joseph Garvin Oct 13 '12 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.