Homework assignments for M328K
====================================
Nr Section : Problems
------------------------------------
[1] 1.3 : 4,14,30
1.5 : 6,8,16,34
------------------------------------ due Tue Sep 12
[2] 3.3 : 6,12,22
3.1 : 6
3.4 : 2,4,10
------------------------------------ due Tue Sep 19
[3] 3.5 : 40,62d,66
... : A1 (see below)
... : B1,B2,B3,B4 (see below)
------------------------------------ due Tue Sep 26
[4] ... : A2,A3,A4 (see below)
... : B5,B6,B7 (see below)
3.7 : 2
------------------------------------ due Tue Oct 3
[5] ... : B8 (see below)
4.1 : 4,24,28
4.2 : 2bde,6,18
------------------------------------ due Tue Oct 10
[6] 4.2 : 10,12
4.3 : 4a,4b,12,16
... : C1,C2 (see below)
------------------------------------ due Tue Oct 17
[7] 5.1 : 4,19,24
6.1 : 10,20,28
... : C3 (see below)
6.3 : 6,8,11
------------------------------------ due Tue Oct 31
[8] 6.2 : 2,8,10
7.1 : 2e,8,12,19,22,38,40
------------------------------------ due Tue Nov 7
[9] 7.2 : 1g,2e,6e,12,26
7.4 : 2g,17,18
------------------------------------ due Tue Nov 14
[10] 7.3 : 4c,29c
7.4 : 14
9.1 : 2,6,14,16,19
------------------------------------ due Tue Nov 28
[11] 6.1 : 46
9.3 : 2,6,8,14
9.4 : 1,2,3,4,18
------------------------------------ due Tue Dec 5
possible practice problems from Section 11
11.1 : 2,5,13a,14,20
11.2 : 1,2,7b
=================================================
NOTE: NO LATE HOMEWORK
Unless stated otherwise in class,
homework is collected in class on Tuesdays,
one week after it has been assigned.
Late homework will not be accepted.
But as announced, the lowest 3 homework scores
get dropped before computing the homework average.
=================================================
PROBLEMS A1 .. A4
A1. If possible, find an integral solution of
(a) 1617x+2541y=10
(b) 1617x+2541y=15
A2. Show that if m|a and m|b then m|gcd(a,b).
A3. Let a and b be positive integers with gcd(a,b)=1.
Show that if a positive integer n divides ab,
then n is the product of gcd(n,a) and gcd(n,b).
A4. Let a and b be positive integers with gcd(a,b)=1.
Show that any positive divisor n of ab
can be written in a unique way as a product n=st,
where s is a positive divisor of a
and t a positive divisor of b.
=================================================
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 write a~b iff 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] to be the set of all integers n satisfying 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) An ~ an for every positive n
Hint: Prove (3) by induction on n, using (2)
B5. Assume here that m=11.
Show that 73 ~ 2 and 25 ~ -1.
Use the rules from B4 (where needed) to justify the congruences
2949 ~ 749 ~ 7*(73)16 ~ 7*216 ~ 7*2*(25)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 2949 by 11 is 8.
B6. Following the ideas used in B5,
compute the remainder in the division of 9595 by 41.
B7. Assuming m is a prime,
show that if x2 ~ 1 then x ~ 1 or x ~ -1.
Does the same hold if m is any positive integer?
B8. 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 .. C3
C1. By playing with numbers, guess a theorem describing
the remainder in the division of 2n by 9.
Then try to prove the theorem.
C2. For which positive integers a and n does
the decimal representation of an end with a 7?
C3. Let m and n be positive integers with gcd(m,n)=1.
Let Y be the set of all ordered pairs (a,b)
with a in A={1,2,...,m} and b in B={1,2,...,n}.
Show that for every integer x in X={1,2,...,mn}
there exists a unique ordered pair (a,b) in Y
such that x≡a (mod m) and x≡b (mod n).
Show that this defines a one-to-one correspondence
between the sets X and Y.
Show that gcd(x,mn)=1 if and only if gcd(a,m)=gcd(b,n)=1.