计算机数学基础①(Numbers)_precisel define even & odd integers

Numbers

Integers

Definition 1.1. The integers are the collection of all whole numbers:
that is, they consist of the whole positive numbers 1, 2, 3, 4, . . ., together
with the whole negative numbers −1,−2,−3,−4, . . ., and the number 0.
We denote this set by writing the symbol Z.

The symbol Z comes from the German word “Zahl,” which means “number,” in case you were curious.
1
2
3
4
5
6

整数是所有整数的集合:
也就是说，它们由正数1、2、3、4、……组成
对于负数- 1，- 2，- 3，- 4，…和数字0。
我们用符号Z来表示这个集合。

符号Z来自德语单词“Zahl”，意思是“数字”，如果你好奇的话。

Even and Odd Integers

Definition 1.2. We say that an integer is even if we can write it as 2
times another integer; in other words, we say that an integer n is even
if we can find an integer k such that n = 2k.
Similarly, we say that an integer is odd if we can write it as one plus an
even number; in other words; we say that an integer n is odd if we can
find an integer k such that n = 2k + 1.
1
2
3
4
5
6

我们说整数是偶数，如果我们可以把它写成2
乘以另一个整数;换句话说，我们说整数n是偶数
如果我们能找到一个整数k使n = 2k。（用来证明）
类似地，我们说一个整数是奇数如果我们把它写成1 + an
偶数;换句话说;如果可以，我们说整数n是奇数
求一个整数k，使n = 2k + 1。(用来证明)

Claim 1.1. The sum of any two odd numbers is even.
1

任何两个奇数的和都是偶数。

证明：

Proof. Take any two odd numbers. Let’s give them names, for ease of
reference: let’s call them M and N. By definition, because M and N
are odd, we can write M = 2k + 1 and N = 2l + 1, for two integers k,l.
Therefore, M + N = (2k + 1) + (2l + 1) = 2k + 2l + 2 = 2(k + l + 1). In
particular, this means that M + N is an even number, as we’ve written
it as a multiple of 2!
1
2
3
4
5
6

Claim 1.2. The product of any two odd numbers is odd.
1

任意两个奇数的乘积都是奇数。

Claim 1.3. No integer is both even and odd at the same time.
1

没有整数同时是偶数和奇数。

Divisibility and Primes(可分性和质数)

Definition 1.3. Given two integers a, b, we say that a divides b if there
is some integer k such that ak = b.
There are many synonyms for “divides”: each of the phrases
• “a is a divisor of b”,
• “a is a factor of b”,
• “b is a multiple of a”,
• “b can be divided by a,” and
• a ∣ b
all mean the same thing as “a divides b.”
1
2
3
4
5
6
7
8
9

给定两个整数a b，我们说a能除b
某个整数k使ak = b。
“分”有很多同义词:每个短语都有
•“a是b的除数”，
•“a是b的因数”，
•“b是a的倍数”，
•“b可以被a整除”和
•a∣b
都和a除以b的意思一样

Claim 1.4. Let a, b, c be three integers. If a divides b and b divides c,
then a divides c.
1
2

设a、b、c是三个整数。如果a能整除b, b能整除c，
我们可以说a可以整除c。

Definition 1.4. A prime number is any positive integer with only two
distinct positive factors; namely, 1 and itself.
1
2

质数是任何只有两个因数的正整数：
也就是1和它本身。

Observation 1.1. 1 is not a prime number.
1

Observation 1.2. 2 is the only even prime number.
1

Definition 1.5. A composite number is any positive integer n that
can be written as the product of two integers a, b, both of which are at
least 2 (and thus both of which are strictly smaller than n.)
1
2
3

合数是任意正整数的n
可以写成两个整数a, b的乘积，它们都在
至少2(因此两者都严格小于n)

Observation 1.3. By definition, any positive integer is either a prime
number, a composite number, or 1.
1
2

根据定义，任何正整数都是素数，合数，或1

Definition 1.6. Given a positive integer n, a prime factorization of
n is any way to write n as a product of prime numbers.
1
2

给定一个正整数n，一个质因数分解n是任何把n写成质数乘积的方法。

Theorem 1.1. Every positive integer can be factorized into a product
of prime numbers in exactly one way, up to the ordering of those prime
factors.
1
2
3

这个定理说明了两点：

• 每个正整数都可以分解为质数
• 没有一个数可以用两种不同的方式分解成质数

Theorem 1.2. There are infinitely many primes.
1

有无限个素数

Claim 1.5. Let ab be a two-digit positive integer (where b is that number’s ones’ digit and a is its tens’ digit.) Show that the number abab is
not prime.
1
2

设ab是一个两个数，则abab不是一个素数

此结论可以优化素数的验证程序。他的大意是一个素数不存在位于2，k之间的因数(k为这个数开根之后往下取整)

Modular Arithmetic(模运算)

取任意两个整数a, n，其中n > 0。我们通过以下算法定义数字a % n，发音为“a mod n”:

• 如果a≥n，从a中反复减去n，直到a < n。这个过程的结果是a % n。
• 如果a < 0，重复将n加到a，直到a > 0。这个过程的结果是a % n。
• 如果这两种情况都不适用，那么根据定义0≤a < n。在本例中，a % n就是a(也就是说，我们不需要做任何事情!)

这个模运算在不同的编程语言中有不同的运算结果，具体要在文档中查看实现原理

Claim 1.7. If a, n are any two integers with n > 0, the quantity a % n
exists and is between 0 and n − 1. That is: the algorithm given above
to calculate % will never “crash” nor “run forever,” and it will always
generate an output between 0 and n − 1.
1
2
3
4

如果a, n是任意两个整数，且n >为0，则a % n存在，且介于0和n−1之间。也就是说:上面给出的计算%的算法永远不会“崩溃”或“永远运行”，它总是生成0到n−1之间的输出。

% and Arithmetic

Definition 1.8. Take any three integers a, b, n. We say that a is congruent to b modulo n, and write a ≡ b mod n, if a − b is a multiple of
n.
1
2

取任意三个整数a, b, n，如果a - b是n的倍数，我们说a同b模n，写为a≡b mod n。

Claim 1.8. Take any three values a, b, n such that n ≠ 0. Then the
following two statements are equivalent:
 - a % n = b % n.
 - a − b is a multiple of n; i.e. a ≡ b mod n.
1
2
3
4

取任意三个值a b n使n≠0。然后下面两个表述是等价的：

• a % n = b % n
• a - b是n的倍数 a≡b mod n

Claim 1.9. Suppose that a, b, c, d, n are any set of integers with n ≠ 0,
such that a % n = b % n and c % n = d % n.
Then we have the following properties:
• (a + c) % n = (b + d) % n.
• (ac) % n = (bd) % n.

This claim is basically just saying that we can do “arithmetic modulo
n!” That is: for numbers a, b, c, d, you know that if a = b, c = d then
ac = bd and a + c = b + d, by just combining these equalities with the
addition and multiplication operations. This claim is saying that if your
values are “equal modulo n,” the same tricks work!
1
2
3
4
5
6
7
8
9
10
11

也就是说a、b、c、d、n都是整数，且n不等于0.如果a同b模n，c同d模n，则a + c同b + d模n，ac同bd模n。

第二段文字就是说进行线性运算取等之后的等式，如果在两边同时取模也是成立的。

注意这个k取任意正整数。
运用这个方法可以对大数进行一个缩小的操作。

这个声明我们可以使用上面的方法来证：

• 首先我们缩小213047为7
• 再找规律，发现四个一循环(最后一位为7，9，3，1)

Other Number Systems

任何一个有理数都可以表示为两数之比，其中x、y是整数，y是非零的。我们用Q来表示有理数集。

numerator 被除数
denominator 除数

Definition 1.11. The natural numbers, denoted N, is the collection
of all nonnegative integers. That is, N = {0, 1, 2, 3, 4, 5, . . .}.
1
2

自然数用集合N表示，是非负整数

Definition 1.12. The real numbers, denoted R, is the collection of
all numbers that you can write out with a (possibly infinite) decimal
expansion: i.e. it’s the collection of things like
• 2.1,
• −724,
• 0.111111 . . . = 0.1, and
• −3.1415926535 . . .
1
2
3
4
5
6
7

实数R是所有可以用(可能是无限的)小数展开的数的集合

Observation 1.4. Notice that every real number, by definition, is either
rational or irrational.
1
2

每个实数如果不是有理数，那他一定是无理数，只可能是两者中的一个！

证明这个只需要用到有理数的定义。

• 将此对数放在等式左边，右边放上x / y
• 将等式两边同时作为2的指数
• 等式两边同时y次方
• 等式左边为奇数，等式右边为偶数，故不成立