Topics in Number Theory

Author(s): Gail Gallitano, Shiv Gupta

Edition: 1

Copyright: 2018

Pages: 304


Details: Electronic Delivery EBOOK | 180 days |

Topics in Number Theory is essentially a first course in number theory and as a prerequisite requires familiarity not much more than what is covered in any high school mathematics curriculum. This book is rich in examples. All the basic topic in elementary number theory including congruence, number theoretic functions, quadratic reciprocity, representation of certain primes in the form x2 + Ny2 using a theorem of Thue, continued fractions and Pell’s equation have been presented in appropriate details and illustrated by examples. Chakrav ala ‘Algorithm’ for finding a solution of Pell’s equation is also presented. The discussion of quadratic fields is followed by Euler’s proof of Fermat’s Last Theorem for exponent three. Several examples of Bachet equations having no solutions whose proofs can be provided based only on congruence arguments are discussed. The discussion of RSA cryptopgraphy is followed by an example using sufficiently large prime numbers. John Conway’s doomsday algorithm for finding day of the week is presented and is graphically illustrated by several examples. This book has over one hundred problems of various level of difficulty from very elementary to challenging. Hints of solutions have been provided to most of these problems.

Introduction and Acknowledgment

Prerequisites and Notation

Chapter 1. Generalities

1. Divisibility

2. Division Algorithm

3. Primes and Composites

4. Congruence and Their Properties

5. Complete Residue System mod m

6. Chinese Remainder Theorem

Chapter 2. Some Number Theoretic Functions

1. Euler's ‑-Function

2. Greatest Integer Function

3. The Functions (n), ơ (n), and µ (n)

4. Perfect Numbers

5. Mobius Inversion Formula

6. Counting the Number of Monic Irreducible Polynomials over a Finite Field

Chapter 3. Primitive Roots and the Structure of Groups Zn

1. The Group Zn

2. Fermat's Little Theorem

3. Euler's Generalization of the Fermat's Little Theorem

4. Mobius -Function Revisited

Chapter 4. Quadratic Residues, Nonresidues, and the Law of Quadratic Reciprocity

1. Legendre Symbol

2. Gauss' Lemma

3. Law of Quadratic Reciprocity

4. Jacobi Symbol

Chapter 5. Representation of Integers as Sums of Squares

1. Sums of Two Squares

2. Sums of Four Squares

Chapter 6. Representing Primes in the Form x2 + Ny2

Chapter 7. Infinitude of Primes

1. Euclid-like Proofs

2. Primes p = 1 (mod n)

3. Euler's Proof of Infinitude of Primes

Chapter 8. Pell's Equation and Continued Fractions

1. Continued Fractions

2. Complete Quotients

3. Reduced Quadratic Irrational

4. Solution of the Pell's Equation x2 - Ny2 = 1

5. Chakravala “Algorithm” for Finding a Solution of Pell's Equation

Chapter 9. Algebraic Number Theory

1. Euclidean Quadratic Fields

2. Fermat's Last Theorem for Exponent 3

Chapter 10. Computational Number Theory

1. Primality Testing

2. RSA Cryptography

3. Computing an (mod m) by Repeated Squaring

4. Calculating Square Root mod p (p > 2, a Prime)

5. Shank's Baby-Step Giant-Step Discrete Log Algorithm

Chapter 11. Some Bachet Equation

Chapter 12. Some Additional Topics

1. Hensel's Lemma

2. LCM(a, b, c) and GCD(a, b, c)

3. Orders of GL(k,Zn) and SL(k,Zn)

4. Problem of Five Sailors and a Monkey

Appendix 1. First 12 Mersenne Primes

Appendix 2. Algebraic Numbers and Algebraic Integers

Appendix 3. Continued Fraction for square root of n for 2 < n < 500 (non-square n) Appendix 4. “Least solution" of Pell's Equation X2 - NY2 = 1

Appendix 5. Test of Divisibility by 7, 11, and 13.

Appendix 6. Calculating Square Roots

Appendix 7. List of primes below 10,000

Appendix 8. Finding Day of the Week - John Conway's Doomsday Algorithm

Appendix 9. Cubic Polynomials with Rational Roots and Critical Points


Credits and Sources Acknowledged




Gail Gallitano

Shiv Gupta

Related ISBN's: 9781524950941, 9781524948016




ISBN 9781524950941

Details Electronic Delivery EBOOK 180 days