Exercise (5.2).17

Let $\{r_1, r_2, r_3, \ldots , r\phi(n)\}$ be a set of reduced residue system modulo $n$.

Show that $r_j^{−1} \equiv r_k \pmod n$ where $1 \le j, k \le \phi (n)$.

[The inverse of any residue in the reduced residue system is also in this system.]

By definition, $\gcd(r_j, n)=1$. This means we can use Euler's Theorem, which tells us

$$ r_j^{\phi(n)} \equiv 1 \pmod n $$

Factorising,

$$ r_j \times r_j^{\phi(n)-1} \equiv 1 \pmod n $$

And so the multiplicative inverse of $r_j$ is

$$r_j^{-1}=r_j^{\phi(n)-1}$$

Now, $\gcd(r_j,n)=1$ implies $\gcd(r_j^m,n)=1$ for any natural number $m$, including $m=\phi(n)=1$. That is

$$ \gcd(r_j^{\phi(n)-1}, n)=1 $$

This is membership criteria for being in the reduced residue system modulo $n$.

This means the inverse of any residue in the reduced residue system is also in the system.

Exercise (5.2).16

Let $a$ be a natural number such that $\gcd (a, 16) = 1$.

Find the multiplicative inverse of $a^3$ modulo 16 as a power of $a$.

Since $\gcd(a,16)=1$, Euler's Theorem gives us

$$ a^{\phi(16)} \equiv 1 \pmod {16} $$

Using $\phi(16)=8$, 

$$ a^{8} \equiv 1 \pmod {16} $$

Factorising,

$$ a^3 \times a^5 \equiv 1 \pmod {16} $$

And so the multiplicative inverse of $a^3$ is

$$ (a^3)^{-1} \equiv a^5 \pmod {16} $$

Exercise (5.2).15

Let $p$ and $q$ be distinct primes. Prove that

$$ p^{q−1} + q^{p−1} \equiv 1 \pmod {pq} $$

We can use result of the previous exercise: if $\gcd (m, n) = 1$, then

$$ m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod {mn} $$

Since $p$ and $q$ are prime, we have $\gcd(p,q)=1$, and so

$$ p^{\phi(q)} + q^{\phi(p)} \equiv 1 \pmod {pq} $$

Using $\phi(q)=q-1$ and $\phi(p)=p-1$,  we conclude

$$ p^{q-1} + q^{p-1} \equiv 1 \pmod {pq} $$

Exercise (5.2).14

Let $\gcd (m, n) = 1$. Prove that 

$$ m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod {mn} $$

Hint: Use the Chinese remainder theorem.

Since $\gcd (m, n) = 1$, Euler's Theorem gives us

$$ m^{\phi(n)} \equiv 1 \pmod n $$

$$ n^{\phi(m)} \equiv 1 \pmod m $$

This means, for some integers $j,k$, 

$$ m^{\phi(n)} - 1 = j n $$

$$ n^{\phi(m)} - 1 = k m $$

Multiplying gives us

$$ \begin{align} jk(mn) & = (m^{\phi(n)} -1 ) (n^{\phi(m)} - 1) \\ \\ & = m^{\phi(n)}n^{\phi(m)} - n^{\phi(m)} -  m^{\phi(n)}  + 1 \\ \\ mn(jk - m^{\phi(n)-1}n^{\phi(m)-1}) -1 & = - n^{\phi(m)} -  m^{\phi(n)} \end{align} $$

That is

$$  n^{\phi(m)} +  m^{\phi(n)} = 1 +  mn( m^{\phi(n)-1}n^{\phi(m)-1} - jk)$$

Which is equivalent to

$$ n^{\phi(m)} +  m^{\phi(n)} \equiv 1 \pmod {mn} $$

Note: this didn't require use of the Chinese remainder theorem.

Exercise (5.2).13

Let the primes $p = 3, q = 23$ and $n = p \times q$.

(i) Determine $\phi (n)$.

(ii) Determine $3^{-1} \pmod { \phi (n)}$.

(i) Since $n=p \times q$, where $p$ and $q$ are prime, we can take advantage of the multiplicity of Euler's totient function.

$$ \begin{align} \phi(n) & = \phi(p \times q) \\ \\ & = \phi(3) \times \phi(23) \\ \\ & = (3-1) \times (23-1) \\ \\ \phi(n) & = 44  \end{align} $$

(ii) Since $\gcd(\phi(n),3) = \gcd(44,3)=1$, we can use Euler's Theorem

$$ 3^{\phi(44)} \equiv 1 \pmod {44} $$

Noting that $\phi(44)=20$, and factorising the LHS gives us

$$ 3 \times 3^{20-1} \equiv 1 \pmod {44}$$

By definition of inverse, we have 

$$ 3^{-1} \equiv 3^{19} \pmod {\phi(n)} $$

Using $3^{10} \equiv 59049 \equiv 1 \pmod {44}$, we have $3^{19} \equiv (3^{10})\times 3^9 \equiv 19683 \equiv 15 \pmod {44}$

And so

$$ 3^{-1} \equiv 15 \pmod {44}$$

Exercise (5.2).12

(a) Let $\gcd (a, n) = 1$. Prove that

$$ a^{−1} \equiv  a^{\phi(n)−1} \pmod n $$

(b) Let $\gcd (a, n) = 1$. Show that the solution of the linear congruence

$$ ax \equiv b \pmod n $$

is given by

$$ x \equiv ba^{\phi(n)−1} \pmod n $$

(a) Since $\gcd(a,n)=1$, we can use Euler's Theorem

$$ a^{\phi(n)} \equiv 1 \pmod n $$

Factorising the LHS we have

$$ a \times a^{\phi(n)-1} \equiv 1 \pmod n $$

By the definition of inverse, we have $a \times a^{-1} \equiv 1 \pmod n$, and so

$$ a^{-1} \equiv a^{\phi(n)-1} \pmod n $$

(b) Since $\gcd(a,n)=1$ we can use Euler's Theorem

$$ a^{\phi(n)} \equiv 1 \pmod n $$

Multiplying both sides by $b$ and also factorising $a^{\phi(n)}$ as above gives us

$$ a \times \bigl ( a^{\phi(n)-1} \times b \bigr ) \equiv b \pmod n $$

And so, by comparison, we can see the solution of the linear congruence $ax \equiv b \pmod n$ is

$$ x \equiv ba^{\phi(n)−1} \pmod n $$

Exercise (5.2).11

For the following either give a proof or exhibit a counterexample:

Let $\gcd (a, n) = 1$ then

$$ a^{\phi(\phi(n))} ≡ 1 \pmod n $$

Consider $a=3, n=5$, which means $\gcd(3,5)=1$.

We have $\phi(5)=4$, and so $\phi(\phi(5)) = \phi(4) = 2$.

And so

$$ \begin{align} a^{\phi(\phi(n))} & \equiv  3^{2} \pmod 5 \\ \\ & \equiv 9 \pmod 5 \\ \\ & \equiv 4 \pmod 5 \\ \\ a^{\phi(\phi(n))} & \not \equiv 1 \pmod n \end{align}$$

This is a counter-example to the given proposition.