计算机数学基础①(Numbers)
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次方
- 等式左边为奇数,等式右边为偶数,故不成立
文章来源: blog.csdn.net,作者:十八岁讨厌编程,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/zyb18507175502/article/details/124230827
- 点赞
- 收藏
- 关注作者
评论(0)