Information provided by the grader:
Homework 1.
1.3.5: There were some issues with over-brevity and non-specificity as
far as having a fixed, but arbitrary integer or even specifying what
sort of number k (in some cases, n) was supposed to be or what range it
was supposed to be in, but overall this problem was good. The only other
major thing that got counted off for was if you said things that didn't
form a complete thought and I could not figure out if you really
understood the logic or not. If anyone got more than -2 on this one, it
means their problem was probably incomprehensible or had very little or
no solid work.
1.3.30: Again, the most common problem was that students forgot to
specify their context: things like "for some integer k (or n) >5," when
it was relevant were missing at times, especially when making the
inductive assumption, most said something synonymous with "assume P(n)
is true" without comment on the argument. I also got some "assume n=k"
but no mention of the hypothesis or its holding for n=k. I also too off
a little if there was very little or no justification for steps. It
didn't have to be much, but just asserting things without any reference
to why it should be believed at all was insufficient. The best proofs
(i.e. highest scores) had a short, but present justification for each
step and clearly communication of their ideas. For instance: some wanted
to use that 2^k > 2k+1 (when k>4) which is true, but requires proof;
some claimed it without reference to k as if it were true for every k
(it isn't). The last (common) mistake I saw was circular reasoning,
writing things like "2^{n+1}>(n+1)^2" at the beginning or middle of the
proof.
1.5.8: The most common errors on this were that people listed negative
factors, gave the gcd without giving a list of factors, or listed only
common factors instead of all factors of each.
1.5.15: This problem was very good for the most part. People were
careful to use the definition and say they were using it. Since the
result was a shorter proof, I was looking for some words of
justification for steps mostly. The most common problem was students
just writing bd=(ac)(jk) => ac|bd and a bunch of other symbols without
citing the definition or some other analogous words.
A1: Reflexivity got a lot of people on this problem. All that needed
to be said after showing the statement was equivalent to mk=0 for some
integer k, and then observe k=0 worked, but most didn't say "this holds
for k=0" or made more difficult claims that required proof but didn't
prove them. The other major error that was common on all parts of the
problem was trying to prove things backwards by assuming the conclusion
held at the start. The last problem I saw not-infrequently was saying
something like "there exists an m," when m is already fixed.
Also: some of them had proofs related to real numbers and not
integers, and it was really confusing as they were not on the homework
page.
With all of them, I may have minor scratch-outs or corrections, but if
they lost points it was not due to the minor things, those are just
there as helpful things for the students so they know how to format or
write things in the future. A general comment to all the students on how
to get good scores on the homework is to make sure it's clear what
you're doing. A list of numbers, some arrows and a boxed answer is not
what you're going for in this class, even on computation problems. Make
it clear what all of your objects are.
Homework 2.
1.5.12: The most common errors were incomplete tables and missing the
pair (5,8). The best answers divided their pairs into rows based on the
first number, so all the (1,X) were in one row, then (2,X) in the next,
and so on.
3.3.16a: The biggest and most fatal error was to try and use the FTA
or some slight weakening such as Euclid's lemma (which are all in
section 3.5, so is not yet available). The typical minor problems were
writing lots of symbols without indicating what they were or writing an
actual conclusion (eg. stopping at ax+(bc)y=1 without saying that by
Theorem 3.9 this means gcd(a,bc)|1 ergo it equals one because only 1|1
in the case they did a computation). Due to the sheer variety and length
of some of the proofs I offer this simplified version for their
convenience (and for those that had ones which were totally off the
mark):
By Corollary 3.8.1, there are integers, x,y, such that ax+cy=1, so
a(bx)+(bc)y=b and again by Theorem 3.9 gcd(a,bc)|b and gcd(a,bc)|a by
definition, so gcd(a,bc)|gcd(a,b)=1 by definition of the gcd.
3.3.24+: Again the most fatal problem was jumping ahead and using the
Euclidean algorithm. The other big one was writing a gcd(a,b)=gcd(a-b,b)
style argument without justifying it (just write "by Theorem 3.7").
Another sample "ideal" solution:
5(3k+2)-3(5k+3)=1, so gcd(5k+3,3k+2)|1 by Theorem 3.9, hence is equal
to 1.
For those looking to use something adapted like the EA, you could also
use Theorem 3.7 to make that style of argument work.
3.4.2ad: mostly uneventful
3.4.4ad: mostly uneventful
Overall notes: If you missed 3.3.16a and 3.3.24+ by jumping ahead it
was a big chunk of your grade on this one, so a lower score might not
reflect a bad understanding of the material, just that you jumped ahead
and used unavailable techniques: just be careful in the future.
Homework 3.
A2 Most got the first and second bits right, for the third bit there
was some trouble with induction for those that did it that way, but
overall this problem went well. There were some other individualized
problems, but nothing systemic.
3.5.34 The most-missed thing was that the question requests integer
pairs, not just natural number pairs, so the +/- was often omitted. The
most common mistakes after that were omitting possibilities from the
list of pairs or not actually doing the computation (some described
things, some just stopped doing the problem in the middle, et cetera).
3.7.2 The most common error was not finding all solutions to the parts
of the problem that had solutions to the equations.
4.1.5 was very good overall
B1 This one got a lot of people. The most common, true "error" was not
completing the problem through to the end, though there were some odd
arithmetic errors as well. The only other common mistake I saw was
people who reduced the exponent modulo 41 instead of reducing the base
modulo 41, so they usually had something like (95)^(95)=(95)^(55)
instead of = (54)^(95). Similarly for 13 instead of 55.
Homework 4.
4.2.2 This went well overall. The only common error were missing one
or more equivalence classes on those with multiple solutions. There are
also still some people who are just writing "k" without saying that k is
an integer, or k is an integer in some range. I would recommend, as a
matter of course, that the students choose more recognizable
representatives, eg. 20 or -5 instead of -55 in the case of part (d),
but I didn't count off for it.
4.2.12 This one also went well. Usually there was only a point off,
and that for failing to note that a a-bar b b-bar = (ab)(a-bar b-bar)
explicitly.
4.3.4a I was looking for either a theory reason why an answer was
unique or a computation which made it clear that the answer they gave
was the only one (mod 187).
4.3.12 This one went similarly well, though those who wrote just
strings of equations and made minor mistakes got it wrong in strange
ways some times. Also, many neglected the context and just put a
congruence with 119 rather than state the answer was literally the
integer 119, as the smallest positive answer as the question asks. The
only other major problem was assuming they could omit the congruence
modulo 4. It still produces the right answer in this case, but not all
numbers 1 mod 2 are also 3 mod 4, so the method is still wrong. It's
easy to provide systems where this logic will produce the wrong answer,
even as simple as
x = 1 mod 2
x = 2 mod 3
x = 1 mod 4 <--(note the difference)
x = 4 mod 5
x = 5 mod 6
x = 0 mod 7
If you use the same logic, on this system (which is EXACTLY the same
except for the mod 4 congruence) you get the wrong answer, since 119 is
NOT 1 mod 4, so you get it right by a 50/50 chance of an odd number
being either 1 or 3 mod 4, but not by real math.
4.3.16a A lot of people thought they should solve things modulo 90
instead of 30 and ended up with a wrong answer from that. Some thought
that just because the CRT didn't apply immediately they could not solve
the system.
As a general comment, I think the overall quality of homework submitted
is going up on average. Work is easier to follow, explanations are more
thorough, et cetera. I would also recommend to students to try and use
the modular language to phrase their answers rather than a+bk sort of
answers. It makes it so they don't have to remember to say "k is an
integer [between x and y]" sort of statements, and it's more concise.
Those who are still just writing strings of equations don't always get
things off, but it seems their scores are lower on average, since things
show up in some problems where it's easy to forget how to get the right
answer from the computations.
Homework 5.
B2) Only one person got part (a) completely right, this was definitely
the problem they had the most difficultly with. A sample solution is
below to parts (a) and (b).
(a) Let 0 < x < mn+1 be an integer. Then let a be the remainder of x
when divided by m and b be the remainder of x when divided by n. If a=0,
use m instead and if b=0 use n instead. Then (a,b) is an ordered pair
which satisfies the conditions of the problem by definition. By the
Chinese Remainder Theorem, the congruence system y= a mod m, y = b mod n
has a unique solution mod mn, so has only one representative from any
complete residue system. Since X is a system of mn distince residue
classes, it is a complete residue system by a lemma from the book, since
x is a representative, it is the unique one given use by the CRT.
(b) Let a(x), b(x) be the representative modulo m and n respectively
for an integer 0 < x < mn+1. Then by part (a), the function x |--> (
a(x), b(x) ) has only one pair of integers a, b such that 0<a<m+1,
0<b<n+1, so that this is actually a function, and the uniqueness implies
the function is 1-1. But then since the set X and the set A x B have the
same size, this implies the function is also onto, hence this function
is a 1-1 correspondence.
Alternative proof of onto for (b): Same up through proving 1-1. To see
onto, we can note that the CRT always allows us to find x mod mn such
that x = a mod m and x = b mod n, hence every complete residue system
has some element x such that x mod m = a and x mod n = b, so that our
function is onto.
B3) It was not terribly common, but it was the *most common* mistake of
the mistakes made: some students did not read the question and so just
said whether or not something was divisible by the given moduli rather
than returning any of the remainders.
6.1.3) Students did very well on average, the only major problem was
those who just wrote strings of equations with no justification. A "by
Wilson's theorem" clause would have saved most of those who got anything
off on this problem.
6.1.10) The most common errors were computational and came exclusively
from people who did it the hard way: everyone who used Fermat got the
right result modulo typos.
6.3.19) This problem was very good overall; there were some very minor
computation errors, but nothing serious.
Homework 6.
(6.1.20) Many students were able to prove divisibility by 8, 3, and 7,
but neglected to justify why this implied divisibility by 168 or omitted
that statement altogether. The reason is, of course, the Fundamental
theorem of arithmetic or the CRT if they do it via congruences, or some
weakening, i.e. if gcd(a,b)=1 and a|c and b|c then ab|c. Also, a great
deal of them just glossed over essential justification. A good deal of
people showed that a^6 was 1 odd (i.e. =1 mod 2) but failed to bootstrap
to mod 8. I would remind them that they proved in previous HW that all
odd numbers, n=2k+1, satisfy n^2 = 1 mod 8.
(6.1.28) The only consistent problems were not citing the CRT or FTA,
there were other problems, but they were ad hoc rather than systemic.
(6.3.6+) This one went very well. The only recommendation I have in
general is to be careful to note that gcd(7,10)=1, since the theorems
require this. I was lenient for those who quoted Euler even if they
didn't overtly state gcd(7,10)=1 since that is one of the theorem's
hypotheses. Those who just wrote a computation got a deduction.
(6.2.8) Students frequently neglected to justify the fact that
(2^d-1)|(2^n-1) when d|n (a non-trivial and non-obvious lemma in the
book.) Some opted to just include a proof of this alongside the main
result, and this was also fine. I got a *lot* of strange notation that
went totally unexplained in this problem rendering a few responses
totally unreadable as a string of symbols and operators with no readable
explanation.
(C1) The most common problem here was not finishing. They sort of
stated some facts and usually didn't connect them. Others just wrote
summations willy nilly and didn't indicate what they were summing over
or reused variables which weren't free and got totally wrong answers.
The best advice I can give here is to *slow down* and write more
carefully, the majority of points lost were due to careless/cavalier
things, and since they were crucial mistakes they cost *a lot*.
Homework 7.
(6.1.48) A lot tried breaking it into cases for some reason, though
none of them who got it right ever used the (unnecessary) hypothesis
that n was odd for that case. Most did not see the easiest way was to
use Fermat, and flopped as a result. A sample solution is below.
Let p be the *smallest* prime factor of n, one exists since n>1 by the
FTA. Then we must have that 2^n = 1 mod p, so that there is a factor of
n which divides p-1. Either that factor is 1 or it isn't. If it is, we
conclude 2^1 = 1 mod p which is nuts, if not then since p-1 < p we have
a contradiction to the minimality of p.
(7.1.2e) Many students tried to use fractions to find the result here,
which is totally outside the bounds of the integers. They should try and
use phi(p^k)=(p^k-p^{k-1}), it's much easier and would have gotten them
full credit.
(7.1.22) Some tried to test the case m=1, but didn't do induction (and
one doesn't need to do induction) so it made some of them harder to
understand. Again, using fractions came up and if they had just used the
integer version most would have gotten full credit. Many also thought
they could just prove it for primes or products of primes, which is
untrue (though for prime powers it is enough).
(7.2.1g) This went mostly well modulo computation errors and isolated
theoretical errors.
(7.2.6e) The biggest issue here was claiming that 2^6*3 was the
smallest possibility just because 2<3, but it's not immediate that this
is smaller than 2*3^6 just because 2^6<3^6, it should be checked either
by computing the actual value, noting that 3^5=243 is already too big as
a shortcut, or writing 2*3^6-2^6*3= 2*3*(3^5-2^5)>0. (Really any valid
justification would have been accepted.) I was lenient if they also
didn't notice that some p^{13} would also work because enough missed the
first one that it seemed a lot to take 2 points away for just those two,
but those who got the first bit I did check for the p^{13} case.
Homework 8.
(8.4.8) A lot of them omitted a lot of work, like finding the inverse
of 5 mod 2772 using the Euclidean algorithm. I can understand not
wanting to compute tons of stuff by hand, but it was one exercise, and
I'm looking to see they had some hand in solving it rather than a
computer somewhere.
(9.1.2) This one went mostly well. The only common incorrect answer I
saw was some of the orders computed to be 1, which I found a bit
bizarre, as something is only order 1 mod n if it is already *equal* to
1 mod n, which none of them were.
(9.1.8) This was very straightforward, nothing to report.
(9.1.10) This one was also uneventful, most of the computations went
well, modulo minor errors. The biggest issue was students not showing
any work or citing any theorems. When they leave them as just lists,
it's not clear they actually *did* the problem or understand anything,
only that they got the answer from *somewhere*, whether it was their
work or otherwise is impossible to tell. This is a line-item comment,
though, *most* students showed plenty of work, cited the right
theorems/results, and did well.
(9.1.16) Many of the students fell into the classic blunder (not the
Asian land war or going in against a Sicilian when death is on the line,
but the third classic blunder) of using since phi(p)=p-1 then all
numbers m so that phi(m)=m-1 are primes. Also, many said without
justification that phi(m) < m-1 when m is not prime, which is the right
idea, but needs the words "by definition of phi(m) and 'prime'," or a
citation of theorem 7.2.