MA357, Spring 2008
Comments on Problem Set 1

These aren't really full solutions, just comments that hint at the solutions, sometimes with lots of detail, sometimes not. If these don't suffice for you to see the full solution, please come see me!

1. If ab = 0 and a is not zero, then we have ab = a0, and the cancellation property says that b = 0.

2. Most of these aren't too hard, but they do take thinking about things in the right way. Let's see:

1. Suppose d|n and d|m. By the definition, there exist integers x and y such that n = dx and m = dy. But then n + m = dx + dy = d(x+y), and we see that d|(n+m).
2. Exactly the same argument: we have n + m = dx and n = dy, from which we see that m = d(x–y), so d|m.
3. We have d|n, so n = dx for some x. But then mn = dxm = d(xm), so d|mn.
4. Direct translation of the fact that 0 = k0, but if k is not zero there is no x such that k = 0x.
5. Suppose 1 = kx. First of all, we know k is not zero. Next, since kx = (–k)(–x), if k is a divisor, then so is –k. So we can assume k is positive, in which case so is x. Since 1 is the smallest positive number, either k = 1 or k > 1. But if k > 1, kx > x ≥ 1, so in particular kx > 1. Hence we must have k = 1 if k is positive, k = –1 if k is negative.
6. We have n = mx and m = ny. Substituting one into the other we get n = nyx. If n = 0, then it's clear that m = 0. Otherwise, we can use the Cancellation Property to conclude that yx = 1, and now use the previous item to conclude.

3. We know that any triple looks like a = st, b = (s² – t²)/2, c = (s² + t²)/2, with s and t both odd, s > t, with no common factors. The condition c = a + 2 boils down, after some algebra, to (s – t)² = 4, and hence to s = t + 2. So to find triples of this kind all we need to do is choose s and t so that their difference is 2. From there, it's easy to get general formulas. One version is this: the primitive Pythagorean triples with c = a + 2 are given by a = u² – 1, b = 2u, c = u² + 1, where u is any even integer. There are various equivalent ways to say this, of course.

4. The line through (1,1) with slope m has equation y = mx + (1–m). The same argument as we did in class shows that the other intersection between the line and the circle must be rational. Plugging in and using the fact that the product of the roots must be the independent term shows that the other intersection has x = ((1–m)²–2)/(m²+1) and y = (2–(1+m)²)/(m²+1). That gives all the rational points on the circle x² + y² = 2.

The reason this doesn't work for x² + y² = 3 is that there is no first rational point from which to start making lines... though it takes some work to prove that no such point can exist.

[For the hotshots: If a rational solution exists, then the equation x² + y² = 3z² has a solution in integers. Suppose so, and choose the solution in which x has the smallest positive value. When we divide x and y by 3, the remainder must be either 0, 1, or 2. By squaring 3k+1 and 3k+2, we can eliminate these possibilities. Thus, both x and y must be multiples of 3. Write x = 3u, y = 3v, plug in, and divide by 3. It follows that z = 3w. Plug that in, divide the whole equation by 3. The result is an equation just like the original one, but in which u, v, w are smaller than x, y, z. That contradicts our original choice, and so shows that our assumption that a solution exists is false.]

5. The first thing to notice is that the lockers that are open at the end are exactly those whose numbers have an odd number of divisors, since the d^th student changes the state of the n^th locker exactly when d|n.

So it boils down to deciding which numbers have an odd number of divisors. But divisors come in pairs: if d|n, then n = dx and x also divides n. The only case in which this does not yield two distinct divisors is when d = x, that is, when n is a square. Since in all other cases the divisors come in pairs, the squares are exactly the numbers which have an odd number of divisors. Hence lockers 1, 4, 9, 16, 25, etc. are the ones that are open at the end.