Menu Close

Find-the-remainder-if-2-2006-is-divided-by-17-

Tinku Tara 0 Comments
Pin




Question Number 21874 by tawa tawa last updated on 05/Oct/17
Find the remainder if 2^(2006) is divided by 17
$$\mathrm{Find}\:\mathrm{the}\:\mathrm{remainder}\:\mathrm{if}\:\:\:\mathrm{2}^{\mathrm{2006}} \:\mathrm{is}\:\mathrm{divided}\:\mathrm{by}\:\:\mathrm{17} \\ $$
Answered by mrW1 last updated on 06/Oct/17
2^(2006) =2^2 ×2^(2004) =4×(2^4 )^(501) =4×(16)^(501) =4×(17−1)^(501) mod 17=−4=13 ⇒remainder =13
$$\mathrm{2}^{\mathrm{2006}} =\mathrm{2}^{\mathrm{2}} ×\mathrm{2}^{\mathrm{2004}} =\mathrm{4}×\left(\mathrm{2}^{\mathrm{4}} \right)^{\mathrm{501}} =\mathrm{4}×\left(\mathrm{16}\right)^{\mathrm{501}} \\ $$$$=\mathrm{4}×\left(\mathrm{17}−\mathrm{1}\right)^{\mathrm{501}} \:\mathrm{mod}\:\mathrm{17}=−\mathrm{4}=\mathrm{13} \\ $$$$\Rightarrow\mathrm{remainder}\:=\mathrm{13} \\ $$
Commented by tawa tawa last updated on 06/Oct/17
God bless you sir
$$\mathrm{God}\:\mathrm{bless}\:\mathrm{you}\:\mathrm{sir} \\ $$
Answered by Tinkutara last updated on 06/Oct/17
By Fermat′s theorem, 2^(17−1) ≡1(mod 17) 2^(16) ≡1(mod 17) 2^(2000) ≡1(mod 17) 2^(2006) ≡64(mod 17)≡13(mod 17)
$$\mathrm{By}\:\mathrm{Fermat}'\mathrm{s}\:\mathrm{theorem}, \\ $$$$\mathrm{2}^{\mathrm{17}−\mathrm{1}} \equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{17}\right) \\ $$$$\mathrm{2}^{\mathrm{16}} \equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{17}\right) \\ $$$$\mathrm{2}^{\mathrm{2000}} \equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{17}\right) \\ $$$$\mathrm{2}^{\mathrm{2006}} \equiv\mathrm{64}\left(\mathrm{mod}\:\mathrm{17}\right)\equiv\mathrm{13}\left(\mathrm{mod}\:\mathrm{17}\right) \\ $$
Commented by tawa tawa last updated on 06/Oct/17
God bless you sir
$$\mathrm{God}\:\mathrm{bless}\:\mathrm{you}\:\mathrm{sir} \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *