Question Number 2699 by abcd last updated on 25/Nov/15
$$\mathrm{Find}\:\mathrm{the}\:\mathrm{remainder}\:\mathrm{when} \\ $$$$\mathrm{3}^{\mathrm{215}} \:\mathrm{is}\:\mathrm{divided}\:\mathrm{by}\:\mathrm{43}. \\ $$
Answered by RasheedAhmad last updated on 25/Nov/15
![Since (3,43)=1 and 43 is prime according to Fermat′s theorm 3^(43−1) ≡1(mod 43) 3^(43) ≡3(mod 43) (3^(43) )^5 ≡(3)^5 (mod 43) 3^(215) ≡243−215(mod 43) [215=43×5] 3^(215) ≡28 Statement of Fermat′s theorm If p is a prime number and (a,p)=1 then a^(p−1) ≡1(mod p](https://www.tinkutara.com/question/Q2717.png)
$$ \\ $$$${Since}\:\left(\mathrm{3},\mathrm{43}\right)=\mathrm{1}\:{and}\:\mathrm{43}\:{is}\:{prime} \\ $$$${according}\:{to}\:{Fermat}'{s}\:{theorm} \\ $$$$\:\:\:\:\:\:\:\mathrm{3}^{\mathrm{43}−\mathrm{1}} \equiv\mathrm{1}\left({mod}\:\mathrm{43}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\mathrm{3}^{\mathrm{43}} \equiv\mathrm{3}\left({mod}\:\mathrm{43}\right) \\ $$$$\:\:\:\left(\mathrm{3}^{\mathrm{43}} \right)^{\mathrm{5}} \equiv\left(\mathrm{3}\right)^{\mathrm{5}} \left({mod}\:\mathrm{43}\right) \\ $$$$\:\:\:\:\:\:\mathrm{3}^{\mathrm{215}} \equiv\mathrm{243}−\mathrm{215}\left({mod}\:\mathrm{43}\right)\:\left[\mathrm{215}=\mathrm{43}×\mathrm{5}\right] \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{3}^{\mathrm{215}} \equiv\mathrm{28} \\ $$$${Statement}\:{of}\:{Fermat}'{s}\:{theorm} \\ $$$${If}\:\:{p}\:\:{is}\:{a}\:{prime}\:{number}\:{and} \\ $$$$\left({a},{p}\right)=\mathrm{1}\:{then} \\ $$$$\:\:\:\:\:\:\:\:\:{a}^{{p}−\mathrm{1}} \equiv\mathrm{1}\left({mod}\:{p}\right. \\ $$