Discrete Mathematics: Elementary and Beyond

6.8 Strange Numbers 111 The key to solving this problem is the Euclidean Algorithm. Let us com- pute the greatest common divisor ...

112 6. Integers, Divisors, and Primes (we could replace−3 by its remainder 44 modulo 47 if we wanted to keep numbers positive, b ...

6.8 Strange Numbers 113 Division.Next, we want to divide the equation by 5. This is what we discussed above: We have to use the ...

114 6. Integers, Divisors, and Primes We can write this as (x−1)(x−2)≡0 (mod 53). One of the factors on the left-hand side must ...

6.9 Number Theory and Combinatorics 115 If there is a number among thesennumbers that is divisible byn, then we have found what ...

116 6. Integers, Divisors, and Primes Finally, the numbers divisible by all of 2, 3, 5 are precisely those that are divisible by ...

6.10 How to Test Whether a Number is a Prime? 117 6.10 How to Test Whether a Number is a Prime?......... Is 123,456 a prime? Of ...

118 6. Integers, Divisors, and Primes starting from a small number. Let us show how to do a similar trick if the exponent is a l ...

6.10 How to Test Whether a Number is a Prime? 119 Unfortunately, the answer is yes. The smallest such number is 341 = 11·31. Thi ...

120 6. Integers, Divisors, and Primes Fermat’s Theorem tells us that primes do pass the Fermat test for every base. On the other ...

6.10 How to Test Whether a Number is a Prime? 121 prime ton. In other words, they satisfy n|an−^1 − 1 for everyasuch that gcd(n, ...

122 6. Integers, Divisors, and Primes So this algorithm, when repeated sufficiently often, tests primality with error probabilit ...

6.10 How to Test Whether a Number is a Prime? 123 6.10.10 Show that a number with 30 digits cannot have more than 100 prime fact ...

This page intentionally left blank ...

7 Graphs 7.1 Even and Odd Degrees..................... We start with the following exercise (admittedly of no practical signifi- ...

126 7. Graphs Now we can at least experiment with smaller numbers. Let us have, say, 5 people: Alice, Bob, Carl, Diane, and Eve. ...

7.1 Even and Odd Degrees 127 Coming back to our problem, we see that we can represent the party by a graph very conveniently. Ou ...

128 7. Graphs FIGURE 7.3. Some graphs with an even number of nodes. Black circles mark nodes of even degree. the number of nodes ...

7.1 Even and Odd Degrees 129 Thus if the number of nodes with odd degree was even before adding the new edge, it remained even a ...

130 7. Graphs 7.1.6How many graphs are there on 20 nodes? (To make this question precise, we have to make sure we know what it m ...