Discrete Mathematics: Elementary and Beyond

6.3 Factorization into Primes 91 So assume that there exists an integer with two different factorizations; call such an integer ...

92 6. Integers, Divisors, and Primes Proof.Suppose, by way of contradiction, that there are negative integers that are even. Cal ...

6.4 On the Set of Primes 93 6.3.6Prove that ifpis a prime, then √ pis irrational. More generally, prove that ifnis an integer th ...

94 6. Integers, Divisors, and Primes must be at least two, except for 2 and 3. Two primes whose difference is 2 are calledtwin p ...

6.4 On the Set of Primes 95 0 50 100 150 200 250 300 400 800 1200 1600 2000 FIGURE 6.3. The graph ofπ(n) from 1 to 2000. Theorem ...

96 6. Integers, Divisors, and Primes This is a lot of primes! Comparing this with the total number of positive integers with 200 ...

6.5 Fermat’s “Little” Theorem 97 Pierre de Fermat 6.5 Fermat’s “Little” Theorem Primes are important because we can compose ever ...

98 6. Integers, Divisors, and Primes Herepdivides the numerator, but not the denominator, since all factors in the denominator a ...

6.6 The Euclidean Algorithm 99 (c) Use (a) to give a new proof of Lemma 6.5.2. 6.5.3Imagine numbers written in basea, with at mo ...

100 6. Integers, Divisors, and Primes The trouble with this method is that it is very difficult to find the prime factorization ...

6.6 The Euclidean Algorithm 101 Else (ifa= 0), returnbas the g.c.d. and halt. When you carry out the algorithm, especially by ...

102 6. Integers, Divisors, and Primes 6.6.9Describe the Euclidean Algorithm applied to two consecutive Fibonacci numbers. Use yo ...

6.6 The Euclidean Algorithm 103 the lemma above gives the bound log 2 Fk+log 2 Fk+1≈log 2  √^1 5 ( 1+ √ 5 2 )k +log 2  √^1 ...

104 6. Integers, Divisors, and Primes (d) Show that this algorithm, when applied to two 100-digit integers, does not take more t ...

6.7 Congruences 105 6.7 Congruences........................... Notation is not part of the bare logical structure of mathematics ...

106 6. Integers, Divisors, and Primes andtransitivity, a≡b (modm),b≡c (modm)=⇒ a≡c (modm). These are trivial if we think of the ...

6.8 Strange Numbers 107 6.7.3How would you definea≡b(mod 0)? 6.7.4(a) Find two integersaandbsuch that 2a≡ 2 b(mod 6), buta≡ b(m ...

108 6. Integers, Divisors, and Primes All this is nothing new if we think of “Monday” as 1, “Tuesday” as 2, etc., and realize th ...

6.8 Strange Numbers 109 (wherexandyare the numbers corresponding to the daysXandY), and so 7 is a divisor of (x−y)5. But 5 is no ...

110 6. Integers, Divisors, and Primes the subtraction table, since in this fielda+b=a−bfor everyaandb (check!), nor the division ...