please
complete exercises 10.4, 10.5, 10.6, 10.7 and 10.9, thank you so
much! (I dont understand...
10.4 Exercise. Show that the algorithm descrihed in Question 3.6 for com puting a (mod n) is a polynomial time algorithm in the number of digits in r In the next scrics of problems you will cxplore the usc of this opcration as a means of testing for primality by starting with a familiar theorem. Theorem (Fermat's Little Theorem). Lef p be a prime. Then for all natural numbers a less than p, a 1 (mod p). Fermat's Little Theorem can be useful for showing cerlain numbers are composite 10.5 Exercise. State the contrapositive of Fermat's Little Theorem. 10.6 Exercise. Use Fermat 's Little Theorem to show that n=737 is composite Unfortunately, the statement of Fermat's Little Theorem lacks the logical. connoctive "if and only if" that we desire for a primality test. This raises the question of whether the converse to Fermat's Little Theorem is true. 10.7 Question. State the converse to Fermat's Little Theorem. Do you think the comverse to Fermat 's Little Theorem is true? 10.8 Theorem. Let n be a natural mumber greater than 1. Thenn is prime fand only if a-l1 (mod n) for all natural mumbers a less than n. 10.9 Question. Does the previous theorem give a polynomial or expaonen- tial time primality test? Inventing polynomial time primality t tests is quite a challenge. One way to saivage some good from Fermat's Little Theorcm is to weaken our demand of certainty. What if instead we look for a probable prime test, by which we mean a statement of the form then n is very likely to be prime. то where the blank would he filled in by some testable condition on n. 10.10 Exercise. Commute 2"- (mod n) for all odd mumbers n less than 100. If you have access to a computer, and some computing software, keep going. Test any conjectures you make along the way. State a probahle prime est based on your observations.
10.4 Exercise. Show that the algorithm descrihed in Question 3.6 for com puting a (mod n) is a polynomial time algorithm in the number of digits in r In the next scrics of problems you will cxplore the usc of this opcration as a means of testing for primality by starting with a familiar theorem. Theorem (Fermat's Little Theorem). Lef p be a prime. Then for all natural numbers a less than p, a 1 (mod p). Fermat's Little Theorem can be useful for showing cerlain numbers are composite 10.5 Exercise. State the contrapositive of Fermat's Little Theorem. 10.6 Exercise. Use Fermat 's Little Theorem to show that n=737 is composite Unfortunately, the statement of Fermat's Little Theorem lacks the logical. connoctive "if and only if" that we desire for a primality test. This raises the question of whether the converse to Fermat's Little Theorem is true. 10.7 Question. State the converse to Fermat's Little Theorem. Do you think the comverse to Fermat 's Little Theorem is true? 10.8 Theorem. Let n be a natural mumber greater than 1. Thenn is prime fand only if a-l1 (mod n) for all natural mumbers a less than n. 10.9 Question. Does the previous theorem give a polynomial or expaonen- tial time primality test? Inventing polynomial time primality t tests is quite a challenge. One way to saivage some good from Fermat's Little Theorcm is to weaken our demand of certainty. What if instead we look for a probable prime test, by which we mean a statement of the form then n is very likely to be prime. то where the blank would he filled in by some testable condition on n. 10.10 Exercise. Commute 2"- (mod n) for all odd mumbers n less than 100. If you have access to a computer, and some computing software, keep going. Test any conjectures you make along the way. State a probahle prime est based on your observations.