Answer to Question #250615 in Discrete Mathematics for Alina

Question

Solve the following:

(a) 123¹⁰⁰¹ (mod 101)

(b) 17¹²³ (mod 13)

Answer 1

Euler's Theorem states, For relatively prime integers a and n

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

$(a) \text{Here, a = 123, n = 101 and (123,101) = 1. Using Euler's Theorem,}\\123^{\phi(101)}\equiv 1(\mod 101)\\ 123^{100}\equiv 1(\mod 101)\\ 123^{1000}\equiv (123^{100})^{10} \equiv 1^{10}\equiv1(\mod 101)\\ 123^{1001}\equiv 123(\mod 101)\equiv 22(\mod 101) \\$

$(b) \text{Here, a = 17, n = 13 and (17,13) = 1. Using Euler's Theorem,}\\ 17^{\phi(13)} \equiv 1(\mod 13)\\ 17^{12} \equiv 1(\mod 13)\\ 17^{120} \equiv (17^{12})^{10}\equiv 1^{10}(\mod 13)\equiv 1(\mod13)\\ 17^{123} \equiv 17^{120}\cdot 17^{3}(\mod 13)\\ 17^{123} \equiv 17^{3}(\mod 13)\equiv 4^3(\mod 13) ~~[\text{Since} ~17\equiv4\mod13]\\ 17^{123} \equiv 12(\mod 13)$