Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
• Meta

I Am The Greatest (Common Divisor)! Topic: Number Theory. Level: Olympiad. December 19th, 2006

Problem: (Stanford Putnam Practice) Suppose is a sequence of positive integers satisfying for . Show that for each .

Solution: Let be an arbitrary positive integer. If we can show that we will be done. We have

so . Then for some positive integer . Similarly, we know so for some positive integer . Then, however,

and

so we must have . Thus . QED.

——————–

Comment: At first, induction seemed the way to go, but after a while you realize that the induction step is, well, not very likely since puts very few restrictions on . So then you look to a better option, trying to find the strongest use of . It turns out that this happens when is a multiple of , which is exactly how the above proof starts.

——————–

Practice Problem: (Stanford Putnam Practice) Let be a prime number. Show that divides infinitely many of the numbers

.

[Reworded]