-
Notifications
You must be signed in to change notification settings - Fork 16
/
number_theory.theory.txt
105 lines (92 loc) · 4 KB
/
number_theory.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
NUMBER_THEORY
Number:
- algebraic structure for counting
- goal:
- cardinal: counting
- ordinal: ordering (e.g. 3th)
- nominal: labelling, i.e. only use numeral, not number value (e.g. Zip code)
Number sets:
- ℕ :
- also noted N
- named positive integers, or natural|whole|counting numbers
- any number that can be expressed with additions of 1 (including none)
- {x: (x - 1∈ N) || (x = 0)}
- 0:
- usually included in modern definitions:
- noted N₀ or N⁰
- in past, was not included
- noted N*, N+ or N₁
- ℤ :
- also noted Z
- named integers
- any number that can be expressed with addition|subtraction and operands ∈ N
- {x-y: x,y∈ N}
- ℚ :
- also noted Q
- named rational numbers
- any number that can be expressed with addition|subtraction|multiplication|subtraction and operands ∈ N
- {x/y: x,y∈ Z, y != 0}
- ℝ :
- also noted R
- real numbers
- any number that can be expressed with addition|subtraction|multiplication|subtraction and exponeniation (except with fractional exponent and negative base) and operands ∈ N
- I:
- named irrational numbers
- if ∈ R && ∉ Q
- ℂ :
- also noted C
- complex numbers
- any number that can be expressed with any algebraic operation (addition|subtraction|multiplication|subtraction|exponeniation) and operands ∈ N
- transcendental numbers:
- any number that cannot be expressed as algebraic expression
Divisor:
- also named factor|multiple
- y is divisor of x if yz = x and y,z∈ N
- divisible: inverse
Greatest common divisor (GCD):
- maximum divisor of two numbers
- Euclidean algorithm:
- func(a, b) => a == b
? a
: a > b
? func(a - b, b)
: func(a, b - a)
(shorter version)
- func(a, b) => b == 0
? a
: func(b, a % b)
Least common multiple (LCM)
- for two numbers, smallest number divisible by both
Prime number:
- when x∈ N and only divisors are 1 and x itself
- composite number: opposite
- 0 and 1 are neither composite nor prime
Coprime
- also named relatively prime
- noted x ⊥ y
- when x,y∈ N and only common divisor is 1
Factorization:
- finding all prime divisors of a number
- fundamental theorem of arithmetic
- also called unique [prime] factorization theorem
- if x∈ N, has exactly one factorization
- except 0 and 1
- canonical representation:
- also named standard form
- writing number as its factorization, with exponents if needed, ordered from smallest to highest base
- e.g. 12 = 2^2 * 3
Normal number:
- when infinite digits with uniform distribution
- simply|absolutely normal: when for a specific|all bases
Golden ratio
- noted φ or Φ (phi)
- irrational number
- φ = 1 + 1/φ, and φ > 0
- implies:
- if φ = x/y
- then x/y = (x+y)/x
- value:
- exact: (1 + √5)/2
- approximated: 1.618033...