Dafny GCD 引理证明

Question

我想用 dafny 来证明以下关于 GCD 的引理：对于所有 k 个自然数，如果 k|a 和 k|b，则 k|gcd(a,b)。到目前为止我有以下代码：

// Euclid's algorithm for computing the greatest common divisor
function gcd(a: nat, b: nat): nat
    requires a > 0 && b > 0
{
    if a == b then a else 
    if b > a then gcd(a, b - a) else 
    gcd(a - b, b) 
}

predicate divides(a: nat, b:nat)
    requires a > 0
{
exists k: nat :: b == k * a
}

lemma dividesLemma(a: nat, b: nat)
//k|a && k|b ==> k|gcd(a,b)
requires a > 0 && b > 0
    ensures gcd(a,b) > 0
    ensures forall k: nat :: divides(a,k) && divides(b,k) ==> divides(gcd(a,b),k)
{
    if(a == b) {
        assert a * 1 == gcd(a,b);
        assert b * 1 == gcd(a,b);
    } else if b > a {
        if(divides(a, b)) {
            assert divides(a,a);
            assert divides(a,b);
            assert divides(a, gcd(a,b));
        } else {
            dividesLemma(a, b - a);
        }
    } else {
        if(divides(b, a)) {
            assert divides(b,b);
            assert divides(b,a);
            assert divides(b, gcd(a,b));
        } else {
            dividesLemma(a, a - b);
        }
    }
}

我知道如何手工证明这一点。我会考虑 a 和 b 的素数分解，并说 gcd(a,b) 是组合素数分解，这样我们就可以从每个素数分解中得到最少数量的素数。例如，如果 a = 9 和 b = 15，则 9 = 3x3 的素数分解和 15 = 3x5 的素数分解，因此 gcd(9,5) = 3 因为这是它们素数分解的最小组合。使用这个事实应该清楚，如果 k|b 和 k|a，k 必须包含那些最小素数。我怎样才能用dafny表达这个？目前，我正在考虑 if a=b 和 if a|b 或 b|a 的基本情况，但不确定如何将 a 和 b 可能在其素数分解中不共享公共素数这一事实结合起来。

任何帮助将不胜感激！

Answer 1

divides 的调用方式有问题。我认为在 ensures 子句中你的意思是 divides(k, a) 而不是 divides(a, k) divides(b, k) 和 divides(gcd(a, b), k).

同样如此

在递归调用 dividesLemma(a, b - a) 之后解决这个问题的一种方法是使用方法的后置条件。这里我们知道对于所有 k 这样 k 除 a 和 k 除 b - a 意味着 k 除 gcd(a, b-a)。使用此信息，我们尝试证明所需的后置条件（代码或证明很容易遵循）

dividesLemma(a, b - a);
assert gcd(a, b) == gcd(a, b-a);
assert forall k : nat :: k > 0 && divides(k, a) && divides(k, b-a) ==> divides(k, gcd(a, b));
forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
    var m :| a == m * k;
    var n :| b == n * k;
    assert (b - a) == (n - m) * k;
    assume n >= m;
    assert divides(k, a);
    assert divides(k, b-a);
    // Implied from last assert forall
    assert divides(k, gcd(a, b)); 
}

这里我假设n >= m因为divides需要n-m是nat，这可以单独证明。

另外第二个递归调用应该是dividesLemma(a - b, b).

function gcd(a: nat, b: nat): nat
  requires a > 0 && b > 0
{
  if a == b
    then a
  else if a < b
    then gcd(a, b-a)
  else gcd(a-b, b)
}

predicate divides(a: nat, b: nat)
  requires a > 0 && b > 0
{
  exists k: nat :: b == k * a
}

lemma helper(a: nat, b: nat, k : nat)
  requires a > 0 && b > 0 && k > 0
  requires divides(k, a) && divides(k, b)
  requires b >= a
  ensures exists m, n :: a == m * k && b == n * k && m <= n;
{ }
    
lemma dividesLemma(a: nat, b: nat)
  decreases a + b
  requires a > 0 && b > 0
  ensures gcd(a, b) > 0
  ensures forall k: nat :: k > 0 && divides(k, a) && divides(k, b) ==> divides(k, gcd(a, b))
{
  if (a == b){
  }
  else if (b > a){
    dividesLemma(a, b - a);
    assert gcd(a, b) == gcd(a, b-a);
    assert forall k : nat :: k > 0 && divides(k, a) && divides(k, b-a) ==> divides(k, gcd(a, b));
    forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
      helper(a, b, k);
      var m, n :| a == m * k && b == n * k && m <= n;
      assert b - a == (n - m) * k;
      assert divides(k, b-a);
    }
  }
  else {
    dividesLemma(a - b, b);
    assert gcd(a, b) == gcd(a - b, b);
    assert forall k : nat :: k > 0 && divides(k, a-b) && divides(k, b) ==> divides(k, gcd(a, b));
    forall k : nat | k > 0 && divides(k, a) && divides(k, b) ensures divides(k, gcd(a, b)) {
      helper(b, a, k);
      var m, n :| b == m * k && a == n * k && m <= n;
      assert a - b == (n - m) * k;
      assert divides(k, a-b);
    }
  }
}

Dafny GCD 引理证明

Dafny GCD lemma Proof

proof

dafny

proof-of-correctness