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、……组成
对于负数- 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.

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

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

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

证明：

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!

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

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

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

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

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.”

给定两个整数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.

设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和它本身。

Observation 1.1. 1 is not a prime number.

Observation 1.2. 2 is the only even prime number.

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.)

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

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

根据定义，任何正整数都是素数，合数，或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.

给定一个正整数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.

这个定理说明了两点：

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

Theorem 1.2. There are infinitely many primes.

有无限个素数

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.

设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.

如果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.

取任意三个整数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.

取任意三个值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!

也就是说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, . . .}.

自然数用集合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 . . .

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

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

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

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

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