Question

a) Show that$2^{340}=1(mod11)$by Fermat’s little theorem and nothing that.

b) Show that $2^{340}=1(mod31)$using the fact that $2^{340}={\left(2^5\right)}^{68}={32}^{68}$

c) Conclude from parts (a) and (b) thatlocalid="1668659996449" $2^{340}\equiv 1(mod341)$

Short answer

It’s concluded that$2^{340}\equiv 1(mod341)$

Step-by-step solution

Step 1

a) By Fermat’s little theorem, $2^{340}\equiv 1(mod11)$.so, raising it to the power$34$, we obtain localid="1668660037657" ${\left(2^{10}\right)}^{34}\equiv 1\equiv 1^{34}(mod111)$

localid="1668660047205" $2^{340}\equiv {\left(2^{10}\right)}^{34}\equiv 1^{34}\equiv 1(mod11)$

b) Sincelocalid="1668659951368" $32=1(mod31)\text{,thus}{32}^{68}\equiv {\left(2^5\right)}^{68}\equiv (1{)}^{68}\equiv 1(mod31)$

localid="1668659916301" $2^{340}\equiv {\left(2^5\right)}^{68}={32}^{68}\equiv (1{)}^{68}\equiv 1(mod31)$

Step 2

c) $11\mid \left(2^{340}-1\right)\Rightarrow \left(2^{340}-1\right)=11p$Where $\gcd (11,p)=1$so from (i) and (ii) role="math" localid="1668659653558" $11p=31q\Rightarrow 31\mid 11p\gcd$since $(31,11)=1\Rightarrow 31\mid p\Rightarrow p=31q_1\dots$using (iii) In (i) $\left(2^{340}-1\right)=1\mathrm{p}=11\ast 31{\mathrm{q}}_1=341{\mathrm{q}}_1$

$\therefore 341\mid \left(2^{340}-1\right)$

$\begin{array}{r}{2}^{340}\equiv 1(mod11)\Rightarrow 11\left|\left(2^{340}-1\right),2^{340}\equiv 1(mod31)\Rightarrow 31\right|\left(2^{300}-1\right)\\ \therefore 341\mid \left(2^{340}-1\right)\end{array}$

Hence , $2^{340}\equiv 1(mod341)$