Homework assignments for M325K ==================================== Nr Section : Problems ------------------------------------ [1] 1.1 : 34,38,48,49 1.2 : 14,20,22,46 1.3 : 5,42 2.1 : 18,26 ------------------------------------ due Fri Jul 14 [2] 2.2 : 2,21,32 2.3 : 22,42 2.4 : 30 5.1 : 11,28 5.2 : 9 5.3 : 16,17,27 ------------------------------------ due Tue Jul 18 [3] 3.1 : 28,32,45,49,54 3.3 : 26 ... : A1,A2,A3,A4 (see below) ------------------------------------ due Fri Jul 21 [4] 3.4 : 18,41 ... : A5,A6,A7 (see below) ... : B1,B2,B3 (see below) ------------------------------------ due Tue Jul 25 [5] ... : B4,B5,B6 (see below) 4.2 : 12 4.3 : 17,25 4.4 : 8a ------------------------------------ due Fri Jul 28 [6] ... : A8,A9,B7 (see below) 6.2 : 20c 6.3 : 25 6.4 : 20 6.5 : 16 ------------------------------------ due Tue Aug 1 [7] ... : B8,C2,D1 (see below) 10.2 : 19,20,29 10.3 : 24,42 10.4 : 32 ------------------------------------ due Fri Aug 4 [8] 7.2 : 13,18,50 7.3 : 33 7.4 : 20,22,26 7.5 : 27,30 ------------------------------------ due Tue Aug 8 [ ] ... : D3 (see below) 7.5 : 35,38 11.1 : 20,29,35 ... check back =================================================== NOTE: NO LATE HOMEWORK Unless stated otherwise in class, homework is assigned every Tuesday and Friday, and collected in class the following Friday and Tueday, respectively. Late homework will not be accepted. But as announced, the lowest homework score gets dropped before computing the homework average. ================================================= PROBLEMS A1..A7 (all numbers here are integers) A1. Show that the product of any two integers of the form 4k+1 is again of this form. A2. Show that the product of any three consecutive integers is divisible by 6. A3. Show that 3 divides k^{3}-k. A4. Let a=qb+r, with b nonzero. Show that every common divisor of a and b is also a common divisor of b and r, and vice versa. A5. Show that 8n+3 and 5n+2 are relatively prime. A6. Show that if kn and km are not both zero, then gcd(km,kn)=|k|*gcd(m,n). A7. Find d=gcd(1234,981), and find m,n such that 1234m+981n=d. A8. Show that gcd(a,bc)=1 if an oly if gcd(a,b)=gcd(a,c)=1. A9. For every positive integer n, define Phi(n) to be the number of integers in {1,2,...,n} that are relatively prime to n. (This is known as Euler's Phi function.) Determine Phi(98000). =================================================== PROBLEMS B1..B8 (all numbers here are integers) (Z stands for the set of all integers) In this problem set, m is some fixed but arbitrary positive integer. Definition: We writea~biff m divides b-a. (In words: a is congruent to b modulo m.) B1. Show that "~" is an equivalence relation on Z, meaning that for any a,b,c (1) a~a (reflexivity) (2) if a~b then b~a (symmetry) (3) if a~b and b~c then a~c (transitivity) B2. Show that a~b if and only if a and b leave the same remainder in the division by m. B3. Define [a]={n in Z | n~a}. (These sets are called equivalence classes modulo m.) Show that P={[0],[1],...,[m-1]} is a partition of Z, meaning that (1) each set in P is non-empty (2) the sets in P are mutually disjoint (3) the union of all sets in P is Z B4. Assume that A~a and B~b. Show that (1) (A+B)~(a+b) (2) (A*B)~(a*b) (3) A^{n}~ a^{n}for every positive n Hint: Prove (3) by induction on n, using (2) B5. Assume here that m=11. Show that 7^{3}~ 2 and 2^{5}~ -1. Use the rules from B4 (where needed) to justify the congruences 29^{49}~ 7^{49}~ 7*(7^{3})^{16}~ 7*2^{16}~ 7*2*(2^{5})^{3}~ 7*2*(-1)^{3}~ -14 ~ 8 (where a~b~c~... means a~b and b~c and c~...) Conclude that the remainder in the division of 29^{49}by 11 is 8. B6. Following the ideas used in B5, compute the remainder in the division of 95^{95}by 41. B7. Assuming m is a prime, show that if x^{2}~ 1 then x ~ 1 or x ~ -1. Does the same hold if m is any positive integer? B8. Let a and b be integer, with gcd(a,m)=1. Show that the congruence ax ~ b has a solution x. (Hint: Use a fact about linear combinations ax+my.) Show that the solution is unique modulo m, that is, if ax_{1}~ b and ax_{2}~ b then x_{1}~ x_{2}. Notice: This also proves that if ax_{1}~ ax_{2}then x_{1}~ x_{2}(cancellation law). B9. Consider the sets defined in B3, and define [u]+[v]="the set of all sums x+y with x in [u] and y in [v]", [u]*[v]="the set of all products x*y with x in [u] and y in [v]". Using the results from B4, if desired, show that [u]+[v]=[u+v]=[r], where r is the remainder in the division of u+v by m. Similarly, show that [u]*[v]=[u*v]=[r], where r is the remainder in the division of u*v by m. This defines an addition and multiplication on P. Show that the distributive property holds. Make an "addition table" and "multiplication table" for the case m=5. =================================================== PROBLEMS C1..C2 These problems use the definitions at the bottom of this page. (A_{x}B denotes the product of a set A with a set B) C1. Consider the sets from B3 and B9. The facts proved in B8 and B9 show (essentially) that (P,+,*) is a field when m is a prime. Show that if m is not a prime, then (P,+,*) is not a field. C2. Let S=Z_{x}(Z-{0}), that is, S is the set of all ordered pairs (a,b) of integers, with b nonzero. On this set S, consider the relation R, defined such that (a,b) R (c,d) if and only if ad=bc. Prove that R is an equivalence relation on S. Thus, R defines a partition Q of S into equivalence classes. For every u in S, denote by [u] the equivalence class containing u. We can define an addition and multiplication on S, by setting (a,b)+(c,d)=(ad+bc,bd) and (a,b)*(c,d)=(ac,bd). Let [u]+[v]={s in S | (s R x+y) for some x in [u] and some y in [v]} and [u]*[v]={s in S | (s R x*y) for some x in [u] and some y in [v]}. Show that [u]+[v]=[u+v] and [u]*[v]=[u*v]. This implies that (Q,+) and (Q,*) have the closure property. Show that every [u] other than [(0,1)] has a multiplicative inverse. Note: With some more work, one can show that (Q,+,*) is a field. [(a,b)] is commonly written as a/b, and a/1 as a. =================================================== PROBLEMS D1..D3 (all numbers here are integers) Definition: We writea≡b (mod m)iff m divides b-a. (In words: a is congruent to b modulo m.) D1. Show that if p is a prime larger than 3, then the numbers {2,3,...,p-2} can be grouped into pairs {a_{i},x_{i}} (distinct numbers) such that a_{i}x_{i}≡1 (mod p). (Hint: B7 and B8 might be useful.) Do this explicitly for p=11. Prove Wilson's Theorem: If p is a prime, then (p-2)! ≡1 (mod p). D2. Let a be an integer and p a prime not dividing a. Define a function f from X={a,2a,3a,...,(p-1)a} to Y={1,2,3,...,p-1} by setting f(x) equal to the remainder of x in the division by p. Show that f is one-to-one and onto. (Hint: B8 might be useful.) Notice: This shows that f(a)*f(2a)*f(3a)*...*f((p-1)a) = (p-1)! Turning this eqation into an equivalence (modulo p) by replacing f(x) by x, and then cancelling (p-1)!, proves Fermat's Little Theorem: If p is a prime not dividing a, then a^{p-1}≡1 (mod p). D3. Use Fermat's Little Theorem to compute the remainder in the division of 10^{500}by 17. =================================================== SOME DEFINITIONS Let G be a set (subset of some universal set U). A function • from G_{x}G to U is called abinary operationon G. We will write also write A•B in place of •(A,B). Let now • be a binary operation on G. We say that (G,•) has theclosureproperty iff for all A and B in G, A•B belongs to G. We say that (G,•) has theassociativityproperty iff for all A,B,C in G, (A•B)•C=A•(B•C). We say that (G,•) has theidentityproperty iff there exists an element I in G, such that for all A in G, A•I=A and I•A=A. Assuming the identity property, aninverseof an element A in G is an element A' in G such that A•A'=I and A'•A=I. We say that (G,•) has theinverseproperty iff every element in G has an inverse. We say that (G,•) is agroupiff it has the closure, associativity, identity, and inverse properties. We say that (G,•) iscommutativeiff for all A,B in G, A•B=B•A. Given two binary operations + and * on G, we say that (G,+,*) has the (left and right)distributiveproperty iff for all A,B,C in G, A*(B+C)=(A*B)+(A*C) and (A+B)*C=(A*C)+(B*C). We call (G,+,*) afieldiff (G contains at least 2 elements and) (G,+) and (G-{0},*) are commutative groups, and (G,+,*) has the distributive property. Here, 0 denotes the identity element of (G,+).