## Wednesday, March 2, 2011

### Tutoring & Number Theory

I've been tutoring 'Artemis' for over a year and a half now*. This fall he picked up the book Introduction to Number Theory, by Mathew Crawford, from Art of Problem Solving, and we've spent most of our sessions since then working out of that. I like not having to worry about what we're going to explore, and he seems to like the problems we encounter each week. He and I work through each problem together. Sometimes I hold back more, and get him to do one on his own, and sometimes I do more (with him correcting my mistakes). We skipped most of the first 3 chapters, because he knew most of that.

Number Theory includes so many cool ideas. I especially like playing with modular arithmetic, and seeing the power it can have. I've never taken a number theory course myself, so I'm consolidating my thinking, and enjoying the stretching.

Here's a problem from the book (modified a bit):
Consider n! and the sum 1+2+...+n.
When is the sum a factor of the factorial?
(problem 6.31)
I've got one part solved, and am still thinking about another part...

[Please don't give complete solutions in the comments. But I'd love to know if you've played with it, and what approach you took.]

Enjoy!

_____
*Search on Artemis to find all the posts.

1. Cute problem. I looked at the formulas for computing factorials and triangular numbers and sought insight. Once I had an idea, I then through some carefully chosen test cases at it to validate the idea.

For instance, I verified that when n=36, the sum is not a divisor of the product, but it is when n=38.

I am confident of my solution, but I haven't proven it.

2. I too considered a closed expression for the sum from 1 to n and thought I had an answer pretty quickly. Realized from Blaise's comment that I was missing a piece. I now think that I've dealt with this 2nd part and have an informal proof. So if n=100, the sum isn't a divisor of the factorial but the sum is a divisor when n=101.

3. Yes, fab problem. I was going to say I hadn't figured it out yet but as I started to write down my approach it became clear to me that I had. So, for n=732 the sum does not divide the factorial, but for n=733 it does... is this what you're getting Avery and Blaise?

My approach, like the others, began with writing a closed form for the sum. Then I multiplied and divided some stuff and reduced everything mod n+1. Then I realized I knew what was going on and it reminded me of Wilson's Theorem.

4. Everyone's being so good about hiding their complete thoughts. :^) I guess I'll say a little here. Odd numbers were easy for me. I showed 'Artemis' a proof as I thought it out. Even numbers felt more confusing, but then I thought about it in bed, and realized I had it.

If you have it, you know which even numbers work.

Ben, I'll have to think about Wilson's Theorem when I'm not so tired.