Let $p$ be prime. If the order of $a$ modulo $p$ is $k$, show that
$$ k \mid (p− 1) $$
We're given
$$ a^k \equiv 1 \pmod p $$
Since $\gcd(p,a)=1$, because the order exists, Euler's Theorem tells us
$$ a^{\phi(p)} \equiv a^{p-1} \equiv 1 \pmod p $$
Since $k$ is the smallest positive integer such that $a^k \equiv 1 \pmod n$, then $(p-1)$ is a multiple of $k$.
That is,
$$ k \mid (p-1) $$
Explain why $a \pmod 2$ where $a$ is odd has order 1.
Since $a$ is odd, we have by definition of odd
$$ a = 1 \pmod 2 \tag{i}$$
The order of $a$ modulo 2 is the smallest positive $k$ such that
$$ a^k = 1 \pmod 2 \tag{ii}$$
where $\gcd(2,a)=1$, which is true for all odd $a$ since 2 is prime.
We can see from (i) that $k=1$ is the smallest positive integer that satisfies (ii).
So the order of odd $a$ modulo 2 is 1.
Prove that if $a$ modulo $n$ has order $mk$ where $m, k$ are positive integers then $a^m$ has order $k$.
We're given $mk$ as the order of $a$ modulo $n$. This means
$$ a^{mk} \equiv 1 \pmod n $$
Rewriting
$$ (a^{m})^{k} \equiv 1 \pmod n $$
This is a necessary for $k$ to be the order of $a^m$, but not sufficient.
We also need to show that $k$ is the smallest positive integer such that $(a^m)^k \equiv 1 \pmod n$.
For the purpose of contradiction, let's assume $j<k$ is the order of $a^m$ modulo $n$. That would mean
$$ (a^m)^j \equiv 1 \pmod n $$
That is
$$ a^{mj} \equiv 1 \pmod n $$
Here $mj < mk$ which is not possible because we're given $mk$ as the order of $a$, and so $mk$ is the least positive integer such that $a^{mk} \equiv 1 \pmod n$.
We have shown that if $a$ modulo $n$ has order $mk$ where $m, k$ are positive integers, then $a^m$ has order $k$.
Let the order of $a$ modulo $n$ be $k$. Show that inverse of $a$ modulo $n$ is
$$ a^{k−1} \pmod n $$
That $k$ is the order of $a$ modulo $n$ means
$$ a^k \equiv 1 \pmod {n} $$
Factorising
$$ a \times a^{k-1} \equiv 1 \pmod {n} $$
By definition of inverse, this tells us the inverse of $a$ modulo $n$ is $a^{k-1}$.
Determine the last three digits of $3^{311}$.
We need to find the least positive residue $x$ such that
$$ 3^{311} \equiv x \pmod {1000} $$
Since $\gcd(3,1000)=1$, Euler's Theorem gives us $3^{\phi(1000)} \equiv 1 \pmod {1000}$. The order of 3 modulo 1000 is a factor of $\phi(1000)=400$. These factors are 1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 200, 400, and are the are the only ones we need to test.
| n | 3^n | 3^n mod 1000 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 81 |
| 5 | 243 | 243 |
| 8 | 6561 | 561 |
| 10 | 59049 | 49 |
| 16 | 43046721 | 721 |
| 20 | 3486784401 | 401 |
However, the above numerical calculations show that none of the factors up to and including 20 is the order. Calculations for factors larger than 20 are not feasible on a calculator.
Since we can't use the order, we use slightly less convenient reductions:
$$ \begin{align} 3^{311} & \equiv (3^{10})^{30} \times 3^{11} \pmod {1000} \\ \\ & \equiv (49^{6})^5 \times 147 \pmod {1000} \\ \\ & \equiv (201)^5 \times 147 \pmod {1000} \\ \\ & \equiv 48227818947147 \pmod {1000} \\ \\ & \equiv 147 \pmod {1000} \end{align} $$
So the last three digits of $3^{311}$ are 147.
Note: the author's solution assumes that we can calculate $3^{100} \equiv 1 \pmod {1000}$, but this is not possible on most calculators.
In each of the following cases determine the least non-negative residue $x$:
(a) $3^{1000} \equiv x \pmod {17} $
(b) $3^{970} \equiv x \pmod {98} $
(a) Since $\gcd(3,17)=1$, Euler's Theorem gives us $3^{\phi(17)} \equiv 1 \pmod{17}$. This means the order of 3 modulo 17 is a factor of $\phi(17)=16$. These factors are 1, 2, 4, 8, 16, and these are the only ones we need to test.
The following calculations show that $2^{16}\equiv 1 \pmod {17}$.
| n | 3^n | 3^n mod 17 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 13 |
| 8 | 6561 | 16 |
| 16 | 43046721 | 1 |
The order of 3 modulo 17 is 16.
This gives us $3^{16} \equiv 1 \pmod {17}$. Using Proposition (6.6) we have
$$ \begin{align} 3^{1000} & \equiv 3^{(1000 \bmod 16)} \pmod {17} \\ \\ & \equiv 3^8 \pmod {17} \\ \\ 3^{1000} & \equiv 16 \pmod {17} \end{align} $$
So the least non-negative residue is $x=16$.
(b) Since $\gcd(3, 98)=1$, Euler's Theorem tells us $3^{\phi(98)} \equiv 1 \pmod{98}$. This means the order of 3 modulo 98 is a factor of $\phi(98)=42$. These factors are 1, 2, 3, 6, 7, 14, 21, 42, and these are the only ones we need to test.
The following calculations show that $4^n \neg \equiv 1 \pmod {98}$ for $n=1, 2, 3, 6, 7, 14, 21$.
| n | 3^n | 3^n mod 98 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 3 | 27 | 27 |
| 6 | 729 | 43 |
| 7 | 2187 | 31 |
| 14 | 4782969 | 79 |
| 21 | 10460353203 | 97 |
This leave only 42 as the order of 3 modulo 98.
We now have $3^{42} \equiv 1 \pmod {98}$. Using Proposition (6.6) we have
$$ \begin{align} 3^{970} & \equiv 3^{(970 \bmod 42)} \pmod {98} \\ \\ & \equiv 3^4 \pmod {98} \\ \\ 3^{1000} & \equiv 81 \pmod {98} \end{align} $$
So the least non-negative residue is $x=81$.
Find the order of 5 modulo 21. Hence, or otherwise, solve
$$ 5x \equiv 16 \pmod {21} $$
Since $\gcd(21,5)=1$ Euler's Theorem tells us $5^{\phi(21)} \equiv 1 \pmod {21}$. This means the order if a factor of $\phi(21)=12$. These factors are 1, 2, 3, 4, 6, 12, and are the only ones we need to test.
The following calculations show $5^6 \equiv 15625 \equiv 1 \pmod {21}$.
| n | 5^n | 5^n mod 21 |
| 1 | 5 | 5 |
| 2 | 25 | 4 |
| 3 | 125 | 20 |
| 4 | 625 | 16 |
| 6 | 15625 | 1 |
The order of 5 modulo 21 is 6.
This means
$$ 5^6 \equiv 1 \pmod {21} $$
Factorising
$$ 5 \times (5^5) \equiv 1 \pmod {21} $$
So the inverse of 5 modulo 21 is $5^5 \equiv 3125 \equiv to 17 \pmod {21}$.
We can use the inverse to solve the linear congruence.
$$ \begin{align} 5x & \equiv 16 \pmod {21} \\ \\ 17 \times 5 \times x \equiv 17 \times 16 \pmod {21} \\ \\ x & \equiv 272 \pmod {21} \\ \\ & \equiv 20 \pmod {21} \end{align} $$
So the solution is $x \equiv 20 \pmod {21}$.
Determine the order 7 modulo 60. Also find the inverse of 7 modulo 60 and solve the linear congruence
$$ 7x \equiv 59 \pmod {60} $$
Since $\gcd(7,60)=1$, Euler's Theorem tells us $7^{\phi(60)} \equiv 1 \pmod {60}$. And so the order is a factor of $\phi(60)=16$. These factors are 1, 2, 4, 8 and 16, and are the only ones we need to test.
The following calculations show $7^4 \equiv 2401 \equiv 1 \pmod {60}$.
| n | 7^n | 7^n mod 60 |
| 1 | 7 | 7 |
| 2 | 49 | 49 |
| 4 | 2401 | 1 |
The order of 7 modulo 60 is 4.
This means
$$ 7^4 \equiv 1 \pmod {60} $$
Factorising
$$ 7 \times (7^3) \equiv 1 \pmod {60} $$
So the inverse of 7 modulo 60 is $7^3 \equiv 343 \equiv 43 \pmod {60}$.
We can use the inverse to solve the linear congruence
$$ \begin{align} 7x & \equiv 59 \pmod {60} \\ \\ 7^{-1} \times 7x & \equiv 43 \times 59 \pmod {60} \\ \\ x & \equiv 2537 \pmod {60} \\ \\ & \equiv 17 \pmod {60} \end{align} $$
So the solution is $x \equiv 17 \pmod {60}$.
Determine the order of 3 modulo 100. Hence, or otherwise, find the last two digits of $3^{1001}$.
Since $\gcd(3,100)=1$, Euler's Theorem tells us $3^{\phi(100)} \equiv 1 \pmod {100}$. This means the order is a factor of $\phi(100)=40$. These factors are 1, 2, 4, 5, 8, 10, 20, and 40, and these factors are the only ones we need to test.
The following calculations show $3^{20} \equiv 1 \pmod {100}$.
| n | 3^n | 3^n mod 100 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 81 |
| 5 | 243 | 43 |
| 8 | 6561 | 61 |
| 10 | 59049 | 49 |
| 20 | 3486784401 | 1 |
The order of 3 modulo 100 is 20.
Noting that $1001 = (20 \times 50) + 1$, we proceed as follows
$$ \begin{align} 3^{1001} & \equiv (3^{20})^{50} \times 3 \pmod {100} \\ \\ & \equiv (1)^{50} \times 3 \pmod {100} \\ \\ & \equiv 3 \pmod {100} \end{align}$$
So the last two digits of $3^{1001}$ are 03.
Given that the order of 5 modulo 13 is 4, determine the least non-negative residue $x$ such that $5^{101} \equiv x \pmod {13}$.
We're given
$$ 5^4 \equiv 1 \pmod 13 $$
Using $101 = (25 \times 4) + 1$, we have
$$ 5^{101} \equiv (5^4)^25 \times 5^1 \equiv (1) \times 5 \equiv 5 \pmod {13} $$
And so the least non-negative residue $x$ is 5.
Determine the orders of the following:
(a) $3 \pmod {10}$
(b) $7 \pmod {12}$
(c) $9 \pmod {16}$
(d) $11 \pmod {25}$
(e) $3 \pmod {13}$
(a) The following calculations show $3^4 \equiv 81 \equiv 1 \pmod {10}$.
| n | 3^n | 3^n mod 10 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 3 | 27 | 7 |
| 4 | 81 | 1 |
Since $\gcd(3,10)=1$, the order of 3 modulo 10 is 4.
(b) The following calculations show $7^2 \equiv 49 \equiv 1 \pmod {12}$.
| n | 7^n | 7^n mod 12 |
| 1 | 7 | 7 |
| 2 | 49 | 1 |
Since $\gcd(7,12)=1$, the order of 7 modulo 12 is 2.
(c) The following calculations show $9^2 \equiv 81 \equiv 1 \pmod {16}$.
| n | 9^n | 9^n mod 16 |
| 1 | 9 | 9 |
| 2 | 81 | 1 |
Since $\gcd(9,16)=1$, the order of 9 modulo 16 is 2.
(d) The following calculations show $11^5 \equiv 161051 \equiv 1 \pmod {25}$.
| n | 11^n | 11^n mod 25 |
| 1 | 11 | 11 |
| 2 | 121 | 21 |
| 3 | 1331 | 6 |
| 4 | 14641 | 16 |
| 5 | 161051 | 1 |
Since $\gcd(11,25)=1$, the order of 11 modulo 25 is 5.
(e) The following calculations show $3^3 \equiv 27 \equiv 1 \pmod {13}$.
| n | 3^n | 3^n mod 13 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 3 | 27 | 1 |
Since $\gcd(3,13)=1$, the order of 3 modulo 13 is 3.
Find the order of 2
(a) modulo 7
(b) modulo 11
(c) modulo 17
(d) modulo 23
We do this exercise by brute force, as per the textbook's examples at the beginning of Chapter 6.
(a) The following calculations show $2^3 \equiv 8 \equiv 1 \pmod 7$.
| n | 2^n | 2^n mod 7 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 1 |
Since $\gcd(2,7)=1$, the order of 2 modulo 7 is 3.
(b) The following calculations show $2^{10} \equiv 1024 \equiv 1 \pmod {11}$.
| n | 2^n | 2^n mod 11 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 5 |
| 5 | 32 | 10 |
| 6 | 64 | 9 |
| 7 | 128 | 7 |
| 8 | 256 | 3 |
| 9 | 512 | 6 |
| 10 | 1024 | 1 |
Since $\gcd(2,11)=1$, the order of 2 modulo 11 is 10.
(c) The following calculations show $2^8 \equiv 256 \equiv 1 \pmod {17}$.
| n | 2^n | 2^n mod 17 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 16 |
| 5 | 32 | 15 |
| 6 | 64 | 13 |
| 7 | 128 | 9 |
| 8 | 256 | 1 |
Since $\gcd(2,17)=1$, the order of 2 modulo 17 is 8.
(d) The following calculation show $2^11 \equiv 2048 \equiv 1 \pmod {23}$.
| n | 2^n | 2^n mod 23 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 16 |
| 5 | 32 | 9 |
| 6 | 64 | 18 |
| 7 | 128 | 13 |
| 8 | 256 | 3 |
| 9 | 512 | 6 |
| 10 | 1024 | 12 |
| 11 | 2048 | 1 |
Since $\gcd(2,23)=1$, the order of 2 modulo 23 is 11.
Determine the last three digits of
$$ 2019^{2019^{2019}} $$
[Tower rule $a^{m^n}= a^{(m^n)}$.]
Lemma
We first prove a useful lemma. For natural numbers $x,n$, if $\gcd(x,n)=1$ then by Euler's Theorem
$$ x^{\phi(n)} \equiv 1 \pmod n $$
For a natural number $y$, we use the division algorithm to write
$$ y = \bigl (y \text{ div } \phi(n) \times \phi(n) \bigr ) + \bigl (y \text{ mod } \phi(n) \bigr ) $$
where the div and mod operators are integer division and remainder.
This gives us
$$ \begin{align} x^{y} & \equiv x^{\bigl (y \text{ div } \phi(n) \times \phi(n) \bigr ) + \bigl (y \text{ mod } \phi(n) \bigr )} \pmod n \\ \\ & \equiv x^{\bigl (y \text{ div } \phi(n) \times \phi(n) \bigr )} \times x^{(y \text{ mod } \phi(n))} \pmod n \\ \\ & \equiv (x^{\phi(n)})^{(y \text{ div } \phi(n))} \times x^{(y \text{ mod } \phi(n))} \pmod n \\ \\ & \equiv 1 \times x^{(y \text{ mod } \phi(n))} \pmod n \\ \\ & \equiv x^{(y \text{ mod } \phi(n))} \pmod n \end{align} $$
And so if $\gcd(x,n)=1$, then for some natural $y$, we have
$$ x^y \equiv x^{(y \bmod \phi(n))} \pmod n $$
Solution
We need to find the least positive $x$ such that
$$ 2019^{2019^{2019}} \equiv x \pmod {1000} $$
We simplify the base using $2019 \equiv 19 \pmod {1000}$,
$$ x \equiv 19^{2019^{2019}} \pmod {1000} $$
Using the lemma above, and noting $\phi(1000)=400$, we have
$$ x \equiv 19^{(2019^{2019} \bmod 400 )} \pmod {1000} $$
We now focus on that index $(2019^{2019} \bmod 400 )$. This is the least positive $y$ such that
$$ 2019^{2019} \equiv y \pmod {400} $$
We simplify the base using $2019 \equiv 19 \pmod {400}$,
$$ y \equiv 19^{2019} \pmod {400} $$
Using the lemma above, and noting $\phi(400)=160$, we have
$$ \begin{align} y & \equiv 19^{(2019 \bmod 160)} \pmod {400} \\ \\ y & \equiv 19^{99} \pmod {400} \end{align} $$
We now calculate $19^{99} \pmod {400}$, using
$$ \begin{align} 19^{99} & \equiv 19^{81} \times 19^{9} \times 19^{9} \pmod {400} \\ \\ & \equiv (19^{3})^{27} \times (19^{3})^3 \times (19^{3})^3 \pmod {400} \\ \\ & \equiv (59^3)^9 \times 59^3 \times 59^3 \pmod {400} \\ \\ & \equiv (179^3)^3 \times 179 \times 179 \pmod {400} \\ \\ & \equiv (139)^3 \times 179 \times 179 \pmod {400} \\ \\ & \equiv (19)^3 \times 179 \times 179 \pmod {400} \\ \\ & \equiv 608779 \pmod {400} \\ \\ & \equiv 379 \pmod {400} \end{align}$$
And so $y = 379$. This gives us
$$ x \equiv 19^{379} \pmod {1000} $$
The same method of calculation as above gives us $x = 179$.
And so
$$ 2019^{2019^{2019}} \equiv 179 \pmod {1000} $$
which means the last three digits of $2019^{2019^{2019}}$ are 179.