1: Chapters
- Page ID
- 83365
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \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{\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.1: What Is Number Theory?
- Simply stated, number theory is concerned with questions about and properties of the integers …,−4,−3,−2,−1,0,1,2,3,4,… and closely-related numbers. Since you’ve been dealing with whole numbers of one kind or another for almost your whole life, some of what we’ll see in the text will seem familiar, and much may seem simple and easy at first glance. Still, number theory is a surprisingly deep subject, and this text only delves into what is known as elementary number theory.
- 1.5: The Division Algorithm
- The goal of this chapter is to introduce and prove the following important result.
- 1.6: The Base b Representation of n
- In this chapter we show how the Division Algorithm is related to a concept touched on since grade school mathematics.
- 1.7: Greatest Common Divisor and Least Common Multiple
- In the last few chapters we have discussed divisibility and the Division Algorithm when a single number is divided by another. In this chapter we begin to look at divisors and multiples that two numbers have in common.
- 1.8: The Euclidean Algorithm
- The Euclidean Algorithm is named after Euclid of Alexandria, who lived about 300 BCE. The algorithm 1 described in this chapter was recorded and proved to be successful in Euclid’s Elements, so this algorithm is over two thousand years old. It provides a simple method to compute gcd(a,b) , even if we do not know much about the divisors of a and b.
- 1.10: Computing Coefficients for Bezout's Lemma
- Though the proof of Bezout’s Lemma in the last chapter simply showed that, given integers a and b, coefficients s and t exist such that gcd(a,b)=sa+tb , suitable modifications of the Euclidean Algorithm give us ways of computing these coefficients. In this chapter we discuss two such ways, known as the Extended Euclidean Algorithm and Blankinship’s Method.
- 1.12: Unique Factorization
- Our goal in this chapter is to prove the Fundamental Theorem of Arithmetic.
- 1.13: The Gaussian Integers
- In this section we study a special subset of the complex numbers known as the Gaussian integers.
- 1.14: Fermat Primes and Mersenne Primes
- Finding large primes and proving that they are indeed prime is not easy. For a long time, people have looked for formulas for producing prime numbers, with varying degrees of success. In this chapter we’ll learn about related questions and answers contributed by many people over the past several centuries—and even in the current one.
- 1.15: Number Theoretic Functions
- The prime-counting function π(x) appearing in the Prime Number Theorem and the prime-generating functions are by no means the only functions studied in number theory. Mathematicians through history have profitably looked at several additional functions tied to our key questions about the integers. In this chapter we introduce three of these.
- 1.20: More Properties of Congruences
- In this chapter we introduce an important idea in working with congruences. It will have useful consequences and will illustrate another reason Bezout’s Lemma is important.
- 1.23: Chinese Remainder Theorem
- The Chinese Remainder Theorem is an important theorem appearing for perhaps the first time in Sunzi Suanjing, a Chinese mathematical text written sometime during the 3rd to 5th centuries AD.
- 1.24: Theorems of Wilson, Euler, and Fermat
- As the Chinese Remainder Theorem illustrated in the last chapter, some useful and interesting number theoretic results deal with congruences. In this chapter we present a few more well known theorems involving congruences.
- 1.25: Primality Tests
- Two theorems from the previous chapter, Wilson’s Theorem and Fermat’s Little Theorem, connect prime numbers and congruences in perhaps surprising ways. In this chapter we look at how these theorems can be turned into techniques for testing whether a number n is prime.