713 Evans Hall

University of California at Berkeley

Berkeley, CA 94720-3840

Tel: 510-642-3768

Fax: 510-642-8204

Email: stankova@math.berkeley.edu

Office Hours TTh 9:30-10:50am in Evans 713.

Webpage: http://math.berkeley.edu/~stankova

Click below for the syllabus:

GSIs finalized office hours were revised in the syllabus on 9/6/2014. Check them out and keep them with at all times. You are welcome to visit any GSI's office hours, along with the professor's office hours.

Do NOT contact the
instructor or the GSIs. We have no control over enrollment.
Contact instead **Thomas Brown, 965 Evans.**

Email is NOT for resolving enrollment questions, or asking for letters, or for discussion of midterm results, or for any discussion about how the student is doing in the class or how to improve. I have received lately a number of such emails, to all of which the response is to come see me in person in office hours (bringing all necessary documentation with you). You are also welcome to visit any GSI's office hours to discuss math questions or how to improve in the course; the GSIs are very qualified to discuss any math question. This is clearly written in the syllabus and was discussed in detail during the first lecture.

Here is some Statistics from Midterm 1. For example, an exam with 79-81 points is in the top 25% of the class. Note that the median is 61/100 points, which indicates that the exam was hard. Undoubtedly, the hardest problem was the True/False question #1, on which there were only two perfect scores. Overall, there was one perfect exam 100/100 and a bunch of 96/100 and 95/100. The range was [8,100].

The GSIs will return the exams on Wed, Oct. 1, in sections. Exams not returned to the GSIs after the 10 minute viewing period will not be considered for regrading. When asking for a problem to be regraded, please, keep in mind that such requests rarely result in a change of the score. The GSIs will review your whole problem and your score may go up or down. Thus, ask for a regrade only if you have a solid reason and only after you read carefully the official solutions. The GSIs will turn down any requests that are not substantiated. The same grading rubrik is applied to all students equally in the class, and it will not be changed for any particular student. Students who miss section on Wed need to pick their exams at a conveninent time for the GSI or in office hours. Any requests for regrading after Monday, Oct. 6, will not be considered.

HW Solutions are posted about a day before the quiz and will be taken off the web in a week. Do NOT ask for solutions to be posted earlier: you must attempt to do your homework without help from posted solutions. If you are late copying them, or you lose them, or some other thing happens: do NOT ask us for the files of the previous solution since we do NOT distribute electronic files of the HW solutions. Instead, ask your classmates for the HW solution files. Make sure you download and save the solutions as soon as they are posted, to avoid having to ask your classmates later on for them.

If not specified odd or even exercises, it is assumed only even exercises, e.g., #2-8 means 2,4,6,8.

Read 4.4 (may skip Computer Arithmetic with Large Integers and Pseudoprimes). Write: #2,4,6(a)(c),8(try an example first),10,12(b),16* (do (a) with brute force if necessary),20,22,32,34,38(a),40,54,55.

Read 4.3. Write #4,10,12,13,16(b)(d),18(a)(b)*,20(a)(b),24(a)(b),26(a)(b),28,30,32(c),40(f). Extra challenge: #11*,36*-37*.

**Hints:****
**In #10: argue by contradiction and assume that there is an odd
divisor of m; this odd divisor is denoted by k in the hints; the
hint is asking you to show the given factorization and use it to
prove that 2^m + 1 will turn out to be composite in this
situation; try some small cases for m to get a feeling for what is
going on. In #11*: argue by contradiction, get rid of all
inconvenient functions to turn the statement only about integers,
and then use the prime factorization of these integers. In #12:
use the hint; if it is hard at first, try it in an example with a
small n, e.g., n=3, 4. In #13: the asterisk * may be “overrated”;
try out an example? In #18(b)*: write out ALL divisors of the
given number and add them up using the formula for the geometric
progression. In #20: memorizing all powers of 2 up to 2^{10} is
good.

Read 4.2 (up to p. 249, inclusive). Write #2,4,29,31,32.

**Hints:****
**In #31, show first that 10^n is congruent to 1 (mod 3) for any
natural number n; then use the decimal expansion of a positive
integer a and modular arithmetic mod 3 to show that a is congruent
to the sum of its digits (mod 3). Try exactly the same approach
for divisibility by 9. In #32: similarly, start by noting that 10
is congruent to -1 (mod 11), then show that 10^n is congruent to 1
(mod 11) when n is even, and to -1 when n is odd; finish by using
the decimal expansion of your number a and replacing all powers of
10^n by +1 or -1, respectively. Try all these divisibility
criteria on 3- or 4-digit numbers to see how they work out in
practice.

Read 2.4. Write #6(a)(b)(d)(e), #8,10(d), #12(d), #14(c)(f)(g), #16(c)(g), #22, #26(e)(f), #32(a)(d), #34(b)(c), #40.

Read 4.1. Write #6, #8, #10(d)(e), #12(c), #14(d), #18, #28(a)(d), #32(c), #36, #38, #40.

Read 2.3. Write #2,6(a)(b)(d),12,14(a)(b)(e),20,22(b)(c),26,30(d),40,50,54,64,74(b). Extra challenge: 76.

Read 2.5. Write #2,4,6,8,10,16,18,20(use bijections),24.

Read 2.1. Write #10,12,16,18,20,22,24,26,32(b)(d),38.

Read 2.2. Write #2,4,12,14,16(d),18(c),24,26(b),30,44.

Read 1.8. Write #4,6,10,14,18,22,30,32,34,36,42,44.

This HW will be tough for those who are not experienced with problem solving and proofs, which is natural at this level. Hence some hints are listed here. Do your best.

**Hints: **#4 (arrange
a,b,c in increasing order in your cases); #6 (x being odd and y
being even is symmetric to another case); #8 (definitely try some
small cases first before you find your example); #10 (Could they
BOTH be perfect squares? Could (n+1)^2 - n^2=1? Why is this
relevant in the problem?) #18 (place r on the real line between
two consecutive integers, exactly one of which will be the
required unique n in the problem; why?; what could go wrong if we
allowed for r to be rational?) #22 (Do it as the hint suggests.
And then apply the inequality from Example 14 to x^2 and 1/x^2
(instead of x and y) for a direct proof.) #30 (If they were such
integers, how large can possibly be |y|?) #32 (The hint is giving
you specific formulas for the integers x, y, and x. Substitute
these formulas into the Pythagorean equation to show that they
satisfy the equation. Do these formulas give infinitely many
triplets of solutions? Why?) #34 (Adapt the proof that square root
of 2 is irrational.) #36 (What kind of a number lies exactly in
the middle between a rational and an irrational number? Use the
average to get a formula for this middle number and show why it
must be irrational by contradiction.) #42 (Direct tiling should do
it. Try it.) #44 (What happens if you color the 5 x 5 board as a
regular chessboard? Try finding an invariant.)

Read 1.6. Write #2,4,8,12,16,18,24,28. Challenge: #35*.

Read 1.7. Write #6,8*,10,12,18,20,24,26,30,34.

Read 1.3. Write #6,8,10(b)(c),14,24,30,32,60,62(a).

Read 1.4. Write #6,10,16,20,32,50,60.

Read 1.5. Write #6,14,20,24,30,40,46.

**Note 1: **The first
quiz is on Wed, Sept. 3 and will be on the material from HW1. For
the quizzes, you are allowed to have a cheat sheet containing
material related to course. The cheat sheet can be only 1 page
(one-sided!) of a regular 8”x11” sheet. It has to be
hand-written by you (no zeroxing, copying, pasting, etc.)!

Read 1.1. Write #2,4,8,12,14,18,28,30,34,38. Extra Challenge: #40, 49.

Read 1.2. Write #2,12,16,24,28,40,42. Extra Challenge: #36, 38.

**Note 1: **The
implication "p --> q" can be read in a number of
ways. One of the most confusing ways to read it is "p only if
q", which means "if p is true then q must be true",
i.e., "if p then q". I would suggest avoiding, whenever
possible, the expression "only if" as it is doubly
dangerous. Indeed, in everyday life it is used to mean "if
and only if", while in math it is used only in one direction
and it is often counterintuitive. For example, Problem #3 from 1.1
can be translated mathematically as: "If p then [q1 AND (not
q2) AND (not q3)].", where p: "You graduate.", q1:
"You fulfilled all requirements for your major.", q2:
"You owe money to the university.", q3: "You owe a
library book."

**Note 2: **The first
quiz is on Wed, Sept. 3.