Solved: Two integers that have no common factors (except 1) are said to be relatively

Chapter 10, Problem T1

(choose chapter or problem)

Two integers that have no common factors (except 1) are said to be relatively prime. Given a positive integer n, let Sn = {a1, a2, a3,...,am}, where a1 < a2 < a3 < < am, be the set of all positive integers less than n and relatively prime to n. For example, if n = 9, then S9 = {a1, a2, a3,...,a6}={1, 2, 4, 5, 7, 8} (a) Construct a table consisting of n and Sn for n = 2, 3,..., 15, and then compute -m k=1 ak and -m k=1 ak (mod n) in each case. Draw a conjecture for n > 15 and prove your conjecture to be true. [Hint: Use the fact that if a is relatively prime to n, then n a is also relatively prime to n.] (b) Given a positive integer n and the set Sn, let Pn be the m m matrix Pn = a1 a2 a3 am1 am a2 a3 a4 am a1 a3 a4 a5 a1 a2 . . . . . . . . . ... . . . . . . am1 am a1 am3 am2 am a1 a2 am2 am1 so that, for example, P9 = 124578 245781 457812 578124 781245 812457 Use a computer to compute det(Pn) and det(Pn)(mod n) for n = 2, 3,..., 15, and then use these results to construct a conjecture. (c) Use the results of part (a) to prove your conjecture to be true. [Hint: Add the first m 1 rows of Pn to its last row and then use Theorem 2.2.3.] What do these results imply about the inverse of Pn (mod n)?