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} $$
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} $$
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.
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}$$
(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 $$
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.
Let $p$ be prime such that $p \not \mid a $ where $a$ is a positive integer. Prove that
$$ a^{p^n - p^{n-1}} \equiv 1 \pmod {p^n} $$
Since $p$ is prime and $p \not \mid a$, we have $\gcd(p, a)=1$, and also $\gcd(p^n, a)=1$. This means we can use Euler's Theorem,
$$ a^{\phi(p^n)} \equiv 1 \pmod {p^n} $$
Now, $\phi(p^n)=p^{n-1}(p-1) = p^n-p^{n-1}$ by Proposition (5.4), and so
$$ a^{p^n - p^{n-1}} \equiv 1 \pmod {p^n} $$
Let $n$ be a positive integer such that $\gcd (n, 10) = 1$. Prove that $n \mid 99 \cdots 99$ where there are $\phi (n)$ number of 9’s in $99 \cdots 99$.
Since $\gcd(n,10)=1$, we can use Euler's Theorem
$$ 10^{\phi(n)} \equiv 1 \pmod {n} $$
This immediately gives us
$$ 10^{\phi(n)} -1 \equiv 0 \pmod {n} $$
which means
$$ \begin{align} n & \mid 10^{\phi(n)} -1 \\ \\ n & \mid 99 \cdots 99 \end {align}$$
The last step uses $10^{\phi(n)} - 1 = 99 \cdots 99$, a decimal number with $\phi(n)$ nines.
Solve the linear congruences
$$ 15x_j ≡ b_j \pmod {32} $$
for $b_j = 5, 7, 9, 11, 13$.
Since $\gcd(15,32)=1$, we can use Euler's Theorem,
$$ 15^{\phi(32)} \equiv 1 \pmod {32} $$
Using $\phi(32)=16$ gives us
$$ \begin{align} 15^{16} & \equiv 1 \pmod {32} \\ \\ 15 \times (15^{15} \times b_j) & \equiv b_j \pmod {32} \end{align}$$
Noting that $15^2 \equiv 225 \equiv 1 \pmod{32}$, gives us $15^{15} \equiv (15^2)^7 \times 15 \equiv 1^7 \times 15 \equiv 15 \pmod {32}$
And so
$$ \begin{align} 15 \times (15^{15} \times b_j) & \equiv b_j \pmod {32} \\ \\ 15 \times (15 \times b_j) & \equiv b_j \pmod {32} \end{align}$$
The following table shows the values of $15 \times b_j \pmod {32}$
| b_j | 15 b_j mod 32 |
| 5 | 11 |
| 7 | 9 |
| 9 | 7 |
| 11 | 5 |
| 13 | 3 |
The solutions for $x_j$ are $11, 9, 7, 5, 3$ for $b_j = 5, 7, 9, 11, 13$, respectively.
Solve the following linear congruences by using Euler’s Theorem:
(a) $7x \equiv 33 \pmod {50}$
(b) $13x \equiv 51 \pmod {100}$
(c) $13x \equiv 52 \pmod {100}$
(a) Since $\gcd(50,7)=1$, we can use Euler's Theorem
$$ 7^{\phi(50)} \equiv 1 \pmod {50} $$
Using $\phi(50) = 20$ we have
$$ \begin{align} 7^{20} & \equiv 1 \pmod {50} \\ \\ 7^{20} \times 33 & \equiv 33 \pmod {50} \\ \\ 7 \times (7^{19} \times 33) & \equiv 33 \pmod {50} \end{align}$$
Noting that $7^2 \equiv 49 \equiv -1 \pmod {50}$ gives us $7^{19} \equiv (7^2)^9 \times 7 \equiv -7 \pmod {50}$.
And so
$$ \begin{align} 7 \times (7^{19} \times 33) & \equiv 33 \pmod {50} \\ \\ 7 \times (-7 \times 33) & \equiv 33 \pmod {50} \\ \\ 7 \times (-231) & \equiv 33 \pmod {50} \end{align}$$
Noting that $-231 \equiv 19 \pmod {50}$ gives us the solution
$$ x \equiv 19 \pmod {50} $$
(b) Since $\gcd(13,100)=1$, we can use Euler's Theorem
$$ 7^{\phi(100)} \equiv 1 \pmod {100} $$
Using $\phi(100) = 40$ we have
$$ \begin{align} 13^{40} & \equiv 1 \pmod {100} \\ \\ 13^{40} \times 51 & \equiv 51 \pmod {100} \\ \\ 13 \times (13^{39} \times 51) & \equiv 51 \pmod {100} \end{align}$$
Noting that $13^3 \equiv 2197 \equiv -3 \pmod {100}$ gives us $13^{39} \equiv (13^3)^{13} \equiv -1594323 \equiv 77 \pmod {100}$
And so
$$ \begin{align} 13 \times (77 \times 51) & \equiv 51 \pmod {100} \\ \\ 13 \times (3927) & \equiv 51 \pmod {100} \end{align}$$
Noting that $3927 \equiv 27 \pmod {100}$ gives us the solution
$$ x \equiv 27 \pmod {100}$$
(c) Since $\gcd(13,100)=1$, we can use Euler's Theorem
$$ 7^{\phi(100)} \equiv 1 \pmod {100} $$
Using $\phi(100) = 40$ we have
$$ \begin{align} 13^{40} & \equiv 1 \pmod {100} \\ \\ 13^{40} \times 52 & \equiv 52 \pmod {100} \\ \\ 13 \times (13^{39} \times 52) & \equiv 52 \pmod {100} \end{align}$$
Noting that $13^3 \equiv 2197 \equiv -3 \pmod {100}$ gives us $13^{39} \equiv (13^3)^{13} \equiv -1594323 \equiv 77 \pmod {100}$
And so
$$ \begin{align} 13 \times (77 \times 52) & \equiv 52 \pmod {100} \\ \\ 13 \times (4004) & \equiv 52 \pmod {100} \end{align}$$
Noting that $4004 \equiv 4 \pmod {100}$ gives us the solution
$$ x \equiv 4\pmod {100}$$
Find the last three digits of $27^{1 000 000}$.
Since $\gcd(27,1000)=1$, Euler's Theorem tells us
$$ 27^{\phi(1000)} \equiv 1 \pmod {1000} $$
Using $\phi(1000) = 400$ gives us
$$ 27^{400} \equiv 1 \pmod {1000} $$
Noting that $1000000 = 400 \times 2500$, we have
$$ 27^{1000000} \equiv (27^{400})^{2500} \equiv 1^{2500} \equiv 1 \pmod {1000} $$
And so the last three digits of $27^{1000000}$ are $001$.
Determine the least non-negative residue $x$ in
$$11^{1767} \equiv x \pmod {301}$$
Since $\gcd(11,301)$ the by Euler's Theorem we have
$$ 11^{\phi(301)} \equiv 1 \pmod {301} $$
Using $\phi(301)=252$ gives us
$$ 11^{252} \equiv 1 \pmod {301} $$
Noting that $1767 = 7(252)+3$, we have
$$ \begin{align} 11^{1767} & \equiv (11^{252})^7 \times 11^3 \pmod {301} \\ \\ & \equiv 1 \times 1331 \pmod {301} \\ \\ & \equiv 127 \pmod {301} \end{align}$$
And so the least non-negative residue $x$ is 127.
Determine the last two digits of $13^{1000}$.
We remind ourselves of Euler's Theorm (5.14), which states that for $n>1$ and $\gcd(n.a)=1$, then
$$ a^{\phi(n)} \equiv 1 \pmod n $$
Since $\gcd(13, 100)=1$ we have
$$ 13^{\phi(100)} \equiv 1 \pmod {100} $$
We have $\phi(100)=40$, and so
$$ 13^{40} \equiv 1 \pmod {100} $$
Noting that $1000 = 40*25$, we have
$$ \begin{align} 13^{1000} & \equiv (13^{40})^{25} \pmod {100} \\ \\ & \equiv 1^{25} \pmod {100} \\ \\ & \equiv 1 \pmod {100} \end{align} $$
So the last two digits of $13^{1000}$ are $01$.
Find the last digit of $7^{2014}$.
We remind ourselves of Euler's Theorm (5.14), which states that for $n>1$ and $\gcd(n.a)=1$, then
$$ a^{\phi(n)} \equiv 1 \pmod n $$
Since $\gcd(10,7)=1$ we have
$$ 7^{\phi(10)} \equiv 1 \pmod {10} $$
That is
$$ 7^{4} \equiv 1 \pmod {10} $$
Using $2014 = 4(503)+2$, we have
$$ \begin{align} 7^{2014} & \equiv (7^4)^{503} \times 7^2 \pmod {10} \\ \\ & \equiv 1 \times 49 \pmod {10} \\ \\ & \equiv 9 \pmod {10} \end{align} $$
And so the last digit of $7^{2014}$ is 9.
Write down two different reduced residue systems modulo 8.
We remind ourselves of Definition (5.11).
A reduced residue system modulo $n$ is the set of integers $\{r_1, r_2, \ldots , r_{\phi (n)}\}$ such that
(i) $\gcd (r_i, n) = 1$ for $i = 1, 2, 3, \ldots , \phi (n)$.
(ii) $r_i \not \equiv r_j \pmod n$ where $i \ne j$.
One reduced residue system modulo 8 is
$$ \{1, 3, 5, 7 \} $$
Another is derived from the above by simply adding $n=8$ to each natural number
$$ \{ 9, 11, 13, 15 \} $$
Let $r_1 = 1, r_2 = 3, r_3 = 5, r_4 = 7$, and $a = 3$. Determine the least non-negative residues $x_j$ for
$j= 1, 2, 3, 4$ such that $ar_j ≡ x_j \pmod {8}$.
What do you notice about your results?
The following shows the least non-negative residues for $x_j$ such that $ar_j \equiv x_j \pmod 8$.
| r | $x_j$ |
| 1 | 3 |
| 3 | 1 |
| 5 | 7 |
| 7 | 5 |
Remembering that sets are unordered, we notice that the set of values of $r$ is the same as the set of values of $x_j$.
We further notice that each value is coprime to 8.
(i) Prove that
$$ \sum _{d \mid p^k} \phi (d) = p^k $$
where $p$ is prime.
(ii) Prove that
$$ \sum _{d \mid p^kq^m} \phi (d) = \sum _{d \mid p^k} \phi (d) \sum _{d' \mid q^m} \phi (d') = p^kq^m $$
where $p$ and $q$ are distinct primes.
(iii) Prove Gauss’s Theorem, that is, for any natural number $n$ we have
$$ \sum _{d \mid n} \phi (d) = n $$
This (iii) is an astonishing result proved by Gauss.
(i) Since $p$ is prime, the only divisors of $p^k$ are
$$ 1, \; p, \; p^2, \; p^3, \; \ldots, \; p^{k-1}, \; p^k $$
And the Euler totient function values of these divisors are
$$ 1, \; (p-1), \; p(p - 1), \; p^2(p-1), \; \ldots , \; p^{k-2}(p-1) , \; p^{k-1}(p-1) $$
The sum of these is
$$ \sum _{d \mid p^k} \phi (d) = 1 + (p-1) + (p^2 -p) + (p^3 -p^2) + \ldots + (p^{k-1}-p^{k-2}) + (p^k - p^{k-1}) $$
The sum reduces because the second term in each bracket is cancelled by the first term of the previous bracket. And so
$$ \sum _{d \mid p^k} \phi (d) = p^k $$
(ii) Since $p$ is prime, the only divisors of $p^k$ are
$$ 1, \; p, \; p^2, \; p^3, \; \ldots, \; p^{k-1}, \; p^k $$
Similarly, since $q$ is a prime, the only divisors of $q^m$ are
$$ 1, \; q, \; q^2, \; q^3, \; \ldots, \; q^{m-1}, \; q^m $$
Since $p$ and $q$ are distinct primes, the factors of $p^kq^m$ are the products of every possible choice of elements from each list above.
$$ \begin{align} & 1(1), \; p(1), \; p^2(1), \; p^3(1), \; \ldots, \; p^{k-1}(1), \; p^k(1), \\ \\ & 1(q), \; p(q), \; p^2(q), \; p^3(q), \; \ldots, \; p^{k-1}(q), \; p^k(q), \\ \\ & 1(q^2), \; p(q^2), \; p^2(q^2), \; p^3(q^2), \; \ldots, \; p^{k-1}(q^2), \; p^k(q^2), \\ \\ & \vdots \\ \\ & 1(q^m), \; p(q^m), \; p^2(q^m), \; p^3(q^m), \; \ldots, \; p^{k-1}(q^m), \; p^k(q^m) \end{align} $$
That is
$$ \sum _{d \mid p^kq^m} \phi (d) = \sum _{d \mid p^k} \phi (d) \sum _{d' \mid q^m} \phi (d') $$
Using the result from part (i), we have $ \sum _{d \mid p^k} \phi(d) = p^k$ and $\sum _{d' \mid q^m} \phi (d') = q^m$, and so
$$ \sum _{d \mid p^kq^m} \phi (d) = \sum _{d \mid p^k} \phi (d) \sum _{d' \mid q^m} \phi (d') = p^kq^m $$
(iii) We will use induction.
Let $P(z)$ be the following statement referring to a natural number $n_z=p_1^{k_1}p_2^{k_2}\ldots p_z^{k_z}$ which has $z$ distinct primes in its prime decomposition.
$$ P(z) \quad := \quad \sum _{d \mid n_z} \phi (d) = n_z $$
We need to prove the base case $P(1)$ and the inductive step $P(z) \implies P(z+1)$.
Base Case $P(1)$
The base case $P(1)$ is, for some prime $p$ and natural number $k$
$$ P(1) \quad := \quad \sum _{d \mid n_1} \phi (d) = n_1 = p^k $$
This was proved in part (i) above, and so the base case is true. Indeed, in part (ii) we proved $P(2)$.
Inductive Step $P(z) \implies P(z+1)$
We assume $P(z)$ is true, the induction hypothesis, and aim to show $P(z+1)$
$$ P(z+1) \quad := \quad \sum _{d \mid n_{z+1}} \phi (d) = n_{z+1} $$
We first note that any divisor $d_{z+1}$ of $n_{z+1}$ is a product of a divisor $d_z$ of $n_z$ and a divisor $d'$ of $p_{z+1}^{k_{z+1}}$.
$$ d_{z+1} = d_z \times d' $$
Since $d_z$ and $d'$ are coprime, we have
$$ \phi(d_{z+1}) = \phi(d_z) \times \phi(d') $$
And so the sum of the Euler totient function of the divisors of $n_{z+1}$ is
$$ \begin{align} \sum_{d_{z+1}} \phi(d_{z+1}) & = \sum_{d_z, \; d'} \left ( \phi(d_z) \times \phi(d') \right ) \\ \\ &= \sum_{d_z \mid n_z} \phi(d_z) \times \sum_{d' \mid p_{z+1}^{k_{z+1}}} \phi(d') \end{align}$$
The induction hypothesis $P(z)$ gives us
$$ \sum_{d_{z+1}\mid n_{z+1}} \phi(d_{z+1}) = n_z \times \sum_{d' \mid p_{z+1}^{k_{z+1}}} \phi(d') $$
And the result from part (i) gives us
$$ \begin {align} \sum_{d_{z+1}\mid n_{z+1}} \phi(d_{z+1}) & = n_z \times p_{z+1}^{k_{z+1}} \\ \\ & = n_{z+1} \end{align} $$
And so $P(z+1)$ is true if $P(z)$ is true.
By induction we have proved Gauss’s Theorem, that is, for any natural number $n$ we have
$$ \sum _{d \mid n} \phi (d) = n $$