DISCRETE MATHEMATICS LOOSELEAF

8th Edition

ISBN: 9781264309689

Author: ROSEN

Publisher: MCG

See similar textbooks

Videos

Textbook Question

Chapter 4.3, Problem 19E

Show that if 2 n -1 is prime, then n is prime. [Hint: Use the identify 2 a b -1=(2 a -1) ⋅ ( 2 a ( b − 1 ) + 2 a ( b − 2 ) +-+2 a + 1 ) .]

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 4.3, Problem 18E

Chapter 4.3, Problem 20E

Chapter 4 Solutions

DISCRETE MATHEMATICS LOOSELEAF

Ch. 4.1 - Prob. 1E Ch. 4.1 - Prove that if a is an integer other than o, then 1...Ch. 4.1 - Theorem 1 Let a, b, and c be integers, where ao ....Ch. 4.1 - Prove that part (iii) of Theorem 1 is true. Let...Ch. 4.1 - Show that if a|b|a, where a and b are integers,...Ch. 4.1 - Show that if a, b, c, and d are integers, where a...Ch. 4.1 - Show that if a, b, and c are integers, where ao ,...Ch. 4.1 - Prove or disprove that if a|bc, where a,b, and c...Ch. 4.1 - Prove that if a and b are integers and a divides...Ch. 4.1 - Prove that if a and b are nonzero integers, a...

Ch. 4.1 - Prove that if a is and integer that is not...Ch. 4.1 - Prove that if a is positive integer, then 4 does...Ch. 4.1 - What are the quotient and remainder when a) 19 is...Ch. 4.1 - What are the quotient and remainder when 44 is...Ch. 4.1 - What time does a 12-hour clock read a) 80 hours...Ch. 4.1 - What time does a 24-hour clock read a) 100 hours...Ch. 4.1 - Suppose that a and b are integers, a4(mod13) , and...Ch. 4.1 - Suppose that a and b are integers, a11(mod19) and...Ch. 4.1 - Show that if a and d are positive integers, then...Ch. 4.1 - Prove or disprove that if a, b, and d are integers...Ch. 4.1 - Let m be a positive integer. Show that a=b(modm)...Ch. 4.1 - Let m be a positive integer. Show that amodm=bmodm...Ch. 4.1 - Show that if n and k are positive integers, then...Ch. 4.1 - Show that if a is and integer d is and integer...Ch. 4.1 - Find a formula of the integer with smallest...Ch. 4.1 - Evaluate these quantities. -17 mod 2 144 mod 7...Ch. 4.1 - Evaluate these quantities. 13 mod 3 -97 mod 11 155...Ch. 4.1 - Find a div m and a mod m when a=111,m=99 ....Ch. 4.1 - Find a div m and a mod m when a=228,m=119 ....Ch. 4.1 - Find the integer a such that a43(mod23) and 22a0 ....Ch. 4.1 - Find the integer a such that a15(mod27) and 26a0 ....Ch. 4.1 - List five integers that are congruent to 4 modulo...Ch. 4.1 - List all integers between -100 and 100 that are...Ch. 4.1 - Decide whether each of these integers is congruent...Ch. 4.1 - Decide whether each of these integers is congruent...Ch. 4.1 - Find each of these values....Ch. 4.1 - Find each of these values. a)...Ch. 4.1 - Find each of these values. a) (192mod41)mod9 b) (...Ch. 4.1 - Find each of these values. a) ( 992mod32)3mod15 b)...Ch. 4.1 - Show that if a = b (mod m) and c= d (mod m), where...Ch. 4.1 - Prob. 41E Ch. 4.1 - Show that if a, b, c, and m are integers such that...Ch. 4.1 - Find counter Examples to each of these statements...Ch. 4.1 - Show that if n is an integer then n20 or 1 (mod...Ch. 4.1 - Prob. 45E Ch. 4.1 - Prove that if n is and odd positive integer, then...Ch. 4.1 - Prob. 47E Ch. 4.1 - Show that Zmwith addition modulo m, where m2 is an...Ch. 4.1 - Prob. 49E Ch. 4.1 - Show that the distributive property of...Ch. 4.1 - Write out the addition and multiplication tables...Ch. 4.1 - Write out the addition and multiplication tables...Ch. 4.1 - Determine whether each of the functions f(a)=adivd...Ch. 4.2 - Convert the decimal expansion of each of these...Ch. 4.2 - Convert the decimal expansion of each of these...Ch. 4.2 - Convert the binary expansion of each of these...Ch. 4.2 - Convert the binary expansion of each of these...Ch. 4.2 - Convert the octal expansion of each of these...Ch. 4.2 - Convert the binary expansion of each of these...Ch. 4.2 - Convert the hexadecimal expansion of each of these...Ch. 4.2 - Convert (BADFACED)16 from its hexadecimal...Ch. 4.2 - Convert (ABCDEF)16 from its hexadecimal expansion...Ch. 4.2 - Convert each of the integers in Exercise 6 from a...Ch. 4.2 - Convert (101101111011)2from its binary expansion...Ch. 4.2 - Convert (1 1000 0110 0011)2from its binary...Ch. 4.2 - Show that the hexadecimal expansion of a positive...Ch. 4.2 - Show that the binary expansion of a positive...Ch. 4.2 - Show that the octal expansion of a positive...Ch. 4.2 - Show that the binary expansion of a positive...Ch. 4.2 - Convert (7345321)8 to its binary expansion and (10...Ch. 4.2 - Give a procedure for converting from the...Ch. 4.2 - Give a procedure for converting from the octal...Ch. 4.2 - Explain how to convert from binary to base 64...Ch. 4.2 - Find the sum and the product of each of these...Ch. 4.2 - Find the sum and the product of each of these...Ch. 4.2 - Find the sum and the product of each of these...Ch. 4.2 - Find the sum and the product of each of these...Ch. 4.2 - Use Algorithm 5 to find 7644mod 645.Ch. 4.2 - Use Algorithm 5 to find 11644 mod 645.Ch. 4.2 - Use Algorithm 5 to find 32003mod 99.Ch. 4.2 - Use Algorithm 5 to find 1231001mod 101.Ch. 4.2 - Prob. 29E Ch. 4.2 - It Can be shown that every integer can be uniquely...Ch. 4.2 - Show that a positive integer is divisible by 3 if...Ch. 4.2 - Show that a positive integer is divisible by 11 if...Ch. 4.2 - Show that a positive integer is divisible by 3 if...Ch. 4.2 - Prob. 34E Ch. 4.2 - Prob. 35E Ch. 4.2 - Prob. 36E Ch. 4.2 - Prob. 37E Ch. 4.2 - Find the decimal expansion of the number with the...Ch. 4.2 - Find the decimal expansion of the number the 3n...Ch. 4.2 - Find the one's complement representations, using...Ch. 4.2 - What integer does each of the following one's...Ch. 4.2 - Prob. 42E Ch. 4.2 - Prob. 43E Ch. 4.2 - Prob. 44E Ch. 4.2 - Prob. 45E Ch. 4.2 - Answer Exercise 40, but this time find the two’s...Ch. 4.2 - Answer Exercise 41, if each expansion is tow’s...Ch. 4.2 - Prob. 48E Ch. 4.2 - Prob. 49E Ch. 4.2 - Answer Exercise 44 for two’s complement...Ch. 4.2 - Show that the integer m with two’s complement...Ch. 4.2 - Prob. 52E Ch. 4.2 - Prob. 53E Ch. 4.2 - Find the Cantor expansions of a) 2. b) 7. c) 19....Ch. 4.2 - Prob. 55E Ch. 4.2 - Describe an algorithm to add two integers from...Ch. 4.2 - Prob. 57E Ch. 4.2 - Multiply (1110)2 and (1010)2 by working through...Ch. 4.2 - Describe an algorithm for finding the difference...Ch. 4.2 - Estimate the number of bit operations used to...Ch. 4.2 - Devise an algorithm that, given the binary...Ch. 4.2 - Prob. 62E Ch. 4.2 - Prob. 63E Ch. 4.2 - Prob. 64E Ch. 4.2 - Show that algorithm 4 uses O (q log a) bit...Ch. 4.3 - Determine whether each of these integers is prime....Ch. 4.3 - Determine whether each of these integers is prime....Ch. 4.3 - Find the prime factorization of each of these...Ch. 4.3 - Find the prime factorization of each of these...Ch. 4.3 - Find the prime factorization of 10!.Ch. 4.3 - How may zeros are there at the end of 100!.Ch. 4.3 - Express in pseudocode the trial division algorithm...Ch. 4.3 - Express in pseudocode the algorithm described in...Ch. 4.3 - Show that am+1 is composite if a and m are...Ch. 4.3 - Show that if 2m+1 is and odd prime, then m=2n for...Ch. 4.3 - Show that log2 3 is an irrational number. Recall...Ch. 4.3 - Prove that for every positive integer n, there are...Ch. 4.3 - Prove or disprove that here are three consecutive...Ch. 4.3 - Which positive integers less than 12 are...Ch. 4.3 - Which positive integers less than 30 are...Ch. 4.3 - Determine whether the integers in each of these...Ch. 4.3 - Determine whether the integers in each of these...Ch. 4.3 - We call a positive integer perfect if it equals...Ch. 4.3 - Show that if 2n-1 is prime, then n is prime....Ch. 4.3 - Prob. 20E Ch. 4.3 - Find these values of the Euler -function. a) (4)...Ch. 4.3 - Show that n is prime if and only if (n)=n1 .Ch. 4.3 - What is the value of (pk) when p is prime and k is...Ch. 4.3 - What are the greatest common divisors of these...Ch. 4.3 - What are the greatest common divisors of these...Ch. 4.3 - What is the least common multiple of each pair in...Ch. 4.3 - What is the least common multiple of each pair in...Ch. 4.3 - Find god (1000, 625) and 1cm (1000, 625) and...Ch. 4.3 - Find gcd(92928, 123552) and lcm (92928, 123552),...Ch. 4.3 - If the product of tow integers is 273852711 and...Ch. 4.3 - Show that if a and b are positive integers, then...Ch. 4.3 - Use the Euclidean algorithm to find a) gcd(l, 5)....Ch. 4.3 - Use the Euclidean algorithm to find gcd(12, 18)....Ch. 4.3 - How many divisions are required to find gcd(21,...Ch. 4.3 - How many divisions are required to find gcd(34,...Ch. 4.3 - Show that if a and b are positive integers, then...Ch. 4.3 - Show that if a and b are positive integers, then...Ch. 4.3 - Use Exercise 37 to show that the integers...Ch. 4.3 - Using the method followed in Example17, express...Ch. 4.3 - Using the method followed in Example 17, express...Ch. 4.3 - Use the extended Euclidean algorithm to express...Ch. 4.3 - Use the extended Euclidean algorithm to express...Ch. 4.3 - Use the extended Euclidean algorithm to express...Ch. 4.3 - Use the extended Euclidean algorithm to express...Ch. 4.3 - Prob. 45E Ch. 4.3 - Find the smallest positive integer with exactly n...Ch. 4.3 - Can you find a formula or rule for the nth terms...Ch. 4.3 - Can you find a formula or rule for the nth term of...Ch. 4.3 - Prove that the product of any three consecutive...Ch. 4.3 - Show that if a, b, and m are integers such that m...Ch. 4.3 - Prove or disprove that n2-79n+1601 is prime...Ch. 4.3 - Prob. 52E Ch. 4.3 - Show that there is a composite integer in every...Ch. 4.3 - Adapt the proof in the text that there are...Ch. 4.3 - Adapt the proof in the text that there are...Ch. 4.3 - Prob. 56E Ch. 4.3 - Prob. 57E Ch. 4.4 - Show that 15 is an inverse of 7 modulo 26 Ch. 4.4 - Show that 937 is an inverse of 13 modulo 2436.Ch. 4.4 - By inspection (as discussed prior to Example 1),...Ch. 4.4 - By inspection (as discussed prior to Example 1),...Ch. 4.4 - Find an inverse of a modulo m for each of these...Ch. 4.4 - Find an inverse of a modulo m for each of these...Ch. 4.4 - Show that if a and m are relatively prime positive...Ch. 4.4 - Show that an inverse of a modulo m, where a is an...Ch. 4.4 - Solve the congruence 4x5(mod9) using the inverse...Ch. 4.4 - Solve the congruence 2x7(mod17) using the inverse...Ch. 4.4 - Solve each of these congruences using the modular...Ch. 4.4 - Solve each of these congruences using the modular...Ch. 4.4 - Find the solutions of the congruence...Ch. 4.4 - Find the solutions of the congruence...Ch. 4.4 - Show that if m is an integer greater than 1 and...Ch. 4.4 - a) Show that the positive integers less than 11,...Ch. 4.4 - Show that if p is prime, the only solutions of...Ch. 4.4 - a) Generalize the result in part (a) of Exercise...Ch. 4.4 - This exercise outline a proof of Fermat’s little...Ch. 4.4 - Use the construction the proof of the Chinese...Ch. 4.4 - Use the construction the proof of the Chinese...Ch. 4.4 - Solve the system of congruence x3(mod6) and...Ch. 4.4 - Solve the system of congruence in Exercise 20...Ch. 4.4 - Prob. 24E Ch. 4.4 - Write out in pseudocode an algorithm for solving a...Ch. 4.4 - Find all solutions, if any, to the system of...Ch. 4.4 - Find all solutions, if any, to the system of...Ch. 4.4 - Use the Chinese remainder theorem to show that an...Ch. 4.4 - Prob. 29E Ch. 4.4 - Complete the proof of the Chinese remainder...Ch. 4.4 - Which integers leave a remainder of 1 when divided...Ch. 4.4 - Which integers divisible by 5 but leave a...Ch. 4.4 - Use Fermat’s little theorem to find 7121 mod 13.Ch. 4.4 - Use Fermat’s little theorem to find 231002 mod 41.Ch. 4.4 - Use Fermat’s little theorem to show that if p is...Ch. 4.4 - Use Exercise 35 to find an inverse of 5 modulo 41.Ch. 4.4 - a) Show that 23401(mod11) by Fermat's little...Ch. 4.4 - a) Use Fermat’s little theorem to compute 3302 mod...Ch. 4.4 - a) Use Fermat’s little theorem to compute 52003...Ch. 4.4 - Show with the help of Fermat’s little theorem that...Ch. 4.4 - Show that if p is and odd prime, then every...Ch. 4.4 - Use Exercise 41 to determine whether M13=213-18191...Ch. 4.4 - Use Exercise 41 to deter mine whether...Ch. 4.4 - Show that if n is prime and b is a positive...Ch. 4.4 - Show that 2047 is a strong pseudoprime to the base...Ch. 4.4 - Show that 1729 is a Carmichael number.Ch. 4.4 - Show that 2821 is a Carmichael number.Ch. 4.4 - Show that if n=p1p2pk , where p1,p2,,pk are...Ch. 4.4 - Use Exercise 48 to show that every integer of the...Ch. 4.4 - Find the nonnegative integer a less than 28...Ch. 4.4 - Express each nonnegative integer a less than 15 a...Ch. 4.4 - Explain how to use the pairs found in Exercise 51...Ch. 4.4 - Solve the system of congruences that arises in...Ch. 4.4 - Show that 2 is a primitive root of 19.Ch. 4.4 - Find the discrete logarithms of 5 and 6 to the...Ch. 4.4 - Let p be and odd prime and r a primitive root of...Ch. 4.4 - Write out a table of discrete logarithms modulo 17...Ch. 4.4 - Which integers are quadratic residues of 11?Ch. 4.4 - Show that if p is an odd prime and a is an integer...Ch. 4.4 - Show that if p is and odd prime, then there are...Ch. 4.4 - Show that if p is and odd prime and a and b are...Ch. 4.4 - Prove Euler’s criterion, which states that if p is...Ch. 4.4 - Prob. 63E Ch. 4.4 - Show that if p is an odd prime, then -1 is a...Ch. 4.4 - Find all solutions of the congruence x2=29(mod35)...Ch. 4.4 - Prob. 66E Ch. 4.4 - Prob. 67E Ch. 4.5 - Which memory locations are assigned by the hashing...Ch. 4.5 - Which memory locations are assigned by the hashing...Ch. 4.5 - A parking lot has 31 visitor space, numbered from...Ch. 4.5 - Use the double hashing procedure we have described...Ch. 4.5 - Prob. 5E Ch. 4.5 - Prob. 6E Ch. 4.5 - Prob. 7E Ch. 4.5 - Write an algorithm in pseudocode for generating a...Ch. 4.5 - Find the first eight terms of the sequence of...Ch. 4.5 - Explain why both 3792 and 2916 would be bad...Ch. 4.5 - Find the sequence of pseudorandom numbers...Ch. 4.5 - Find the sequence of pseudorandom number generated...Ch. 4.5 - Suppose you received these bit strings over a...Ch. 4.5 - Prove that a parity check bit can detect an error...Ch. 4.5 - The first nine digits of the ISBN-10 of the...Ch. 4.5 - The ISBN-10 of the sixth edition of Elementary...Ch. 4.5 - Determine whether the check digit of the ISBN-10...Ch. 4.5 - Find the check digit for the USPS money orders...Ch. 4.5 - Determine whether each of these numbers is a valid...Ch. 4.5 - One digit in each of these identification numbers...Ch. 4.5 - One digit in each of these identification numbers...Ch. 4.5 - Determine which single digit errors are detected...Ch. 4.5 - Determine which transposition errors are detected...Ch. 4.5 - Determine the check digit for the UPCs that have...Ch. 4.5 - Determine whether each of the strings of 12 digits...Ch. 4.5 - Does the check digit of a UPC code detect all...Ch. 4.5 - Determine which transposition errors the check...Ch. 4.5 - Find the check digit a15 that follows each of...Ch. 4.5 - Determine whether each of these 15-digit numbers...Ch. 4.5 - Which errors in a single digit of a 15-digit...Ch. 4.5 - Can the accident transposition of two consecutive...Ch. 4.5 - For each of these initial seven digits of an ISSN,...Ch. 4.5 - Are each of these eight-digit codes possible...Ch. 4.5 - Does the check digit of an ISSN detect every...Ch. 4.5 - Does the check digit of an ISSN detect every error...Ch. 4.6 - Encrypt the message DO NOT PASS GO by translating...Ch. 4.6 - Encrypt the message STOP POLLUTION by translating...Ch. 4.6 - Encrypt the message WATCH YOUR SETEP by...Ch. 4.6 - Decrypt these messages that were encrypted using...Ch. 4.6 - Decrypt these messages encrypted using the shift...Ch. 4.6 - Suppose that when a long string of text is...Ch. 4.6 - Suppose that when a string of English text is...Ch. 4.6 - Suppose that the ciphertext DVE CFMV KF NFEUVI,...Ch. 4.6 - Suppose that the ciphertext ERC WY JJMGMIRXPC...Ch. 4.6 - Determine whether there is a key of which the...Ch. 4.6 - What is the decryption function for an affine...Ch. 4.6 - Find all pairs of integers key (a, b) for affine...Ch. 4.6 - Suppose that the most common letter and the second...Ch. 4.6 - Prob. 14E Ch. 4.6 - Decrypt the message EABW EFRO ATMAR ASIN, which is...Ch. 4.6 - Prob. 16E Ch. 4.6 - Suppose you have intercepted a ciphertext message...Ch. 4.6 - Use the Vigenère cipher with key BLUE to encrypt...Ch. 4.6 - The ciphertext OIKYWVHBX was produced by...Ch. 4.6 - Express the Vigenère cipher as a cryptosystem. To...Ch. 4.6 - Prob. 21E Ch. 4.6 - Once the length of the key string of a Vigènere...Ch. 4.6 - Prob. 23E Ch. 4.6 - In Exercised 24-27 first express your answers...Ch. 4.6 - In Exercised 24-27 first express your answers...Ch. 4.6 - In Exercised 24-27 first express your answers...Ch. 4.6 - In Exercised 24-27 first express your answers...Ch. 4.6 - Suppose that (n, e) is an RSA encryption key, with...Ch. 4.6 - Describe the steps that Alice and Bob follow when...Ch. 4.6 - Describe the steps that Alice and Bob follow when...Ch. 4.6 - In Exercises 31-32 suppose that Alice and Bob have...Ch. 4.6 - In Exercises 31-32 suppose that Alice and Bob have...Ch. 4.6 - We describe a basis key exchange protocol using...Ch. 4.6 - Prob. 34E Ch. 4.6 - Show that the Paillier cryptosystem is additively...Ch. 4 - Find 210 div 17 and 210 mod 17.Ch. 4 - a) Define what it means for a and b to be...Ch. 4 - Show if ab(modm) and cd(modm) , then a+cb+d(modm)...Ch. 4 - Describe a procedure for converting decimal (base...Ch. 4 - Prob. 5RQ Ch. 4 - Convert (7206)8 and (AOEB)16 to a binary...Ch. 4 - State the fundamental theorem of arithmetic.Ch. 4 - a) Describe a procedure for finding the prime...Ch. 4 - a) Define the greatest common divisor of two...Ch. 4 - a) How can you find a linear combination (with...Ch. 4 - a) What does it mean for a to be an inverse of a...Ch. 4 - a) How can an inverse of a modulo m be used to...Ch. 4 - a) State the Chinese remainder theorem. b) Find...Ch. 4 - Suppose that 2n11(modn) . Is n necessarily prime?Ch. 4 - Use Fermat’s little theorem to evaluate 9200 mod...Ch. 4 - Explain how the check digit is found for a 10-digi...Ch. 4 - Encrypt the meassage APPLES AND ORGANGES using a...Ch. 4 - a) What is the difference between a public key and...Ch. 4 - Explain how encryption and decryption are done in...Ch. 4 - Describe how two parties can share a secret key...Ch. 4 - The odometer on a car goes to up 100,000 miles....Ch. 4 - a) Explain why n div 7 equals the number of...Ch. 4 - Find four numbers congruent to 5 modulo 17.Ch. 4 - Show that if a and d are positive integers, then...Ch. 4 - Show that if acbc(modm) where a,b,c, and m are...Ch. 4 - Show that the sum of the squares of two odd...Ch. 4 - Show that if n2+1 is a perfect square, where n is...Ch. 4 - Prove that there are no solutions in integers x...Ch. 4 - Develop a test for divisibility of a positive...Ch. 4 - Develop a test for divisibility of a positive...Ch. 4 - Devise an algorithm for guessing a number between...Ch. 4 - Determine the complexity, in terms of the number...Ch. 4 - Show that an integer is divisible by 9 if and only...Ch. 4 - Show that a and b are positive irrational numbers...Ch. 4 - Prove there are infinitely many primes by showing...Ch. 4 - Find a positive integer n for which Qn=n!+1 is not...Ch. 4 - Use Dirichlet’s theorem, which states there are...Ch. 4 - Prove that if n is a positive integer such that...Ch. 4 - Show that every integer greater than 11 is the sum...Ch. 4 - Find the five smallest consecutive composite...Ch. 4 - Show that Goldbach’s conjecture, which states that...Ch. 4 - Find an arithmetic progression of length six...Ch. 4 - Prove that if f(x) is a nonconstant polynomial...Ch. 4 - How many zeros are at the end of the binary...Ch. 4 - Use the Euclidean algorithm to find the greatest...Ch. 4 - How many divisions are required to find gcd(144,...Ch. 4 - Find gcd(2n+1,3n+2) , where n is a positive...Ch. 4 - Show that if a and b are positive integers with ab...Ch. 4 - Adapt the proof that here are infinitely many...Ch. 4 - Explain why you cannot directly adapt the proof...Ch. 4 - Explain why you cannot directly adapt the proof...Ch. 4 - Show that if the smallest prime factor p of the...Ch. 4 - Prob. 33SE Ch. 4 - Find a set of four mutually relatively prime...Ch. 4 - For which positive integers n is n4+nn prime?Ch. 4 - Show that the system of congruences x2(mod6) and...Ch. 4 - Find all solutions of the system of congruences...Ch. 4 - a) Show that the system of congruences xa1(modm1)...Ch. 4 - Prove that 30 divisible n9-n for every nonnegative...Ch. 4 - Prove that n12-1 is divisible by 35 for every...Ch. 4 - Show that if p and q are distinct prime numbers,...Ch. 4 - Determine whether each of these 13-digit numbers...Ch. 4 - Show that the check digit of an ISBN-13 can always...Ch. 4 - Show that there are transpositions of two digit...Ch. 4 - Prob. 45SE Ch. 4 - Show that the check digit of an RTN can detect all...Ch. 4 - The encrypted version of message is LJMKG MG-MXF...Ch. 4 - Use the autokey cipher to encrypt the message NOW...Ch. 4 - Use the auto key cipher to encrypt the message THE...Ch. 4 - Given integers n and b, each greater than 1, find...Ch. 4 - Given the positive integers a, b, and m with m1 ,...Ch. 4 - Given a positive integer, find the cantor...Ch. 4 - Give a positive integer, determine whether it is...Ch. 4 - Given a positive integer, find the prime...Ch. 4 - Given two positive integers, find their greatest...Ch. 4 - Prob. 7CP Ch. 4 - Prob. 8CP Ch. 4 - Prob. 9CP Ch. 4 - Given n liner congruences modulo pairwise...Ch. 4 - Prob. 11CP Ch. 4 - Prob. 12CP Ch. 4 - Prob. 13CP Ch. 4 - Prob. 14CP Ch. 4 - Prob. 15CP Ch. 4 - Find the original plaintext message from the...Ch. 4 - Prob. 17CP Ch. 4 - Prob. 18CP Ch. 4 - Given a valid RSA key (n, e), and the primes p and...Ch. 4 - Given a message encrypted using the RSA...Ch. 4 - Generate a shared key using the Diffie-Hellman key...Ch. 4 - Prob. 22CP Ch. 4 - Determine whether 2p1 is prime for each of the...Ch. 4 - Prob. 2CAE Ch. 4 - Prob. 3CAE Ch. 4 - Prob. 4CAE Ch. 4 - Prob. 5CAE Ch. 4 - Prob. 6CAE Ch. 4 - Prob. 7CAE Ch. 4 - Prob. 8CAE Ch. 4 - Prob. 9CAE Ch. 4 - Prob. 1WP Ch. 4 - Explain how probabilistic primality tests are used...Ch. 4 - The question of whether there are infinitely many...Ch. 4 - Prob. 4WP Ch. 4 - Describe the algorithms that are actually used by...Ch. 4 - Describe the history of the Chinese remainder...Ch. 4 - When are the numbers of a sequence truly random...Ch. 4 - Prob. 8WP Ch. 4 - Prob. 9WP Ch. 4 - Prob. 10WP Ch. 4 - Prob. 11WP Ch. 4 - Describe how public key cryptography can be used...Ch. 4 - Describe the Rabin public key cryptosystem,...Ch. 4 - Explain why it would be unsuitable to use p, where...Ch. 4 - Prob. 15WP Ch. 4 - Explain the steps that Gentry used to construct a...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

Show that if 2 n -1 is prime, then n is prime. [Hint: Use the identify 2 a b -1=(2 a -1) ⋅ ( 2 a ( b − 1 ) + 2 a ( b − 2 ) +-+2 a + 1 ) .]

Solution Summary: The author explains how to prove that 2n-1 is not prime.

Videos

Want to see the full answer?

Chapter 4 Solutions