Loading [MathJax]/extensions/TeX/newcommand.js
Skip to main content
🔗

Exercises 9.6 Exercises

🔗
1.

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

🔗
3.

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

🔗
5.

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{.}

🔗
6.

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).

🔗
7.

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

🔗
8.

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

🔗
9.

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

🔗
10.

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.

🔗
11.

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.

🔗
12.

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

🔗
13.

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

🔗

Let f(n)=\phi(n)/n\text{.}

🔗
14.

Show that f(p^k)=f(p) if p is prime.

🔗
15.

Find the smallest n such that f(n)<1/5\text{.}

🔗
16.

Find all n such that f(n)=1/2\text{.}

🔗
17.

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

🔗
18.

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

🔗
20.

Use the ideas that proved \phi was multiplicative (Subsection 9.5.2) to see whether you can finally solve the “first problem”, Section 1.1. Especially think of making a table.