module Data.Nat.Divisible where

Divisibility of natural numbersπŸ”—

In the natural numbers, divisibility1 is the property expressing that a given number can be expressed as a multiple of another, and we write 2 when there exists some such that

Note the use of an existential quantifier, which is a bit annoying: For divisibility to truly be a property, we must work under a truncation, since otherwise there would be proofs that since for any we have To avoid this sticky situation, we define divisibility with a single step of indirection:

_∣_ : Nat β†’ Nat β†’ Type
zero  ∣ y = y ≑ zero
suc x ∣ y = fibre (_* suc x) y

infix 7 _∣_

In this way, we break the pathological case of by decreeing it to be the (contractible) type Every other natural number is already handled, because the function β€œβ€ is injective. With this indirection, we can prove that divisibility is a mere property:

∣-is-prop : βˆ€ x y β†’ is-prop (x ∣ y)
∣-is-prop zero y n k = prop!
∣-is-prop (suc x) y (n , p) (n' , q) = Ξ£-prop-path! (*-suc-inj x n n' (p βˆ™ sym q))

instance
  H-Level-∣ : βˆ€ {x y} {n} β†’ H-Level (x ∣ y) (suc n)
  H-Level-∣ = prop-instance (∣-is-prop _ _)
  {-# INCOHERENT H-Level-∣ #-}

The type is, in fact, the propositional truncation of β€” and it is logically equivalent to that type, too!

∣-is-truncation : βˆ€ {x y} β†’ (x ∣ y) ≃ βˆ₯ fibre (_* x) y βˆ₯
∣-is-truncation {zero} {y} =
  prop-ext!
    (Ξ» p β†’ inc (y , *-zeror y βˆ™ sym p))
    (rec! Ξ» x p β†’ sym p βˆ™ *-zeror x )
∣-is-truncation {suc x} {y} = Equiv.to is-prop≃equivβˆ₯-βˆ₯ (∣-is-prop (suc x) y)

βˆ£β†’fibre : βˆ€ {x y} β†’ x ∣ y β†’ fibre (_* x) y
βˆ£β†’fibre {zero} wit  = 0 , sym wit
βˆ£β†’fibre {suc x} wit = wit

fibreβ†’βˆ£ : βˆ€ {x y} β†’ fibre (_* x) y β†’ x ∣ y
fibreβ†’βˆ£ f = Equiv.from ∣-is-truncation (inc f)

divides : βˆ€ {x y} (q : Nat) β†’ q * x ≑ y β†’ x ∣ y
divides x p = fibreβ†’βˆ£ (x , p)

As an orderingπŸ”—

The notion of divisibility equips the type with yet another partial order, i.e., the relation is reflexive, transitive, and antisymmetric. We can establish the former two directly, but antisymmetry will take a bit of working up to:

∣-refl : βˆ€ {x} β†’ x ∣ x
∣-refl = divides 1 (*-onel _)

∣-trans : βˆ€ {x y z} β†’ x ∣ y β†’ y ∣ z β†’ x ∣ z
∣-trans {zero} {zero} p q = q
∣-trans {zero} {suc y} p q = absurd (sucβ‰ zero p)
∣-trans {suc x} {zero} p q = 0 , sym q
∣-trans {suc x} {suc y} {z} (k , p) (k' , q) = k' * k , (
  k' * k * suc x   β‰‘βŸ¨ *-associative k' k (suc x) βŸ©β‰‘
  k' * (k * suc x) β‰‘βŸ¨ ap (k' *_) p βŸ©β‰‘
  k' * suc y       β‰‘βŸ¨ q βŸ©β‰‘
  z                ∎)

We note in passing that any number divides zero, and one divides every number.

∣-zero : βˆ€ {x} β†’ x ∣ 0
∣-zero = divides 0 refl

∣-one : βˆ€ {x} β†’ 1 ∣ x
∣-one {x} = divides x (*-oner x)

A more important lemma is that if divides a non-zero number then the divisors of any positive are smaller than it. Zero is a sticking point here since, again, any number divides zero!

m∣snβ†’m≀sn : βˆ€ {x y} β†’ x ∣ suc y β†’ x ≀ suc y
m∣snβ†’m≀sn {x} {y} p with βˆ£β†’fibre p
... | zero  , p = absurd (zero≠suc p)
... | suc k , p = difference→≀ (k * x) p

m∣nβ†’m≀n : βˆ€ {m n} .⦃ _ : Positive n ⦄ β†’ m ∣ n β†’ m ≀ n
m∣nβ†’m≀n {n = suc _} = m∣snβ†’m≀sn

proper-divisor-< : βˆ€ {m n} .⦃ _ : Positive n ⦄ β†’ m β‰  n β†’ m ∣ n β†’ m < n
proper-divisor-< mβ‰ n m∣n with ≀-strengthen (m∣nβ†’m≀n m∣n)
... | inl here  = absurd (m≠n here)
... | inr there = there

This will let us establish the antisymmetry we were looking for:

∣-antisym : βˆ€ {x y} β†’ x ∣ y β†’ y ∣ x β†’ x ≑ y
∣-antisym {zero}  {y}     p q = sym p
∣-antisym {suc x} {zero}  p q = absurd (sucβ‰ zero q)
∣-antisym {suc x} {suc y} p q = ≀-antisym (m∣snβ†’m≀sn p) (m∣snβ†’m≀sn q)

Elementary propertiesπŸ”—

Since divisibility is the β€œis-multiple-of” relation, we would certainly expect a number to divide its multiples. Fortunately, this is the case:

∣-*l : βˆ€ {x y} β†’ x ∣ x * y
∣-*l {y = y} = fibreβ†’βˆ£ (y , *-commutative y _)

∣-*r : βˆ€ {x y} β†’ x ∣ y * x
∣-*r {y = y} = fibreβ†’βˆ£ (y , refl)

|-*l-pres : βˆ€ {n a b} β†’ n ∣ b β†’ n ∣ a * b
|-*l-pres {n} {a} {b} p1 with (q , Ξ±) ← βˆ£β†’fibre p1 = fibreβ†’βˆ£ (a * q , *-associative a q n βˆ™ ap (a *_) Ξ±)

∣-*-cancelr : βˆ€ {n a b} .⦃ _ : Positive n ⦄ β†’ a * n ∣ b * n β†’ a ∣ b
∣-*-cancelr {n} {a} {b} p1 with (q , Ξ±) ← βˆ£β†’fibre p1 = fibreβ†’βˆ£ (q , *-injr n (q * a) b (*-associative q a n βˆ™ Ξ±))

If two numbers are multiples of then so is their sum.

∣-+ : βˆ€ {k n m} β†’ k ∣ n β†’ k ∣ m β†’ k ∣ (n + m)
∣-+ {zero} {n} {m} p q = ap (_+ m) p βˆ™ q
∣-+ {suc k} (x , p) (y , q) = x + y , *-distrib-+r x y (suc k) βˆ™ apβ‚‚ _+_ p q

∣-+-cancel : βˆ€ {n a b} β†’ n ∣ a β†’ n ∣ a + b β†’ n ∣ b
∣-+-cancel {n} {a} {b} p1 p2 with (q , Ξ±) ← βˆ£β†’fibre p1 | (r , Ξ²) ← βˆ£β†’fibre p2 = fibreβ†’βˆ£
  (r - q , monus-distribr r q n βˆ™ apβ‚‚ _-_ Ξ² Ξ± βˆ™ ap ((a + b) -_) (sym (+-zeror a)) βˆ™ monus-cancell a b 0)

∣-+-cancel' : βˆ€ {n a b} β†’ n ∣ b β†’ n ∣ a + b β†’ n ∣ a
∣-+-cancel' {n} {a} {b} p1 p2 = ∣-+-cancel {n} {b} {a} p1 (subst (n ∣_) (+-commutative a b) p2)

The only number that divides 1 is 1 itself:

∣-1 : βˆ€ {n} β†’ n ∣ 1 β†’ n ≑ 1
∣-1 {0} p = sym p
∣-1 {1} p = refl
∣-1 {suc (suc n)} (k , p) = *-is-oner k (2 + n) p

Even and odd natural numbersπŸ”—

A number is even if it is divisible by 2, and odd otherwise. Note that a number is odd if and only if its successor is even; we take this as our definition because it’s easier to compute with positive statements.

is-even : Nat β†’ Type
is-even n = 2 ∣ n

is-odd : Nat β†’ Type
is-odd n = is-even (suc n)

oddβ†’not-even : βˆ€ n β†’ is-odd n β†’ Β¬ is-even n
odd→not-even n (x , p) (y , q) = 1≠2*n (x - y) $
  monus-swapr 1 _ _ (ap suc q βˆ™ sym p) βˆ™ sym (monus-distribr x y 2)
  where
    1β‰ 2*n : βˆ€ n β†’ Β¬ (1 ≑ n * 2)
    1≠2*n zero = suc≠zero
    1≠2*n (suc n) h = zero≠suc (suc-inj h)

We can easily decide whether a number is even or odd by induction.

even-or-odd : βˆ€ n β†’ is-even n ⊎ is-odd n
even-or-odd zero = inl ∣-zero
even-or-odd (suc n) with even-or-odd n
... | inl p = inr (∣-+ ∣-refl p)
... | inr p = inl p

even? : βˆ€ n β†’ Dec (is-even n)
even? n with even-or-odd n
... | inl e = yes e
... | inr o = no (odd→not-even n o)

See Data.Nat.DivMod for a general decision procedure for divisibility.


  1. Not to be confused with a proper division algorithm.β†©οΈŽ

  2. read β€œa divides bβ€β†©οΈŽ