## Neat Number Theory/Discrete Math Problem (Pt. III)

**Point of post:** Since I found this problem enjoyable, for some odd reason, I thought I’d also generalize the methodology in the first proof of this post to the general form and give another alternate proof. These methods have both their pros and cons. The general proof of the problem in my last post has the advantage that it finds a general formula for (see that post for this definition) but is maybe a non-obvious approach and leaves the answer is an ostensibly computationally intractable form. The proof in this post is more obvious and ends up with a “nicer” answer but leave you only an “estimate” of for any given . Regardless, it is valuable. And, finally for the sake of logical soundness we prove that the form given in the previous proof and the form given in this one are equivalent.

**Proof (1): **We note once again that

Thus, it is easy to see that

and

from where it easily follows by induction that

from which it becomes apparent that

But, a quick check shows that by definition

where is Euler’s Totient Function. We next notice that is increasing since . Thus, we notice that if denotes reduction then

But, notice that . we see that

are integers. Thus, by our previous discussion we may conclude that

and

It follows from these two equations and that

Thus, noting that since we see that

we may conclude by the Squeeze Theorem that

But, using basic facts about we see that if that

From where the conclusion follows.

We know endeavor to prove the following in two ways, one combinatorial/probabilistic in nature and the other by induction

**Theorem (1): **Let , then

**Proof: **For each consider let and let

evidently then . So letting, as usual, be the probability that we see that for

where is the projection onto the th coordinate. Thus,

But notice that

but the inclusion-exclusion principle states that

From where it follows that

which is what was to be proven.

*Remark: *I can be described, and only by the most generous, as an amateur combinatorialist. There is a good chance I made some stupid error above, if so I would like the hear about it. 🙂

**Theorem: **Let , then

**Proof: **. In this proof we slightly extend our notation so that

We proceed by induction. For this is clear. So, assume that

We note that

Thus, we note that

but we may rewrite the right hand side as

But, changing the index on the right sum gives

and finally factoring out of this right-most sum gives

thus, calling and using this and our induction hypothesis we see that

and thus the induction is complete.

**References: **For more information on Euler’s Totient Function, and number theory in general see:

1. Niven, Ivan, Herbert S. Zuckerman, and Hugh L. Montgomery. *An Introduction to the Theory of Numbers*. New York: Wiley, 1991. Print.

No comments yet.

## Leave a Reply