Explain why you cannot directly adapt the proof that there

Problem 1E The odometer on a car goes to up 100,000 miles. The present owner of a car bought it when the odometer read 43,179 miles. He now wants to sell it: when you examine the car for possible purchase, you notice that the odometer reads 89,697 miles. What can you conclude about how many miles he drove the car, assuming that the odometer always worked correctly?

Problem 49E Use the autokey cipher to encrypt the message THE DREAM OF REASON (ignoring spaces) using a) the keystream with seed X followed by letters of the plaintext. ________________ b) the keystream with seed X followed by letters of the ciphertext.

Problem 2E a) Explain why n div 7 equals the number of complete weeks in n days, ________________ b) Explain why n div 24 equals the number of complete days in n hours.

Problem 4E Show that if a and d are positive integers, then there are integers q and r such that a = dq + r where –d/2 < r d/2.

Problem 3E Find four numbers congruent to 5 modulo 17.

Problem 5E Show that if ac ? bc (mod m), where a.b.c, and m are integers with m > 2, and d = gcd(m,c), then a ? b (mod m/d).

Problem 6E Show that the sum of the squares of two odd integers cannot be the square of an integer.

Problem 7E Show that if n2 + 1 is a perfect square, where n is an integer, then n is even.

Problem 9E Develop a test for divisibility of a positive integer n by 8 based on the binary expansion of n.

Problem 8E Prove that there are no solutions in integers x and y to the equation x2 – 5y2 = 2. [Hint: Consider this equation modulo 5.]

Problem 10E Develop a test for divisibility of a positive integer n by 3 based on the binary expansion of n.

Problem 11E Devise an algorithm for guessing a number between 1 and 2n – 1 by successively guessing each bit in its binary expansion.

Problem 12E Determine the complexity, in terms of the number of guesses, needed to determine a number between 1 and 2n – 1 by successively guessing the bits in its binary expansion.

Problem 13E Show that an integer is divisible by 9 if and only if the sum of its decimal digits is divisible by 9.

Problem 14E Show that if a and b are positive irrational numbers such that 1/a + 1/b = 1, then every positive integer can be uniquely expressed as either ?ka? or ?kb? for some positive integer k.

Problem 15E Prove there are infinitely many primes by showing that Qn = n! + 1 must have a prime factor greater than n whenever n is a positive integer.

Problem 16E Find a positive integer n for which Qn =n! + 1 is not prime.

Problem 17E Use Dirichlet’s theorem, which states there are infinitely many primes in every arithmetic progression ak + b where gcd(a, b) = 1, to show that there are infinitely many primes that have a decimal expansion ending with a 1.

Problem 18E Prove that if n is a positive integer such that the sum of the divisors of n is n + 1, then n is prime.

Problem 19E Show that every integer greater than 11 is the sum of two composite integers.

Problem 20E Find the five smallest consecutive composite integers.

Problem 21E Show that Goldbach’s conjecture, which states that every even integer greater than 2 is the sum of two primes, is equivalent to the statement that every integer greater than 5 is the sum of three primes.

Problem 22E Find an arithmetic progression of length six beginning with 7 that contains only primes.

Problem 23E Prove that if f(x) is a nonconstant polynomial with integer coefficients, then there is an integer y such that f(y) is composite. [Hint: Assume thai f(x0) = p is prime. Show that p divides f(x0 + kp) for all integers k. Obtain a contradiction of the fact that a polynomial of degree n, where n > 1, takes on each value at most n times.]

Problem 24E How many zeros are at the end of the binary expansion of 10010!?

Problem 25E Use the Euclidean algorithm to find the greatest common divisor of 10,223 and 33,341.

Problem 26E How many divisions are required to find gcd(l44, 233) using the Euclidean algorithm?

Problem 27E Find gcd(2n +1.3n + 2), where n is a positive integer. [Hint: Use the Euclidean algorithm.]

Problem 28E a) Show that if a and b are positive integers with a ? b, then gcd(a, b) = a if a = b, gcd(a,b) = 2 gcd(a/2, b/2) if a and b are even, gcd(a, b) = gcd(a/2, b) if a is even and b is odd. and gcd(a, b) = gcd(a – b, b) if both a and b are odd. ________________ b) Explain how to use (a) to construct an algorithm for computing the greatest common divisor of two positive integers that uses only comparisons, subtractions, and shifts of binary expansions, without using any divisions. ________________ c) Find gcd(1202. 4848) using this algorithm.

Problem 29E Adapt the proof that there are infinitely many primes (Theorem 3 in Section 4.3) to show that are infinitely many primes in the arithmetic progression 6k + 5. k = 1, 2,….

Problem 30E Explain why you cannot directly adapt the proof that there are infinitely many primes (Theorem 3 in Section 4.3) to show that there are infinitely many primes in the arithmetic progression 3k + 1, k = 1, 2,…

Problem 31E Explain why you cannot directly adapt the proof that there are infinitely many primes (Theorem 3 in Section 4.3) to show that are infinitely many primes in the arithmetic progression 4k + 1, k = 1,2,....

Show that if the smallest prime factor \(p\) of the positive integer \(n\) is larger than \(\sqrt[3]{n}\), then \(n / p\) is prime or equal to 1 . A set of integers is called mutually relatively prime if the greatest common divisor of these integers is 1. ________________ Equation Transcription: Text Transcription: p n \sqrt[3]{n} n / p.

Problem 33E Determine whether the integers in each of these sets are mutually relatively prime. a) 8, 10, 12 ________________ b) 12,15,25 ________________ c) 15,21,28 ________________ d) 21, 24,28,32

Problem 34E Find a set of four mutually relatively prime integers such that no two of them are relatively prime.

Problem 35E For which positive integers n is n4 + 4n prime?

Problem 36E Show that the system of congruences x ? 2 (mod 6) and x ? 3 (mod 9) has no solutions.

Problem 37E Find all solutions of the system of congruences x ? 4 (mod 6) and x ? 13 (mod 15).

Problem 38E a) Show that the system of congruences.x: ? a2(modm1) and x ? a2 (mod m2), where a1, a2. m1, and m2 are integers with m1 >0 and m2 > 0, has a solution if and only if gcd(m1, m2) | a1 – a2. ________________ b) Show that if the system in part (a) has a solution, then it is unique modulo 1cm(m1, m2).

Problem 39E Prove that 30 divides n9 – n for every nonnegative integer n.

Problem 40E Prove that n12 – 1 is divisible by 35 for every integer n for which gcd(n, 35) = 1.

Problem 41E Show that if p and q are distinct prime numbers, then pq-1 + qp-l = 1 (mod pq).

Problem 42E Determine whether each of these 13-digit numbers is a valid ISBN-13. a) 978-0-073-20679-1 ________________ b) 978-0-45424-521-1 ________________ c) 978-3-16-148410-0 ________________ d) 978-0-201-10179-9

Problem 43E Show that the check digit of an ISBN –13 can always delect a single error.

Problem 44E Show that there are transpositions of two digits that are not detected by an ISBN-13. A routing transit number (RTN) is a bank code used in the United States which appears on the bottom of checks. The most common form of an RTN has nine digits, where the last digit is a check digit. If d1d2…d9 is a valid RoTN. the congruence 3(d1 + d4 + d7) +7(d2 + d5 + d8) + (d3 + d6 + d9) = 0 (mod 10) must hold.

Problem 45E Show that if d1d2 ... d9) is a valid RTN, then d9 = 7(d1 + d4 + d7) + 3(d2 + d5 + d8) + 9(d3 +d6) mod 10. Furthermore, use this formula to find the check digit that follows the eight digits 11100002 in a valid RTN.

Problem 46E Show that the check digit of an RTN can detect all single errors and determine which transposition errors an RTN check digit can catch and which ones it cannot catch.

Problem 26E Use Algorithm 5 to find 11644 mod 645.

Problem 47E The encrypted version of a message is LJMKG MGMXF QEXMW. If it was encrypted using the affine cipher f (p) = (7p + 10) mod 26, what was the original message? Autokev ciphers are ciphers where the n th letter of the plaintext is shifted by the numerical equivalent of the nth letter of a keystream. The keystream begins with a seed letter; its subsequent letters are constructed using either the plaintext or the ciphertext. When the plaintext is used, each character of the keystream, after the first, is the previous letter of the plaintext. When the ciphertext is used, each subsequent character of the keystream, after the first, is the previous letter of the ciphertext computed so far. In both cases, plaintext letters are encrypted by shifting each character by the numerical equivalent of the corresponding keystream letter.