Let \(a^{2c} \text{ mod } n = (a^c)^2 \text{ mod } n\) and \(a^{2c+1}\text{…
2019
Let \(a^{2c} \text{ mod } n = (a^c)^2 \text{ mod } n\) and \(a^{2c+1}\text{ mod } n= a \cdot (a^c)^2\text{ mod }n\). For \(𝑎=7, 𝑏=17 \ and \ 𝑛=561\), What is the value of \(a^b( \text{mod } n)\)?
- A.
160
- B.
166
- C.
157
- D.
67
Attempted by 60 students.
Show answer & explanation
Correct answer: A
Solution: Compute 7^17 (mod 561) by repeated squaring.
Key idea: express the exponent 17 in binary and use modular squaring to build up powers.
7^1 ≡ 7 (mod 561)
7^2 = 7^1·7^1 = 49 ≡ 49 (mod 561)
7^4 = 49^2 = 2401 ≡ 157 (mod 561) because 2401 − 4·561 = 157
7^8 = 157^2 = 24649 ≡ 526 (mod 561) because 24649 − 43·561 = 526
7^16 = 526^2 = 276676 ≡ 103 (mod 561) because 276676 − 493·561 = 103
Since 17 = 16 + 1, combine 7^16 and 7^1:
7^17 ≡ 7^16 · 7^1 ≡ 103 · 7 = 721 ≡ 160 (mod 561)
Answer: 160.
A video solution is available for this question — log in and enroll to watch it.