Chapters
- Page ID
- 82838
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)- 1: Basic Axioms for Z
- This page provides an introduction to key notation and properties in number theory, particularly regarding integers. It defines important sets like natural numbers, integers, rational numbers, and real numbers, explaining their interrelationships. The page details crucial axioms related to integers, such as closure under operations, uniqueness of unit factors, laws of exponents, and properties of inequalities.
- 2: Proof by Induction
- This page covers the Principle of Mathematical Induction (PMI) through detailed examples, including a proof of \(2^n > 5n\) for \(n \ge 5\) and the structure of inductive proofs. It highlights eight components of inductive proof and provides exercises. Additionally, it discusses triangular and square numbers, encouraging students to derive their formulas without induction, while also hinting at the use of induction for proofs.
- 3: Elementary Divisibility Properties
- This page introduces the concept of divisibility in mathematics, explaining that \(d \mid n\) means there exists an integer \(k\) such that \(n=dk\). It highlights equivalent statements and key properties of divisibility, including transitivity, linearity, and cancellation, presented in theorem form. Definitions related to linear combinations are also covered, emphasizing their importance in the context of divisibility.
- 4: The Floor and Ceiling of a Real Number
- This page covers the floor and ceiling functions, defined by Kenneth Iverson, where the floor function \(\lfloor x \rfloor\) gives the greatest integer less than or equal to \(x\), and the ceiling function \(\lceil x \rceil\) provides the least integer greater than or equal to \(x\). Key properties and inequalities are discussed, along with exercises to enhance comprehension and application of these mathematical concepts.
- 5: The Division Algorithm
- This page covers the Division Algorithm, which asserts that for any integers \(a\) and \(b\) (where \(b>0\)), unique integers \(q\) (quotient) and \(r\) (remainder) exist such that \(a = bq + r\) with \(0 \leq r < b\). It includes proofs of existence and uniqueness, definitions of even and odd integers, exercises to strengthen understanding, and an introduction to modular arithmetic with related proofs.
- 6: Greatest Common Divisor
- This page explains the greatest common divisor (gcd) of integers \(a\) and \(b\) as the largest integer \(d\) that divides both, noting that \(\gcd(0,0)=0\). It covers common divisors, provides examples, and proves key properties of gcd such as symmetry and the relationship with absolute values. Additionally, it includes exercises to enhance comprehension of the topic.
- 7: The Euclidean Algorithm
- This page explains the Euclidean Algorithm for calculating the greatest common divisor (gcd) of two integers. It presents essential lemmas, such as \(\gcd(a,0)=a\) for positive \(a\) and that \(\gcd(a,b)=\gcd(b,r)\) when \(a=bq+r\). An example of computing \(\gcd(803,154)\) showcases the algorithm's efficiency. The page also features exercises to practice finding gcd values, emphasizing the algorithm's practical applications.
- 8: Bezout's Lemma
- This page discusses Bezout's Lemma, which asserts that for any integers \(a\) and \(b\), there are integers \(s\) and \(t\) such that \(\gcd(a,b) = sa + tb\). The proof constructs a set of linear combinations and uses the Well-Ordering Property to show that the smallest positive integer in this set is \(\gcd(a,b)\). While it confirms the existence of \(s\) and \(t\), it does not provide a method for finding them, which will be addressed in subsequent chapters.
- 9: Blankinship's Method
- This page describes W.A. Blankinship's matrix method for deriving integers \(s\) and \(t\) in Bezout’s Lemma and finding the greatest common divisor (gcd). The process involves manipulating an array format of rows until the gcd and coefficients are identified. Two examples demonstrate the methodology, ensuring accuracy in the obtained gcd and coefficients. Additionally, exercises provide opportunities for practice and exploration of gcd-related properties.
- 10: Prime Numbers
- This page covers prime and composite integers, defining primes as having only two positive divisors and composites as having more. It includes proofs about composite integers having factors and the existence of prime divisors in integers greater than 1, along with Euclid's Theorem on the infinitude of primes.
- 11: Unique Factorization
- This page outlines the Fundamental Theorem of Arithmetic, asserting that every integer greater than one can uniquely be factored into primes. It includes examples, such as the prime factorization of 600, and introduces key lemmas on divisibility and relatively prime integers.
- 12: Fermat Primes and Mersenne Primes
- This page covers the complexities of identifying large primes, specifically Mersenne and Fermat numbers. It outlines the criteria for prime generation, such as the primality of \(n\) for Mersenne numbers. Historical insights like known Mersenne primes and the conjectured non-primality of certain Fermat numbers are mentioned.
- 13: The Functions σ and τ
- This page covers the definitions and examples of positive divisors, including the functions \(\tau(n)\) and \(\sigma(n)\) for a positive integer \(n\), and discusses proper divisors and perfect numbers. It provides a theorem on calculating these functions using prime factorization, supported by lemmas.
- 14: Perfect Numbers and Mersenne Primes
- This page explores perfect numbers under 10,000, explaining that if \(2^p - 1\) is a Mersenne prime, then \(2^{p-1}(2^p - 1)\) is a perfect number. It proves all even perfect numbers follow this structure and establishes a correspondence between even perfect numbers and Mersenne primes. The page also poses open questions about the infinitude of even perfect numbers and Mersenne primes, as well as the existence of odd perfect numbers.
- 15: Congruences
- This page introduces congruence modulo \(m\) and its properties, defined as \(a \equiv b \pmod{m}\) when \(m\) divides \(a-b\). It highlights congruence as an equivalence relation with reflexivity, symmetry, and transitivity. Theorem 3 details rules for congruences in modular arithmetic, including operations like addition and multiplication, illustrated with Fermat numbers. Theorem 4 clarifies the modulus operation, accompanied by exercises to deepen understanding of these concepts.
- 16: Divisibility Tests for 2, 3, 5, 9, 11
- This page explores properties of positive integers regarding their decimal representation and modular arithmetic. It introduces a theorem linking a positive integer \(a\) and its last digits (\(a_0\)), as well as the sums of its digits, to determine \(a \mod m\) for various moduli. Theorems are presented with corresponding modulus rules based on the last digit and digit sums, leading to a corollary on divisibility. Examples and exercises further engage readers in modular arithmetic concepts.
- 17: Divisibility Tests for 7 and 13
- This page presents a theorem on the divisibility of a number \(a\) by 7 and 13, based on its decimal representation. It explains that \(a\) is divisible by 7 if the difference between the number formed by its leading digits and twice the last digit is divisible by 7, and similarly for 13 with a different coefficient. Proofs and examples clarify the application of these rules, and exercises are included for practice.
- 18: More Properties of Congruences
- This page covers essential theorems in modular arithmetic, including the unique inverse of relatively prime numbers and the cancellation property influenced by the greatest common divisor. It also addresses solving congruences, demonstrating step-by-step methods to find specific solutions and acknowledging cases with no solutions.
- 19: Residue Classes
- This page introduces residue classes modulo \(m\) denoted as \([a]\), encompassing all integers congruent to \(a\). It explains that there are \(m\) distinct classes corresponding to integers \(0\) to \(m-1\), and discusses representatives of these classes, stressing their uniqueness. Theorems support these concepts, augmented by exercises for practical understanding with specific moduli.
- 20: Zm and Complete Residue Systems
- This page introduces the ring of integers modulo \(m\), \(\mathbb{Z}_m\), which consists of \(m\) distinct residue classes \([0], [1], \ldots, [m-1]\). It defines complete residue systems modulo \(m\) and presents least nonnegative and absolute residue systems. Examples show construction of different complete residue systems, while theorems outline their specific structures for even and odd moduli.
- 21: Addition and Multiplication in Zm
- This page introduces arithmetic operations of addition and multiplication in residue classes modulo \(m\), forming a ring and ensuring results are consistent through defined binary operations and equivalences. It presents the structure \(J_m\) for modular operations, supported by examples and exercises. Additionally, it covers solving congruences through step-by-step reduction, successfully determining \(x=5\) as the solution via trial and error within a designated range.
- 22: The Groups Um
- This page explores units in modular arithmetic, defining them within residue classes \(\mathbb{Z}_m\) as classes with inverses based on the condition \(\gcd(a,m)=1\). It introduces the group of units \(U_m\) and the Euler phi function \(\phi(m)\), which counts the number of units.
- 23: Two Theorems of Euler and Fermat
- This page covers key theorems in number theory, particularly Fermat's Big Theorem, which asserts that \(x^n + y^n = z^n\) has no positive integer solutions for \(n > 2\), and Fermat's Little Theorem, relevant in cryptography. It explores Euler's Theorem's implications and includes exercises on modular arithmetic, showcasing methods for calculating large exponentiations modulo a small integer through examples. The focus is on practical applications of these theorems in number theory.
- 24: Probabilistic Primality Tests
- This page discusses Fermat’s Little Theorem, which states that for a prime \(p\), \(a^{p-1} \equiv 1 \pmod{p}\) for \(1 \leq a < p\), and its converse regarding the primality of \(m\). It notes that while \(a^{m-1} \equiv 1 \pmod{m}\) suggests \(m\) is prime, this is not always true, as seen with 341. The page emphasizes that for \(m \leq 10^{10}\), the test is a strong indicator but not conclusive, highlighting the need for more reliable primality tests like Maple's isprime.
- 25: The Base b Representation of n
- This page covers the base \(b\) representation of integers, defining the structure, uniqueness, and various bases such as binary, decimal, and hexadecimal. It outlines a theorem supported by the Division Algorithm and provides examples of number conversions. Moreover, it explores methods for deriving binary representations, including systematic identification of powers of 2. Exercises are included for readers to practice and discover patterns in integer representations across different bases.
- 26: Computation of aN mod m
- This page focuses on efficient methods for calculating powers, particularly \(a^N\) and \(a^n \mod m\). It contrasts traditional multiplication with the "Binary Method," which leverages successive squaring based on the binary representation of \(N\) to minimize the number of multiplications. The theorem states that this approach requires at most \(2\lfloor\log_2(n)\rfloor\) multiplications.
- 27: The RSA Scheme
- This page introduces the RSA public key cryptographic scheme by Rivest, Shamir, and Adelman, outlining its number-theoretic foundations with integer message conversion. It details the encipher (E) and decipher (D) functions and their inverse relationship, supported by a lemma on prime numbers. Theorem 1 confirms E and D as inverses, ensuring the restoration of original messages. Future sections will cover practical implementation.
- 28: A Rings and Groups
- This page defines two key algebraic structures: rings and groups. A ring consists of a set with two operations (addition and multiplication) that follow certain properties, with examples including real numbers and integers. A group includes a set and a binary operation that meets rules like associativity, identity, and inverses, exemplified by integers under addition and non-zero rationals under multiplication. It serves as an introductory resource for abstract algebra.