Number Theory: In Context and Interactive

Compute the group of units \(U_n\) for \(n=10,11,12\text{.}\)

Prove Theorem 7.5.3 as a corollary of Theorem 9.2.5.

Prove that if \(p\) is prime, then \(a^p\equiv a\) (mod \(p\)) for every integer \(a\text{.}\)

Use Exercise 9.6.3 to prove the polynomial \(x^5-x+2\) has no integer roots (see Section 4.5 for context).

Formally prove that \(\phi(p)=p-1\) for prime \(p\text{,}\) by deciding which \([a]\in \{[0],[1],[2],\ldots,[p-2],[p-1]\}\) have \(\gcd(a,p)=1\text{.}\)

Verify Euler’s Theorem by hand for \(n=15\) for all relevant \(a\) (note that \(\phi(15)=8\text{,}\) and remember that \(a^8=((a^2)^2)^2\) so we can use modulo reduction at each squaring).

Get the inverse of 29 modulo 31, 33, and 34 using Euler’s Theorem.

Evaluate without a calculator \(11^{49}\) (mod \(21\)) and \(139^{112}\) (mod \(27\)).

Solve the congruence \(33x\equiv 29\) (mod \(127\)) and (mod \(128\)).

Solve as many of the systems of congruences we already did Exercises 5.6 using the Chinese Remainder Theorem and Euler’s Theorem as you need in order to understand how it works. Follow the models closely if necessary.

Use the facts from Section 9.5 to create a general formula for \(\phi(N)\) where \(N=\prod_{i=1}^k p_i^{e_i}\text{.}\) Then prove it by induction.

Conjecture and prove a necessary (or even sufficient) criterion for when \(\phi(n)\) is even. (Thanks to Jess Wild.)

Compute the \(\phi\) function evaluated at 1492, 1776, and 2001.

Prove whether there are infinitely many values of \(\phi\) that end in zero.

Conjecture whether there are any relations between \(m\) and \(n\) that might lead \(\phi(m)\) to divide \(\phi(n)\text{.}\)

Look up the Carmichael conjecture about \(\phi\text{.}\) What does it say, and what is the current status⁵ of this conjecture?

For those with an interest in computer science: Look up the Busy Beaver problem for Turing machines. Then read this description of how Euler’s Theorem helps prove the immense size of the current record holder⁶ (as of this writing). Explain in your own words how it helped, but also what additional (number-theoretic) tools were needed.