Exercise (4.1).6

Show that $2^{2046} ≡ 1 \pmod {2047}$. Check whether 2047 is prime.

We start with $2^{11} = 2048$, and so

$ 2^{11} \equiv 1 \pmod {2047} $

$  2^{2046} \equiv (2^{11})^{186} \equiv 1 \pmod {2047}$.

2047 is not prime since $2047 = 23 \times 89$.

Exercise (4.1).5

(a) Show that $2^{8190} ≡ 1  \pmod {8191}$. What can you say about the number 8191?

(b) Show that $2^{65536} ≡ 1 \pmod {65537}$. What can you say about the number 65537?

(a) From experience we know that 8192 is a power of 2. In fact, $2^{13} = 8192$. And so

$2^{13} \equiv 1 \pmod {8191}$

$ 2^{8190} \equiv (2^{13})^{630} \equiv 1 \pmod {8191}$

This suggests 8191 is a candidate for being a prime.

(b) Similarly, we know that $2^{16}=65536$ and so 

$ 2^{16} \equiv -1 \pmod {65537} $

$ 2^{65536} \equiv (2^{16})^{4096} \equiv 1 \pmod {65537} $

This suggests 65537 is a candidate for being a prime.

Exercise (4.1).4

(i) Find $8^{21} \pmod {23}$.

(ii) Solve the equation $8x ≡ 7 \pmod {23}$.

(i) Since 23 is a prime, and does not divide 8, we can use the FlT.

$ 8^{22} \equiv 1 \pmod {23} $

$ 8^{21} \times 8 \equiv 1 \pmod {23} $

By inspection we can see that $8^{21} \equiv 3 \pmod {23}$ gives us $3 \times 8 \equiv 24 \equiv 1 \pmod {23}$.

And so $8^{21} \equiv 3 \pmod {23}$.

(ii) From above we have $ 8^{21} \times 8 \equiv 1 \pmod {23} $ and $8^{21} \equiv 3 \pmod {23}$, and so

$ 3 \times 8 \equiv 1 \pmod {23} $

$ 3 \times 8 \times 7 \equiv 7 \pmod {23} $

Which gives us $x \equiv 21 \pmod {23}$.

Exercise (4.1).3

(i) Determine the remainder when $6^{2014}$ is divided by 11.

(ii) Determine the remainder when $6^{2013}$ is divided by 11.

(i) We need to solve

$$ 6^{2014} \equiv x \pmod {11} $$

Since 11 is prime, and does not divide 6, we have by FlT

$ 6^{10} \equiv 1 \pmod {11} $

And so

$ 6^{2014} \equiv (6^{10})^{201} \times 6^4 \equiv 6^4 \equiv 1296 \pmod {11} $

$ 6^{2014} \equiv 9 \pmod {11} $

So the remainder when $6^{2014}$ is divided by 11 is 9.

(ii) This is very similar to the above. The difference leads to

$ 6^{2013} \equiv (6^{10})^{201} \times 6^3 \equiv 6^3 \equiv 216 \pmod {11} $

$ 6^{2013} \equiv 7 \pmod {11} $

So the remainder when $6^{2013}$ is divided by 11 is 7.

Exercise (4.1).2

Determine the multiplicative inverse of the following numbers by using Fermat’s Little Theorem. Give your answer as the least non-negative residue.

(a) $5 \pmod {11}$

(b) $9 \pmod {23}$

(c) $2 \pmod {37}$

(d) $5 \pmod {41}$

For integer $a$ and prime $p$, where $p \not \mid a$, we have

$$ a^{p-1} \equiv 1 \pmod p \; \implies \; a(a^{p-2}) \equiv 1 \pmod p \; \implies \; a^{-1} \equiv a^{p-2} \pmod p $$

(a) Here 11 is prime, and does not divide 5, and so

$ 5^{-1} \equiv 5^{9} \pmod {11} $

Using $5^3 \equiv 125 \equiv 4 \pmod {11}$, we have

$ 5^{-1} \equiv (5^{3})^3 \equiv 4^3 \equiv 64  \pmod {11} $

$ 5^{-1} \equiv 9 \pmod {11} $

(b) Here 23 is prime, and does not divide 9, and so

$ 9^{-1} \equiv 9^{21} \pmod {23} $

Using $9^7 \equiv 4782969 \equiv 4 \pmod {23}$, we have

$ 9^{-1} \equiv (9^{7})^3 \equiv 64 \pmod {23} $

$ 9^{-1} \equiv 18 \pmod {23} $

(c) Here 37 is prime, and does not divide 2, and so

$ 2^{-1} \equiv 2^{35} \pmod {37} $

Using $2^7 \equiv 128 \equiv 17 \pmod {37}$, we have

$ 2^{-1} \equiv (2^{7})^5 \equiv 17^5 \pmod {37} $

Using $17^2 \equiv 289 \equiv 30 \pmod {37}$, we have

$ 2^{-1} \equiv (17^2)^2 \times 17 \equiv 30^2 \times 17 \equiv 15300 \pmod {37} $

$ 2^{-1} \equiv 19 \pmod {37} $

(d) Here 41 is prime, and does not divide 5, and so

$ 5^{-1} \equiv 5^{39} \pmod {41}$

Using $5^{13} \equiv 1220703125 \equiv 39 \pmod {41}$, we have

$ 5^{-1} \equiv (5^{13})^3 \equiv 39^3 \equiv 59319 \pmod {41}$

$ 5^{-1} \equiv 33 \pmod {41} $

Exercise (4.1).1

Determine the least non-negative residue $x$ of the following congruences:

(a) $7^{101} ≡ x \pmod {11}$

(b) $2^{1976} ≡ x \pmod {13}$

(c) $5^{1961} ≡ x \pmod {7}$

(d) $3^{2013} ≡ x \pmod {23}$

(e) $26^{2013} ≡ x \pmod {23}$

We remind ourselves of Fermat's Little Theorem (FlT). For integer $a$ and prime $p$, where $p \not \mid a$, we have

$$ a^{p-1} \equiv 1 \pmod {p} $$

(a) Since 11 is prime, and doesn't divide 7, we can use the FlT.

$ 7^{10} \equiv 1 \pmod {11} $

$ (7^{10})^{10} \equiv 1^{10} \pmod {11}  $

$ 7^{100} \equiv 1 \pmod {11}  $

$ 7^{100} \times 7  \equiv 7 \pmod {11}  $

$ 7^{101}  \equiv 7 \pmod {11}  $

(b) Since 13 is prime, and doesn't divide 2. we can use the FlT.

$ 2^{12} \equiv 1 \pmod{13} $

$ (2^{12})^{164} \equiv 1 \pmod{13} $

$ 2^{1968} \times 2^8 \equiv 256 \equiv 9 \pmod{13} $

$ 2^{1976} \equiv  9 \pmod {13} $

(c) Since 7 is prime, and doesn't divide 5, we can use the FlT.

$ 5^{6} \equiv 1 \pmod 7 $

$ (5^{6})^{326} \equiv 1 \pmod 7 $

$ 5^{1956} \times 5^5 \equiv 3125 \equiv 3 \pmod 7 $

$ 5^{1961} \equiv 3 \pmod 7 $

(d) Since 23 is prime, and doesn't divide 3, we can use the FlT.

$ 3^{22} \equiv 1 \pmod {23} $

$ (3^{22})^{91} \equiv 1 \pmod {23} $

$ 3^{2002} \times 3^{11} \equiv 177147  \equiv 1 \pmod {23} $

$ 3^{2013} \equiv 1 \pmod {23} $

(d) We first note that

$ 26 \equiv 3 \pmod {23} $

$ 26^{2013} \equiv 3^{2013} \equiv 1 \pmod {23} $ using (d) above.

Exercise (3.5).15

Determine the prime decomposition of

$$ 8^8 − 1 = 16 777 215 $$

We have

$$ \begin{align} 16 777 215 & = (8^4-1)(8^4+1) \\ \\ & = (8^2-1)(8^2+1) \times 4097  \\ \\ & = 63 \times 65 \times 4097 \end{align} $$

We can factorise these separately

$ 63 = 3^2 \times 7 $

$ 65 = 5 \times 13 $

$ 4097 = 17 \times 241 $

And so

$$ 8^8 -1 = 3^2 \times 5 \times 7 \times 13 \times 17 \times 241 $$