Menu Close

what-is-remainder-when-61-61-divided-by-1001-

Tinku Tara 0 Comments
Pin




Question Number 104139 by bobhans last updated on 19/Jul/20
what is remainder when 61^(61) divided by 1001
$${what}\:{is}\:{remainder}\:{when}\:\mathrm{61}^{\mathrm{61}} \:{divided} \\ $$$${by}\:\mathrm{1001} \\ $$
Commented by aurpeyz last updated on 19/Jul/20
how?
$$\mathrm{how}? \\ $$
Answered by floor(10²Eta[1]) last updated on 19/Jul/20
x≡61^(61) (mod 1001) 61^2 =3721≡718(mod 1001) 61^4 ≡718^2 =515524≡9(mod 1001) 61=4.15+1⇒61^(61) =(61^4 )^(15) .61≡9^(15) .61(mod1001)★ 9^4 =6561≡555(mod 1001) 9^5 ≡555.9=4995≡−10(mod 1001) 9^(15) =(9^5 )^3 ≡−1000≡1(mod 1001) ★9^(15) .61≡61(mod 1001) ⇒x=61
$$\mathrm{x}\equiv\mathrm{61}^{\mathrm{61}} \left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\mathrm{61}^{\mathrm{2}} =\mathrm{3721}\equiv\mathrm{718}\left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\mathrm{61}^{\mathrm{4}} \equiv\mathrm{718}^{\mathrm{2}} =\mathrm{515524}\equiv\mathrm{9}\left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\mathrm{61}=\mathrm{4}.\mathrm{15}+\mathrm{1}\Rightarrow\mathrm{61}^{\mathrm{61}} =\left(\mathrm{61}^{\mathrm{4}} \right)^{\mathrm{15}} .\mathrm{61}\equiv\mathrm{9}^{\mathrm{15}} .\mathrm{61}\left(\mathrm{mod1001}\right)\bigstar \\ $$$$\mathrm{9}^{\mathrm{4}} =\mathrm{6561}\equiv\mathrm{555}\left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\mathrm{9}^{\mathrm{5}} \equiv\mathrm{555}.\mathrm{9}=\mathrm{4995}\equiv−\mathrm{10}\left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\mathrm{9}^{\mathrm{15}} =\left(\mathrm{9}^{\mathrm{5}} \right)^{\mathrm{3}} \equiv−\mathrm{1000}\equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\bigstar\mathrm{9}^{\mathrm{15}} .\mathrm{61}\equiv\mathrm{61}\left(\mathrm{mod}\:\mathrm{1001}\right) \\ $$$$\Rightarrow\mathrm{x}=\mathrm{61} \\ $$
Answered by OlafThorendsen last updated on 19/Jul/20
61^(61) = 61.(61^2 )^(30) 61^(61) = 61.3721^(30) 61^(61) ≡ 61.718^(30) [1001] 61^(61) ≡ 61(718^2 )^(15) [1001] 61^(61) ≡ 61×(9)^(15) [1001] 61
$$\mathrm{61}^{\mathrm{61}} \:=\:\mathrm{61}.\left(\mathrm{61}^{\mathrm{2}} \right)^{\mathrm{30}} \\ $$$$\mathrm{61}^{\mathrm{61}} \:=\:\mathrm{61}.\mathrm{3721}^{\mathrm{30}} \\ $$$$\mathrm{61}^{\mathrm{61}} \:\equiv\:\mathrm{61}.\mathrm{718}^{\mathrm{30}} \:\left[\mathrm{1001}\right] \\ $$$$\mathrm{61}^{\mathrm{61}} \:\equiv\:\mathrm{61}\left(\mathrm{718}^{\mathrm{2}} \right)^{\mathrm{15}} \:\left[\mathrm{1001}\right] \\ $$$$\mathrm{61}^{\mathrm{61}} \:\equiv\:\mathrm{61}×\left(\mathrm{9}\right)^{\mathrm{15}} \:\left[\mathrm{1001}\right] \\ $$$$\mathrm{61} \\ $$$$ \\ $$

Pin

Leave a Reply

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