MATH 456 Midterm: MATH456 ROSENBERG-J SPRING2013 0101 MID SOL 1

• School: University of Maryland
• Department: Mathematics
• Course: MATH 456
• Professor: All

Document Summary

Friday, april 19, 2013: (10 points) the number n = 5893 is a product of two primes. We have 772 62 = (77 + 6) (77 6) 0 mod n. thus n divides 83 71. Hint: the prime p has a very special form. Note: it suf ces to give an algorithm for computing x; you don"t actually have to carry it out. Since p 1 = 216, every integer in the range from 1 to p 1 has order mod p equal to 2j for j 16. We compute x rst modulo 2, then modulo 4, then modulo 8, etc. Say that x = x0 + 2x1 + + 215x15, where xj = 0 or 1 for each j. 3x0+2x1+ 123 (mod p) and raise both sides to the power 215. 1 (mod p), we see (3x0)215 (mod p). 123215 (mod p) and raise both sides to the power 214.