Contents xi 37 The Chinese Remainder Theorem 320 Solving One Equation 320 Solving Two Equations 322 Recap 324 Exercises 324 38 Factoring 325 Infinitely Many Primes 327 A Formula for Greatest Common Divisor 328 Irrationality of√2 329 Recap 331 Exercises 331 Chapter 7 Self Test 335 8 Algebra 337 39 Groups 337 Operations 337 Properties of Operations 338 Groups 340 Examples 342 Recap 345 Exercises 345 40 Group Isomorphism 347 The Same? 347 Cyclic Groups 349 Recap 352 Exercises 352 41 Subgroups 353 Lagrange's Theorem 356 Recap 359 Exercises 359 42 Fermat's Little Theorem 362 First Proof 362 Second Proof 363 Third Proof 366 Euler's Theorem 367 Primality Testing 368 Recap 369 Exercises 369 43 Public Key Cryptography l:Introduction 370 The Problem:Private Communication in Public 370 Factoring 370Contents xi 37 The Chinese Remainder Theorem 320 Solving One Equation 320 Solving Two Equations 322 Recap 324 Exercises 324 38 Factoring 325 \ Infinitely Many Primes 327 A Formula for Greatest Common Divisor 328 Irrationality of v'2 329 Recap 331 Exercises 3 31 Chapter 7 Self Test 335 8 Algebra 337 39 Groups 337 Operations 337 Properties of Operations 338 Groups 340 Examples 342 Recap 345 Exercises 345 40 Group Isomorphism 347 The Same? 347 Cyclic Groups 349 Recap 352 Exercises 352 41 Subgroups 353 - Lagrange's Theorem 356 Recap 359 \, Exercises 359 42 Fermat's Little Theorem 362 First Proof 362 Second Proof 363 Third Proof 366 Euler's Theorem 367 Primality Testing 368 Recap 369 Exercises 369 43 Public Key Cryptography 1: Introduction 370 The Problem: Private Communication in Public 370 Factoring 370