Hardy and Wright, Chapter 8 (First Part)

This week we met a day early, owing to some scheduling conflicts. If you missed last week’s notes on chapter 7, they’re here. This week we spent an hour talking about things in chapter 8, but did not finish, so we’ll return to the last few sections next week. Chapter 8 is on “Congruences to composite moduli,” and is a bit dense, for us anyway.

Chris continues to claim the book is imprecise, while Eric and I are of the mind that it is simply written in an older style, and could be more verbose. Chris is an algebraist, and Eric and I are topologists, which may have something to do with our discrepancy. Chris’ objection this week concerned statements in the text at the end of section 8.4. In this and the previous section, the congruences under consideration are f(x)\equiv 0\pmod{p^a} for some a>1, and polynomial f. The idea is that you can get at solutions by considering the equivalence mod p^{a-1}. Then depending on the function, and what roots you find mod p^{a-1}, you can say things about roots mod p^a. There is a condition on the derivative of f that I thought was maybe related to field extensions (I vaguely remember things like this coming up in Algebra courses years ago), but we decided this was not the case.

Anyway, Chris was asking about the claim that x^2-c\equiv 0\pmod{2^a} has either 2 roots or 0 when a=2, and 4 or 0 when a>2 (c odd). He had asked me about this earlier in the week, and I have written out the squares mod 4,8,16, and 32, and verified the statement there. Chris was concerned about the relation to the statement of Theorem 123. Looking at that theorem, each root of x^2-c\equiv 0\pmod{2^{a-1}} should either give 2 or 0 roots, mod 2^a, and so it seemed like there should be more and more roots for higher powers. We tried to sort this out for a while, and worked through the proof of Theorem 123 as we went, and eventually decided maybe it was ok. Then, while writing this up I realized probably we hadn’t actually decided how the argument went for these cases. Perhaps I’ll have more for you next week.

Part of the proof of theorem 123 was to re-write f(\xi+sp^{a-1}) as f(\xi)+sp^{a-1}f'(\xi)+\frac{1}{2}s^2p^{2a-2}f''(\xi)+\cdots, a technique that was used a few times in this chapter. When I was reading this I decided it looked like this was a Taylor series, and during our meeting we agreed that this was the case. We also talked about the statement that \frac{f^{(k)}(x)}{k!} is always an integer (it helps that f is polynomial). There’s no way I would have thought to use Taylor series, if I had been trying to prove these statements on my own (which I would be, I suppose, if I were more serious).

I then asked if people had worked through the example at the end of section 8.1, about professors’ lecturing schedule. I could follow the equivalences, but I was a little confused about how the word problem was converted to the equivalences. I can see that starting on Monday, and lecturing every 2 days corresponds to the days 1+2k_1 (if we let Monday be the first day), and similarly for the other lecturing schedules. But then I didn’t understand the condition x=7k_7 corresponding to no lectures on Sunday. Chris suggested that maybe the interpretation of the problem was that instructors would have “lectures” that spanned a few days (like the first professor above, starting on Monday, would have “2-day-lectures”). I think we have since sorted out that this is not correct. The instructor will lecture every n-th day (like n=2 in the example line above), and not lecture any of the other days. The setup of the problem is asking “what is the first Sunday that each lecturer would be lecturing?” Thus, we need equivalences x=a+n_ak_a corresponding to the a-th lecturer lecturing every n_a days (and beginning, conveniently, on the a-th day) to pick out days when everybody would be lecturing, and the equivalence x=7k_7 to pick out Sundays.

Eric asked if the solutions to x^{p-1}-1\equiv 0\pmod{p^a} could be easily determined from the roots of x^{p-1}-1\equiv 0\pmod{p^{a-1}}. Of course, the point of these few sections was that they are roots \xi of the second equation, with some multiple of p^{a-1} added on. So the roots of the first equation have the form \xi+sp^{a-1} for 0\leq \xi<p^{a-1},0\leq s<p. Eric’s question is if those values of s are easy to find. We got a little help from python, working out the case p=5,a=2, but burned out before getting to the next prime. Perhaps we’ll come back to it next week.

Finally, Chris asked about any relation between the polynomials f_m(x) of section 8.5 and cyclotomic polynomials. I only vaguely remember what those are, but he reminded us that the n-th cyclotomic polynomial was one whose roots were exactly the n-th roots of unity. Interpreting this in the finite ring setting (that we are in), he seems to be correct when m is a prime. However, we’re not sure that carries over when m is not prime (which is, perhaps, part of the point of this section). In a related question, he asked what one could say about x^5-1\equiv 0\pmod{6}.

We didn’t come up with too much useful during out meeting, but Eric and I played around with some numbers afterwards. The results of the first few sections of chapter 8 indicate that you should be able to obtain solutions to x^5-1\equiv 0\pmod{6} by considering the equivalence mod 2, and mod 3, and combining the results. Doing so, we note that x^5\equiv x\pmod{2} and also mod 3, so the only roots are x=1\pmod{2} and x=1\pmod{3}. This should give the single root x=1\pmod{6}. We asked python (well, sage, technically, via Eric’s sagenb.org setup), and found the interesting result that x^5\equiv x\pmod 6, which we were both surprised by. We played around with a few other moduli, and continued to be intrigued by what we found. Perhaps we’ll have more to say next week, when we continue our discussion of chapter 8. For now, all we can say is that we’re not too good at thinking in modular arithmetic.


Tags: ,

One Response to “Hardy and Wright, Chapter 8 (First Part)”

  1. Qiaochu Yuan Says:

    Re: square roots \bmod 2^a, the key is the structure of the group of units. For a = 1, 2 the group of units is cyclic, but for a \ge 3 the group of units is the direct sum of a group of order 2 generated by -1 and a group of order 2^{a-1} generated by 5.

    On the other hand, the group of units \bmod p^a for odd primes p is always cyclic.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: