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 k3-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 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]={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) 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. 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).
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.
(AxB 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=Zx(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 write a≡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 {ai,xi}
(distinct numbers) such that aixi≡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 ap-1≡1 (mod p).
D3. Use Fermat's Little Theorem to
compute the remainder in the division of 10500 by 17.
===================================================
SOME DEFINITIONS
Let G be a set (subset of some universal set U).
A function • from GxG to U is called a binary operation on 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 the closure property iff
for all A and B in G, A•B belongs to G.
We say that (G,•) has the associativity property iff
for all A,B,C in G, (A•B)•C=A•(B•C).
We say that (G,•) has the identity property 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,
an inverse of 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 the inverse property iff
every element in G has an inverse.
We say that (G,•) is a group iff
it has the closure, associativity, identity, and inverse properties.
We say that (G,•) is commutative iff
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) distributive property 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,+,*) a field iff (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,+).