Homework assignments for M328K
====================================
Nr Section : Problems
------------------------------------
[1] 1.3 : 4,14,30
1.5 : 6,8,16,34
... : A1 (see below)
------------------------------------ due Tue Sep 8
[2] 3.3 : 6,12,22
3.4 : 2,4,10
... : A2,B1 (see below)
------------------------------------ due Tue Sep 15
[3] 3.5 : 40,62d,66
3.7 : 2
4.1 : 4,24,28
------------------------------------ due Tue Sep 22
[4] 4.2 : 2bde,6,10,12,18
... : A6,A7,B2 (see below)
------------------------------------ due Tue Sep 29
[5] 4.3 : 4a,4b,12,16
5.1 : 4,19,24
... : B3 (see below)
------------------------------------ due Tue Oct 13
[6] 6.1 : 10,20,28
6.3 : 6,8,11
... : B4 (see below)
------------------------------------ due Tue Oct 20
[7] 6.2 : 2,8,10
7.1 : 2e,8,12,19,22,38,40
... : C2 (see below)
------------------------------------ due Tue Nov 3
[7] 7.2 : 1g,2e,6e,12,26
7.3 : 4c,29c
7.4 : 14
------------------------------------ due Tue Nov 17
[8] 6.1 : 46
9.1 : 2,6,14,16,19
... : A3 (see below)
------------------------------------ due Tue Nov 24
[9] 9.3 : 8
9.4 : 1,2,3
------------------------------------ due Tue Dec 1
possible practice problems afterwards:
9.3 : 10
9.4 : 4,18
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, only the 10 highest HW scores
are used to compute the homework average.
=================================================
PROBLEMS A1 .. A3
(all numbers here are integers)
(Z stands for the set of all integers)
In this problem set,
m is some fixed but arbitrary (unspecified) positive integer.
Definition: We write a~b iff m divides b-a.
(In words: a is congruent to b modulo m.)
A1. 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)
A2. Show that a~b if and only if
a and b leave the same remainder in the division by m.
A3. 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
A4. 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)
A5. 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.
A6. Following the ideas used in A5,
compute the remainder in the division of 9595 by 41.
A7. 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?
A8. 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 ax1 ~ b and ax2 ~ b then x1 ~ x2.
Notice: This also proves that
if ax1 ~ ax2 then x1 ~ x2 (cancellation law).
A9. Consider the sets defined in A3, 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 A4, 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 B1 .. B4
B1. Show that if n|a and n|b then n|gcd(a,b).
B2. Show that if a|n and b|n then lcm(a,b)|n.
B3. 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).
B4. 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 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.