Solutions manual for "A computational introduction to number theory and algebra"

If you follow me on Twitter, you've probably known that I've been into "A computational introduction to number theory and algebra" aka NTB for the last two or three months.

IMHO, NTB is the best introductory-level book on number theory and algebra, especially for those who want to study these two mathematic subjects from a computer science and cryptography perspective.

Moreover, the complete book is freely available online in PDF format under a Creative Common license. Thank you professor Victor Shoup!

Professor Jonathan Katz says it best:

This (NTB) is an outstanding and well-written book whose aim is to introduce the reader to a broad range of material — ranging from basic to relatively advanced — without requiring any prior knowledge on the part of the reader other than calculus and mathematical maturity. That the book succeeds at this goal is quite an accomplishment! Besides focusing on the computational aspects of number theory and algebra — e.g., presenting algorithms for various tasks and analyzing their complexity — the book emphasizes important applications of the mathematics developed.

...

On the whole, this book is a must-read for anyone interested in computational number theory or algebra and especially applications of the latter to cryptography. I would not hesitate, though, to recommend this book even to students “only” interested in the algebra itself (and not the computational aspects thereof); especially for computer science majors, this book is one of the best available introductions to that subject.

In order to show my gratitude to professor Victor Shoup, as the title of this blog post suggests, I decide to write a solutions manual, which is, unfortunately, not supplied with the book.

My solutions manual doesn't cover all the exercises. I simply can't because some of them are too hard for me :-(. I spend most of my effort on underlined exercises which "develop important (but usually simple) facts, and should be viewed as an integral part of the book."

Currently I have solved most of the exercises in chapter 1, 2 and 6. This is a work in progress, so please come back frequently to see updates for exercises from other chapters.

Last but not least, please be aware that although I'm pretty confident about my solutions, they might be wrong. Please don't use them as submissions for your homeworks without first trying to DIY ;-). If you spot anything wrong (including my newbie Latex-fu :-)), please let me know. Thank you.

-----------------------

Click on the links to see the relevant exercises and solutions.

Solutions manual for "A Computational Introduction To Number Theory And Algebra"

1 Basic properties of the integers

1.1 Divisibility and primality

1.2 Ideals and greatest common divisors

1.3 Some consequences of unique factorization

2 Congruences

2.1 Equivalence relations

2.2 Definitions and basic properties of congruences

2.3 Solving linear congruences

2.4 The Chinese remainder theorem

2.5 Residue classes

2.6 Euler’s phi function

2.7 Euler’s theorem and Fermat’s little theorem

2.8 Quadratic residues

2.9 Summations over divisors

3 Computing with large integers

3.1 Asymptotic notation

3.2 Machine models and complexity theory

3.3 Basic integer arithmetic

3.4 Computing in

3.5 Faster integer arithmetic (*)

3.6 Notes

6 Abelian groups

6.1 Definitions, basic properties, and examples

6.2 Subgroups

6.3 Cosets and quotient groups

6.4 Group homomorphisms and isomorphisms

6.5 Cyclic groups

6.6 The structure of finite abelian groups (∗)