Number Theory Basics

Euclid's Division Algorithm

• A method for dividing a positive integer a by another positive integer b to find the quotient q and remainder r such that:
  • a = bq + r
  • 0 ≤ r < b
• The algorithm is used to find the greatest common divisor (GCD) of two numbers
• It is a recursive process, where the remainder becomes the new divisor and the divisor becomes the new dividend

Fundamental Theorem of Arithmetic

• Every positive integer can be expressed as a product of prime numbers in a unique way, except for the order of the factors
• This theorem states that every positive integer has a unique prime factorization
• It is a fundamental principle in number theory, used to prove many results about integers and their properties

Irrational Numbers

• A real number that cannot be expressed as a finite decimal or a ratio of integers (e.g. π, e, sqrt(2))
• Irrational numbers have infinite non-repeating decimal expansions
• They cannot be expressed exactly as a finite decimal or fraction, but can be approximated to any desired degree of accuracy

Properties of Real Numbers

• Commutative Property of Addition: a + b = b + a
• Associative Property of Addition: (a + b) + c = a + (b + c)
• Commutative Property of Multiplication: a × b = b × a
• Associative Property of Multiplication: (a × b) × c = a × (b × c)
• Distributive Property: a × (b + c) = a × b + a × c
• Existence of Additive and Multiplicative Identities: 0 and 1 respectively
• Existence of Additive Inverses: for each real number a, there exists a real number -a such that a + (-a) = 0

Rational and Irrational Numbers

• Rational Numbers: real numbers that can be expressed as a ratio of integers (e.g. 3/4, 22/7)
• Irrational Numbers: real numbers that cannot be expressed as a ratio of integers (e.g. π, e, sqrt(2))
• Every rational number has a finite decimal expansion, while every irrational number has an infinite non-repeating decimal expansion
• The set of rational numbers is countable, while the set of irrational numbers is uncountable

Euclid's Division Algorithm

• A method to divide a positive integer a by another positive integer b to find quotient q and remainder r, where a = bq + r and 0 ≤ r < b.
• Used to find the greatest common divisor (GCD) of two numbers.
• A recursive process where the remainder becomes the new divisor and the divisor becomes the new dividend.

Fundamental Theorem of Arithmetic

• Every positive integer can be expressed as a product of prime numbers in a unique way, except for the order of the factors.
• States that every positive integer has a unique prime factorization.
• A fundamental principle in number theory used to prove many results about integers and their properties.

Irrational Numbers

• Real numbers that cannot be expressed as a finite decimal or a ratio of integers (e.g. π, e, sqrt(2)).
• Have infinite non-repeating decimal expansions.
• Cannot be expressed exactly as a finite decimal or fraction, but can be approximated to any desired degree of accuracy.

Properties of Real Numbers

• Commutative Property of Addition: a + b = b + a.
• Associative Property of Addition: (a + b) + c = a + (b + c).
• Commutative Property of Multiplication: a × b = b × a.
• Associative Property of Multiplication: (a × b) × c = a × (b × c).
• Distributive Property: a × (b + c) = a × b + a × c.
• Existence of Additive and Multiplicative Identities: 0 and 1 respectively.
• Existence of Additive Inverses: for each real number a, there exists a real number -a such that a + (-a) = 0.

Rational and Irrational Numbers

• Rational Numbers: real numbers that can be expressed as a ratio of integers (e.g. 3/4, 22/7).
• Irrational Numbers: real numbers that cannot be expressed as a ratio of integers (e.g. π, e, sqrt(2)).
• Every rational number has a finite decimal expansion, while every irrational number has an infinite non-repeating decimal expansion.
• The set of rational numbers is countable, while the set of irrational numbers is uncountable.

Learn about fundamental concepts in number theory, including Euclid's Division Algorithm and the Fundamental Theorem of Arithmetic.