# Fundamental Number Theory with Applications (Discrete Mathematics and Its Applications)

## Richard A. Mollin

Language: English

Pages: 464

ISBN: 0849339871

Format: PDF / Kindle (mobi) / ePub

Beginning with the arithmetic of the rational integers and proceeding to an introduction of algebraic number theory via quadratic orders, Fundamental Number Theory with Applications reveals intriguing new applications of number theory. This text details aspects of computer science related to

• cryptography
• factoring
• primality testing
• complexity analysis
• computer arithmetic
• computational number theory
Fundamental Number Theory with Applications also covers:
• Carmichael numbers
• Dirichlet products
• Jacobsthal sums
• Mersenne primes
• perfect numbers
• powerful numbers
• self-contained numbers
Numerous exercises are included, testing the reader's knowledge of the concepts covered, introducing new and interesting topics, and providing a venue to learn background material.
Written by a professor and author who is an accomplished scholar in this field, this book provides the material essential for an introduction to the fundamentals of number theory.
• Hidden Markov Processes: Theory and Applications to Biology

The Best Writing on Mathematics 2012

Introduction to Linear Algebra - Instructor's Manual (3rd Edition)

Words: Notes on Verbal Width in Groups (London Mathematical Society Lecture Note Series)

Measure Theory and Probability

many primes of the form 4n − 1, n ∈ N. 1.3. Primes 35 Proof. If there are only finitely many, namely S = {p1 , p2 , . . . , pr }, then we r may form N = i=1 pi and set M = 4N − 1. Let p|M where p is prime. If p is of the form 4n−1, then p|N , so p|(M −4N ) = −1, a contradiction. This suffices to show that only primes of the form 4n + 1 divide M , since all odd integers are of the form 4n + 1 or 4n − 1 = 4(n − 1) + 3 since division of an odd number by 4 leaves a remainder of 1 or 3. Therefore,

where 1 ≤ j, k ≤ m. Since the cardinality is |S| = j=1 |Sj |, n = j=1 |Sj |. If |Sj | ≤ 1 for all j = 1, 2, . . . , m, then n ≤ m, a contradiction. Hence, at least one of the Sj has more than one element. The term pigeonhole principle comes from the notion of n + 1 pigeons flying into n holes. This principle, along with induction will be a very useful tool for us to use throughout the text. The following is a simple illustration. 36 1. Arithmetic of the Integers Example 1.18 Suppose that n ∈

. 7.2 The Equation ax2 + by2 + cz2 7.3 Bachet’s Equation . . . . . . . 7.4 Fermat’s Last Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 243 252 254 259 . . . =0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 265 274 277 281 . . . . . . . . Appendix A: Fundamental Facts . . .

easily checked that Zq is closed under multiplication and addition, namely for any integers r, s, with r, s ∈ Zq , then r · s ∈ Zq and r ± s ∈ Zq . We need this development in the following proof. Theorem 1.28 Lucas-Lehmer Test If p > 2 is prime, then Mp is prime whenever Mp divides the (p − 1)-st term of the sequence sj , which is defined by the recurrence sj = s2j−1 − 2, for any j > 1, where s1 = 4. Proof. Recall first Theorem 1.20 on page 36, which told us that if Mn is prime, then n is prime.

Thus, as with the shift transformation of which the affine cipher is a generalization, e = (a, b) since e is multiplication by a followed by addition of b modulo n, and d = (a−1 , −b) is subtraction of b followed by multiplication with a−1 . In the case of the shift transformation, the inverse is additive and in the case of the affine cipher, the inverse is multiplicative. Of course, these coincide precisely when a = 1. In either case, knowing e or d allows us to easily determine the other, so