Frustration with Example

Homework in college can get pretty frustrating. Unlike high school, we typically only have homework once per week, but it also typically counts for a lot more of your grade, like 10% or 20%. Also, it's graded a lot more harshly, and it's typically more difficult. Instead of just spending maybe 30 minutes reviewing what you did in class, it's often the main instrument of learning the material (yes, you teach yourself, and it's just through the homework, fun!). Kids usually spend a lot of time on each assignment, and usually there are only about four or five questions, but that can still take many hours. If there are more questions, the grader (who is typically not the teacher) selects a few and grades those and nothing else. For instance, in Math 220H (linear algebra, honors) we would have about 30 problems/week, but only six would be graded. So if you got 29/30 correct and one of those was graded, you got an 83%. Hooray!

Anyhow, I was doing my Math 465 (Number Theory) homework today because it's due tomorrow. One of the problems caused me a great deal of frustration, largely because I spent a lot of time on it, and I learned nothing from it. I wouldn't have minded if I had learned. Let me explain the problem. It'll be fun, I promise, and you'll get to see what super cool math majors do!

So we're working with Greatest Common Divisors (GCDs), which is probably a familiar example. Pick two numbers A and B, and the GCD is the biggest number that divides both of them. If A = 12 and B = 8, the GCD is 4, because no bigger number divides both 8 and 12.

There's a fun fact about this though. If you were to just look at the equation 12*X + 8*Y = E, and pick any X and Y that you wanted as long as they were both whole numbers, you could never make E any smaller than 4. So, the smallest number that you can make E using that set-up is the GCD of those two numbers.

The problem was this: If A*D - B*C = 1, show that the GCD of (A+B) and (C+D) is 1.

So I started on that problem, and thought about it for days, just to let it sit and simmer and see what came up. Basically, nothing did. So tonight when I worked on it, I just tried everything I could. I noticed that it's a linear combination if you write it correctly: A*D + (-C)*B = 1, and thus the GCD of A and B is 1. Hooray? I tried to go further from there but it didn't help me.

Then I ran out of options and looked in one of my old math books to see if there was any help there. There was nothing pertaining to this particular problem, but it DID spark an idea somehow. I figured I'd look at a linear combination of the second part and see if that helped: (A+B)*K + (D-C)*N = M. What I thought I could do is as follows. Assume that M is greater than 1. Thus, the GCD of A+B and D-C is greater than one, and M divides both of them since it's a divisor of both. Since it devides A+B, it divides A and B, and since M>1, the GCD of A and B isn't one - contradiction! But the last step doesn't make any sense, so I gave up on that.

I thought about doing prime decomposition, and I thought I had it there for a while. Then I tried expanding my linear combination, but still nothing.

It ended up that the answer was a trick you learn in high school called "Adding zero." Basically, it goes like this: If you add and subtract the same quantity from the same side of the equation, everything is still the same. Thus, you can say X = Y or you can say X + A - A = Y, because the +A and -A equal zero together. What you had to do was this:

A*D - B*C = 1

A*D - B*C + A*C - A*C = 1

A*D +A*C - B*C - A*C = 1

A(D+C) - C(B+A) = 1

A(C+D) + (-C)(A+B) = 1

Since you have a linear combination of C+D and A+B, their GCD is one.

Okay, fine. It's true, I get it, the GCD is one. The thing is, I didn't learn anything from it - the answer to the problem was a stupid trick you laern in high school that doesn't teach you anything about the methods or insights of number theory. Perhaps there is a tiny bit of somethign to be learned - sometimes you add zero! - but the goal would have been much better served if the instructor had added to the question (Hint: Add and subtract a certain quantity) so that you didn't spend two hours on it.

Anyway, it's late.

Goodnight.