# 1972 IMO Problems/Problem 3

Let and be arbitrary non-negative integers. Prove that is an integer. (.)

## Solution 1

Let . We intend to show that is integral for all . To start, we would like to find a recurrence relation for .

First, let's look at :

Second, let's look at :

Combining,

.

Therefore, we have found the recurrence relation .

We can see that is integral because the RHS is just , which we know to be integral for all .

So, must be integral, and then must be integral, etc.

By induction, is integral for all .

Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html

## Solution 2

Let p be a prime, and n be an integer. Let be the largest positive integer such that

WTS: For all primes ,

We know

Lemma 2.1: Let be real numbers. Then

Proof of Lemma 2.1: Let and

On the other hand,

It is trivial that

Apply Lemma 2.1 to the problem: and we are pretty much done.

Note: I am lazy, so this is only the most important part. I hope you can come up with the rest of the solution. This is my work, but perhaps someone have come up with this method before I did.