Maths

[jack]

Last night, I decided I definitely *was* pining for maths, and came home and looked out my numbers and sets example sheets. I was pleased that my storage of maths notes, while not anal, was labelled enough that I could find it, though I couldn't find the lecture notes.

(Numbers and Sets was a course in the very first term, taught by Doctor Leader, notorious for requiring no prerequisites, but being a good introduction to how to think about pure maths, and the example sheet questions graduating from "show you can use the theorems taught" to "no-one solves this ever, apart from a few of the supervisors and professors".)

I've gone through the first half. I could do everything fairly easily that I did fairly easily seven years ago.

Amazingly, I can remember the relevant theorems from the first part of the course after all this time and even how to prove them -- no doubt being the first things, and the first interesting things, they sank in more than everything else[1].

I admit, solving the questions would be basically impossible without remembering them -- you'd basically have to deduce them from the whole cloth, which is possible, but requiring a great leap of intuition. This is something to remember for later courses: often becoming lost was due to not grokking that Blah Theorem was the fundamental part of this section of the course.

My logic is, I need some recreational puzzles, and these are perfect for it: based on knowledge I have, and designed to be solvable by a bright person. And that you can work towards solving, requiring a mix of knowledge, perseverance and insight (well, ok, not much so far). Neither requiring application of only a limited set of skills, nor just the right leap of insight (as eg. soduku or riddles do).

If anyone wants to join me, feel free; I can post the questions and the solutions I do work out :) (I would expect someone bright and interested in maths but without a maths background to be able to make a start, though people may disagree in either direction.)

[1] There are only three: (1) That 1,2...(p-1) all have inverses mod p (2) Fermat's Little Theorem, a^p-1=1 mod p and (3) Wilson's Theorem, (p-1)!=(p-1) mod p.

Comments

[cartesiandaemon.livejournal.com]

I'm glad someone else is interested :) I found I could remember the key tricks, and managed to put them back into the proofs -- compared to the rest of the course, they weren't as hard as I remember, though I don't know if I could ever have got it from scratch :)

(I would have thought it necessary to write it down (unless you're familiar with it) -- I find this sort of thing extremely prone to implicit assumptions, especially as going back to the beginning. I expect your proofs are right, though I admit doubt they're rigorous if they're not written down. But maybe that's just me.)

FWIW, you can probably find the proofs online, but what I have is:

(1) Have 1<a<p. Consider a,2a,3a,...,(p-1)a.

These are non-zero mod p, else p divides ai. But p is prime, so must divide one or the other (proof by fundamental theorem of arithmetic, that each number is a unique product of primes), contradiction, as both <p.

Also these must be distinct else some ia=ja (1<=j<i<p) hence (i-j)a==0 (p) hence p divides (i-j)a. Contradiction as before.

But then a,2a...(p-1)a must be equal (mod p) 1,2...,p-1 in some order, hence some ai==1 (p), so i is the required inverse.

(2) (a)(2a)...((p-1)a)==(1)(2)...(p-1) as both lists are the same rearranged (see before). Then a^p-1(p-1)! == (p-1)! (mod p). (p-1)!=/=0 since no product of a,i<p can be a multiple of p. So cancel it from both sides and a^p-1==1 (p)

(3) What are self-inverses? a^2==1 (p) <==> a^2-1==0 <==> (a+1)(a-1)==0 <==> a+1=p (since 1<=a<p, and p| a+1 or a-1 ). So p-1 is the only self-inverse.

Hence (p-1)! is a product of: 1, p-1, and (p-3)/2 pairs of inverses. All the inverses cancel, leaving (p-1)!==(p-1) mod p.

Does that accord?

[alextfish.livejournal.com]

I sat down to write them out before looking at this comment, and you were right, I'd neglected to prove that ia=/=ja mod p for 1<=j<i<p until that point. And I'd also handwaved rather about the self-inverses. But otherwise, yes, that lines up with what was in my head. Yay, maths :)

[cartesiandaemon.livejournal.com]

:) I'm glad I wasn't maligning you too much. I was exactly the same at the time, I always saw the answer and never liked clearing up the edges, however necessary I recognised it. It's obviously not important in this case -- if you needed to be rigorous, you could prove that as soon as you thought of it.

It's a good feeling to know the skill is all still there after all, isn't it? :)

Yay, maths :)

:) Likewise. I've been puzzling all day at work, the first, um, six-ish questions I've been doing were fairly easy, but the next I'm blocked on. I need to check my notes -- there may be another result I'd forgotten which is necessary. Else I just haven't thought how to do it yet.