title: 01. 整数运算基础
tags:
  - zk
  - basic
  - integer​

WTF zk教程第1讲：整数运算基础

作为零基础的零知识证明教程，我们将从最基础的整数运算开始学习。相信大部分人在中学时已经学过，会非常轻松。我们还将用python复现整数运算，新手也可以很快上手。

对于没使用过python的朋友，建议安装Anaconda来安装并管理python环境。

1. 基本定义

整数是没有小数部分的数，可以是正数、负数或零。我们用 \mathbb{Z} 表示所有整数的集合。

对于整数 a \in \mathbb{Z}，那么我们用 \lvert a \rvert 表示 a 的绝对值，也就是 a 的非负值，不考虑其符号。

我们经常会用到自然数 \mathbb{N}，它是整数的子集，包含所有正整数。

另外，我们有时会用到非负整数，我们用 \mathbb{N_0} 表示：

注：在有些教材中会将0包含在自然数中，关于0是否包含在自然数中目前仍有争议。

2. 整数运算

整数运算包括加法、减法、乘法和除法。让我们回顾一下这些基本运算的规则：

• 加法（ + ）： 对于整数 a 和 b，它们的和 a + b 是将它们相加得到的结果。

  a, b = 7, 5
  sum_result = a + b
  print(f'加法示例: {sum_result}')
  # 加法示例: 12
  ​

• 减法（ - ）： 对于整数 a 和 b，它们的差 a - b 是将 b 从 a 中减去得到的结果。

  diff_result = a - b
  print(f'减法示例: {diff_result}')
  # 减法示例: 2
  ​

• 乘法（ \times ）： 对于整数 a 和 b，它们的积 a \times b 是将它们相乘得到的结果。

  product_result = a * b
  print(f'乘法示例: {product_result}')
  # 乘法示例: 35
  ​

3. 整数性质

整数有一些重要的性质：

• 封闭性： 整数加法和乘法在整数集合内是封闭的，即对任意两个整数的加法或乘法仍得到一个整数。

• 交换性： 整数加法和乘法是交换的，即 a + b = b + a 和 a \times b = b \times a 对于任意整数 a 和 b 成立。

• 结合性： 整数加法和乘法是结合的，即 (a + b) + c = a + (b + c) 和 (a \times b) \times c = a \times (b \times c) 对于任意整数 a, b 和 c 成立。

4. 欧几里得除法（Euclidean Division）

我们平常使用的除法是实数除法，两个整数相除的结果不一定是整数，比如 7 \div 5=1.4 不是整数。因此，我们引入整数除法，也叫欧几里得除法（Euclidean Division）。它的结果由两部分组成：商（quotient）和余数（remainder）。欧几里得除法的定义：

对于整数 a 和 b（其中 b \neq 0），存在唯一的整数对 (q, r)，使得 a = bq + r，其中 q 是商, r 是余数，且 0 \leq r \lt |b|。

如果 a 除以 b 的余数为零，则我们称 a 可以被 b 整除（ b 整除 a），记为 b \mid a，我们可以称 b 为 a 的因数；若余数不为零，则记为 b \nmid a。

我们可以利用python实现欧几里得除法，实现的时候要注意处理当 a 或 b 为负数的情况：python中的divmod函数允许余数为负，而欧几里得除法要求余数 0 \leq r \lt |b|。相反，python 自带的模运算（求余数） % 是允许出现负数的。这里有必要去了解一下编程语言内部对模运算的实现公式： a\%b=a-(a//b) * b 。(这里的 // 就是 python 内部对欧几里得除法的实现，保证余数为正且小于除数)。

def euclidean_division(a, b):
    quotient, remainder = divmod(a, b)
    if remainder < 0:
        # 调整余数确保非负
        remainder += abs(b)
        # 调整商使等式仍然成立
        quotient += 1
    return quotient, remainder

quotient, remainder = euclidean_division(a, b)
print(f'除法示例: 商为 {quotient}, 余数为 {remainder}')
# 除法示例: 商为 1, 余数为 2
​

5. 总结

这一讲，我们介绍了整数基础，包括其定义及其基础运算（加、减、乘、欧几里得除法），并使用python实现了它们。相信大家中学都学过这些概念，觉得很简单，让我们继续WTF zk之旅！