Let's talk about a useful technique for dealing with certain types of multiplicative number theory problems.

Definition: For a positive integer , let be the greatest such that .

Corollary:

Corollary of Equality:

Corollary:

With this very simple tool we can already prove some useful identities.

Lemma 1:

Lemma 2:

Lemma 3: (simply assume WLOG )

Lemma 4:

Proof: Using the corollary of equality, this reduces to Lemma 3.

Lemma 5: Let . We have the series of identities




...


Again, these are easily proven by assuming WLOG .

Lemma 6: Let be a set of positive integers, and let . Then by the corollary of equality we have the identities



...


These identities are very nice. For they become




And for they are





Note the relation to binomial coefficients. The missing coefficients of give trivial identities such as .

---

Of course, has other uses. Often in problems involving divisibility and/or factorials it is more convenient to consider an equivalent problem given by the corollary of equality than the original problem.

Problem: Prove that is an integer.

Solution: Using the corollary of equality, this reduces to showing that



But if you know that



Then all it takes is another lemma.

Lemma:

---

Practice Problem 1: If are positive integers with odd, determine .

Practice Problem 2: Prove that



Is a polynomial in of degree . (Hint: What "primes" are applicable here?)