# Spring 2005

Homework, Schedule, Assignments

“P” means “Pathway”; “J” means Jones&Jones. “P2.34” means problem 34 in chapter 2 of Pathway; “J7.13” means exercise 7.13 in Jones&Jones. It is crucial that you attempt the problems in Pathway before looking at the “notes and answers” section.

Due Date

Have done before class

Presentations

02/01/05, Tu

02/03/05, Th

P1.1-1.42 (not 1.22). For 1.29, 1.31 and 1.36, interpret the first question as “Is the set ... closed under addition?” In 1.30 and 1.32, the “subgroup generated by a and b” means the set {ax + by| x,y in Z}

KK: P1.18

JB: 1.19

LB: 1.31

BD: 1.36

JH: P1.40

JSm: P1.41

02/08/05, Tu

P1.43-1.61

CH: P1.46

AMe: P1.50

KG: P1.51 (find different example than book's)

MN: P1.53

JSo: P1.54

02/10/05, Th

P1.62-2.6

TW: P1.63

NA: P1.65 (first half)

HN: P1.66

LD: P1.67

NP: P2.2

JC: P2.5

02/15/05, Tu

P2.7-2.18

CM: P2.7

BR: P2.9

AMy: P2.11

SR: P2.16

SH: P2.12

ND: P2.13

02/17/05,Th

P2.19-2.34

For 2.23-2.25: Ignore the “Is it a group table?” question. “element which generates the group” means an element whose multiples give you everything in the set (like 5 does in P2.23 (5, 4, 3, 2, 1, 0), but 3 doesn't (3, 0, 3, 0,...))

JSa: P2.21

KK: P2.26

JB: P2.28

LB: P2.29

BD: P2.32

02/22/05, Tu

P2.35-2.43

JSm: P2.34

CH: P2.36

AMe: P2.37

MN: P2.40

JSo: P2.42

02/24/05, Th

P2.44-P2.56

HW1 (30 points): (had to change when I discovered that J has all solutions in the back)

1. P1.52

2. Use the Division Algorithm to establish that the cube of any integer has one of the forms 9k, 9k + 1, or 9k + 8.

3. Prove that no integer in the following sequence is a perfect square:

11, 111, 1111, 11111,...

4. A band of 17 pirates stole a sack of gold coins. When they tried to divide the fortune into equal portions, 5 coins remained. In the ensuing brawl over who should get the extra coins, one pirate was killed. The wealth was redistributed, but this time an equal division left 14 coins. Again an argument developed in which another pirate was killed. But now the total fortune was evenly distributed among the survivors. What was the least number of coins that could have been stolen?

5. Given integers a and b, prove: If there exist integers x and y for which ax + by = gcd(a,b), then gcd(x,y) = 1.

6. Prove that if d is a common divisor of a and b, then d = gcd(a,b) if and only if gcd(a/d,b/d) = 1.

When writing up a problem from P, your writeup should be substantially more complete than the answer in the book. You need to cite earlier problems when you use them, for example, and explain your reasoning.

TW: P2.46

NA: P2.48

HN: P2.49

LD: P2.51

NP: P2.54

03/01/05, Tu

P2.57-P2.64

NP: P2.54

JC: P2.60

CM: P2.57

BR: P2.58

SR: P2.61

03/03/05, Th

P3.1-P3.14

JSa: P3.2

KK: P3.3

JB: P3.5

LB: P3.10

ND: P3.11

SH: P3.13

03/08/05, Tu

P3.15-P3.33 (3.17 and 3.18 only if you've had Modern Algebra)

BD: P3.15

JSm: P3.16

CH: P3.19

AMe: P3.24

MN: P3.32

03/10/05, Th

P3.34-P3.42 (rephrasing below)

P3.39: In each of the tables in q 38, does each element have a multiplicative inverse?

P3.40: Prove that Mn is closed under multiplication and that each element of Mn has a multiplicative inverse.

P3.41: You may use the fact that each row and each column in a group multiplication table contains each element of the group exactly once.

P3.42: Use 36 and 41 to prove that if gcd(a,n) = 1, then ...

CH: P3.19

JSo: P3.36

TW: P3.37

NA: P3.38,.39

LD: P3.40

HN: P3.41

03/15/05, Tu

P3.43-P3.48

NP: 3.43

JC: 3.44

CM: 3.45

BR: 3.46

SR: 3.47

03/17/05, Th

P3.49-P3.57

HW2 (30 points)

1. Find at least five different numbers with Φ(n) = 160. How many more can you find?

2. Find all values of n that solve each of the following equations: (a) Φ(n) = n/2; (b) Φ(n) = n/3; (c) Φ(n) = n/6

3. Solve x86 ≡ 6 (mod 29); x39 ≡ 3 (mod 13); and x ≡ 9794 (mod 73).

4. (a) The congruence 71734250 ≡ 1660565 (mod 1734251) is true. Can you make any conclusions about the primality (or not) of 1734251?

(b) 12964026 ≡ 15179 (mod 64027). Can you make any conclusions about 64027?

(c) 252632 ≡ 1 (mod 52633). Can you make any conclusions about 52633?

5. If you know the value of (n-1)! (mod n), how can you use that information to determine whether n is prime?

6. Find the number of zeros at the end of 100!. Describe how you would figure out the answer to this question for n!, for any integer n.

CM: P3.45

JSa: P3.51

KK: P3.52

AMy: P3.54

JB: P3.55

LB: P3.56

ND: P3.57

03/22/05, Tu

P3.58-P3.62; P3.88-P3.95

SH: P3.61

BD: P3.62

03/24/05, Th

Midterm Exam (50 points)

Sample Midterm:

1. Prove that if a and b are integers with b>0, then there exist unique integers q and r satisfying a = qb + r, with 4br < 5b

2. Prove that for any integer a, 6|a(a + 1)(a + 2).

3. Prove that for any positive integer n and any positive integer a, gcd(a,a + n) divides n. Use this fact to find gcd(a,a + 1).

4. (a) Find all the solutions (mod 15) to the congruence x2 ≡ 1 (mod 15).

(b) There are four solutions (mod 33) to x2 ≡ -2 (mod 33). Does this contradict Lagrange's Theorem? Why or why not?

5. What is the remainder when 62002 is divided by 11?

6. Show that if p is an odd prime, then 2(p – 3)! ≡ –1 (mod p)

7. Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.

03/29/05, Tu, Spring Break

03/31/05, Th, Spring Break & Cesar Chavez Holiday

04/05/05, Tu

P3.88-P3.95, P4.1-P4.10

For P4.3, 4.4, interpret “does it form a subgroup?” as “is it closed under multiplication?”

JSm: P3.89

CH: P3.90

AMe: P3.91

MN: P4.4

04/07/05, Th

Jsection5.3, including all its exercises (J5.14-J5.19) (Euler's Theorem is P3.41)

P4.11-P4.15

JSo: J5.15, J5.16

NA: J5.19

LD: P4.11

NP: P4.14

HN: P4.15

04/12/05, Tu

P4.16-P4.32 (skip P4.20)

NP: P4.17

JC: P4.19

SR: P4.21

JSa: P4.29

KK: P4.30

04/14/05, Th

P4.33-P4.43 (Gauss's Lemma)

AMy: P4.34

JB: P4.36

LB: P4.37

ND: P4.41

SH: P4.42

BD: P4.43

04/19/05, Tu

P4.44-P4.62

JSm: P4.46

CH: P4.50

AMe: P4.51

MN: P4.58

JSo: P4.60

04/21/05, Th

P6.1-P6.15 (not “optional supplement” in 6.15. Notice that table 5.1 is a table of sums of two squares – first square down the left column; second square giving the column. For P6.9, use this version of Lagrange's Theorem on subgroups: The order of an element divides the order of the group – in this case, Mp.)

NA: P6.6

LD: P6.8

NP: P6.9

HN: P6.10

JC: P6.13

SR: P6.14

04/26/05, Tu

P6.16-P6.28

HW3 (40 points)

1. If a = b2 is a perfect square and p is an odd prime, explain why it is impossible for a to be a primitive root modulo p.

2. A number a is called a cubic residue modulo p if it is congruent to a cube modulo p. Let b be an element of order p-1 in Mp

a) Make a list of all the cubic residues modulo 5, modulo 7, modulo 11, and modulo 13.

b) Find two numbers a1 and b1 such that neither a1 nor b1 is a cubic residue modulo 19, but a1b1 is a cubic residue modulo 19. Similarly, find two numbers a2 and b2 such that none of the three numbers a2, b2, or a2b2 is a cubic residue modulo 19.

c) If p ≡ 2 (mod 3), make a conjecture as to which a's are cubic residues. Prove that your conjecture is correct.

d) If p ≡ 1 (mod 3), show that a is a cubic residue modulo p exactly when 3 divides the smallest integer x that satisfies bx ≡ a (mod p).

[Hint added 4/19 for #2c and d: Make use of that primitive root b in Mp]

3. Given that a is a quadratic residue for the odd prime p, prove:

a) The integer p – a is a quadratic residue of p if p ≡ 1 (mod 4), and a quadratic nonresidue if p ≡ 3 (mod 4)

b) If p ≡ 3 (mod 4), then x ≡ a(p+1)/4 (mod p) and x ≡ –a(p+1)/4 (mod p) are the solutions of the congruence x2a (mod p).

4. Use Gauss's Lemma and the Theorem proved in P4.14,P4.15 (see P p. 88) to prove that

a) If p is congruent to 1 modulo 5, then 5 is a quadratic residue modulo p.

b) If p is congruent to 2 modulo 5, then 5 is a quadratic nonresidue modulo p.

5. Using the primes p = 12553 and q = 13007, construct an RSA scheme and encode your entire name (at least 10 letters; add some extra letters if necessary). Attach any computer work that you did to accomplish this, or describe what you put into your calculator.

JSa: P6.19

KK: P6.22

AMy: P6.23

JB: P6.25

LB: P6.27

ND: P6.28

04/28/05, Th

SH: P6.30

BD: P6.32

JSm: P6.33

CH: P6.34

AMe: P5.6

05/03/05, Tu

P5.10-P5.18, Jsections 2.3, 2.4

MN: P5.10

JSo: P5.15

NA: P5.16,5.18

LD: J2.5

NP: J2.9

HN: J2.21

05/05/05, Th

Jsections 8.1,8.2

JC: J8.1

SR: J8.3

JSa: J8.4

KK: J8.8

AMy: J8.6,8.7

JB: J8.21

05/10/05, Tu

Jsections 8.3, 9.1, 9.2

LB: J8.9

ND: J8.11

SH: J9.1

BD: J9.2

05/12/05, Th

P5.19-P5.23, Jsections 9.3, 11.1, 11.6, 11.7

JSm: P5.20

CH: P5.22

AMe: J9.3

05/17/05, Tu

Jsections 11.8, 11.9, 11.10, including the exercises

HW 4 (40 points)

1. You may notice when looking at Pythagorean triples (a,b,c) that for many of them, c is two greater than b (when they are listed as in P: a is even). For example, the triples (4,3,5), (8, 15, 17), and (12, 35, 37) all have this property.

a) Find two more primitive Pythagorean triples having this property.

b) Find a primitive Pythagorean triple (a,b,c) with b + 2 = c > 1000.

c) Find a formula describing all primitive Pythagorean triples satisfying c = b + 2.

2. Using the procedure of P Chapter 6 to write the prime 12049 as a sum of two squares, starting from the equation 5572 + 552 = 26 · 12049.

3. a) Show that a power of 3 can never be a perfect number.

b) More generally, if p is an odd prime, show that a power pk can never be a perfect number.

c) Show that a number of the form 3i5j can never be a perfect number.

d) More generally, if p and q are distinct odd primes, show that the product piqj can never be a perfect number.

4. A number that is equal to the product of its proper divisors, instead of the sum, could be called product perfect. For example, 6 and 15 are product perfect, while the product of 9's proper factors is too small and the product of 12's proper factors is too large.

a) List all the product perfect numbers between 2 and 50.

b) Describe all product perfect numbers in a way that enables you to quickly answer questions of the form “is n product perfect?” and “Find a product perfect number larger than 10,000.”

c) Prove that your description in (b) is correct.

End of HW 4

05/19/05, Th

Review!!

05/24/05, Tu

Final Exam (60 points) 11:00-12:50, Stevenson 3076

Review!

Participation (50 points)