UGC NET CSE | December 2019 | Part 2 | Question: 35

Question

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 $a=7$, $b=17$ and $n=561$, What is the value of $a^b( \text{mod } n)$?

• A. $160$
• B. $166$
• C. $157$
• D. $67$

Comments

https://www.quora.com/How-do-I-solve-2-35-mod-561

---

@`JEET

You can check this at first.

 

Here,

$\begin{align} 7^{17}\mod 561 &\equiv 7\left(\left( 7^4 \right)^2\right)^2 \mod 561\\ &\equiv 7\left(\left( 2401 \right)^2\right)^2\\ &\equiv 7\left(\left( 157 \right)^2\right)^2\\ &\equiv 7\left(24649\right)^2\\ &\equiv  7\left(-35\right)^2; [\because 24649 \mod 561 \equiv 526 \equiv -35]\\ &\equiv 7(1225)\\  &\equiv 7(103) \\ &\equiv 721 \\ &\equiv 160 \end{align}$

---

👍👍👍👍

Answer 1

$\underline{\textbf{Answer:}\Rightarrow}\;1)\;160$

$\underline{\textbf{Explanation:}\Rightarrow}$

$\textbf{Given:}\;7^{17}\;\text{mod}\;561$ 

$\mathbf{561}$ can be factorised into $3\times 17\times 11$.

Now,

$7^{17} = 3\times \mathbf{q_1}+1\\7^{17} = 17\times \mathbf{q_2}+7\\7^{17}= 11\times \mathbf{q_3} - 5\;\;\;\text{[$\therefore\;$Positive remainder = 6]}$

Now choose among the all options which when divided by $\mathbf{3,17,11}$ gives the remainder $\mathbf{1,7,6}$.

$\therefore$ Only option $(1)$ satisfies.

---

$\textbf{Calculating remainders using Euler's Theorem:}$

$\mathrm{\begin{align} 7^{17} \;\text{mod}\;11 &= 7^{10}\times 7^7 \;\text{mod} \;11 \\&= 1 \times 7^7 \;\;\text{mod} \;\;11 \\&= 7^3 \times 7^3 \times 7\;\;\text{mod} \;\;11\\&= 343\;\;\text{mod}\;\;11\times 343\;\;\text{mod}\;\;11\times 7\;\;\text{mod}\;\;11 \\&= 2\times 2\times7\;\;\text{mod} \;\;11 \\&= 28\;\;\text{mod}\;\;11 \\&= 6\;\;\text{mod} \;\;11 \\&= \color{magenta}{\enclose{circle}{-5}} \; \;\text{mod} \;\;11 \end{align}}$

Or, remainder $=\color{magenta}{\enclose{circle}{6}}\;\;\;\mathrm{[\because 6+5=11]}$

Similarly, the other two remainders can be calculated.

$\therefore\;\textbf{1)}$ is the right option.

$\textbf{For extended Reading, Refer:}$

http://mathonline.wikidot.com/examples-of-finding-remainders-of-large-numbers

Comments

https://www.quora.com/How-do-I-solve-2-35-mod-561

---

Please describe whole process

Answer 2

• 7¹⁷mod561

• ≡7((7⁴)²)²)mod561

• ≡7((2401)²)²)mod561

• ≡7((157)²)²)mod561 [2401 mod 561 ≡ 157]

• ≡7(24649)²mod561

• ≡7(−35)² [∵24649mod561 ≡ 526 ≡ −35]

• ≡7(1225)mod561

• ≡7(103)mod561

• ≡721mod561

• ≡160