Question Number 221271 by gregori last updated on 29/May/25
$$\:\:{Find}\:{the}\:{remainder}\:{when}\:{x}^{\mathrm{100}} \: \\ $$$$\:\:{is}\:{divided}\:{by}\:\left({x}^{\mathrm{2}} +{x}+\mathrm{1}\right) \\ $$
Answered by A5T last updated on 29/May/25
$$\mathrm{x}^{\mathrm{2}} \equiv\left(−\mathrm{1}−\mathrm{x}\right)\left(\mathrm{mod}\:\:\mathrm{x}^{\mathrm{2}} +\mathrm{x}+\mathrm{1}\right) \\ $$$$\Rightarrow\mathrm{x}^{\mathrm{4}} \equiv\mathrm{x}^{\mathrm{2}} +\mathrm{2x}+\mathrm{1}\equiv\mathrm{x}\left(\mathrm{mod}\:\mathrm{x}^{\mathrm{2}} +\mathrm{x}+\mathrm{1}\right) \\ $$$$\Rightarrow\mathrm{x}^{\mathrm{5}} \equiv\mathrm{x}^{\mathrm{2}} \left(\mathrm{mod}\:\mathrm{x}^{\mathrm{2}} +\mathrm{x}+\mathrm{1}\right) \\ $$$$\Rightarrow\mathrm{x}^{\mathrm{100}} =\left(\mathrm{x}^{\mathrm{4}} \right)^{\mathrm{25}} \equiv\mathrm{x}^{\mathrm{25}} =\left(\mathrm{x}^{\mathrm{5}} \right)^{\mathrm{5}} \equiv\left(\mathrm{x}^{\mathrm{2}} \right)^{\mathrm{5}} =\left(\mathrm{x}^{\mathrm{5}} \right)^{\mathrm{2}} \\ $$$$\Rightarrow\mathrm{x}^{\mathrm{100}} \equiv\mathrm{x}^{\mathrm{4}} \equiv\mathrm{x}\left(\mathrm{mod}\:\mathrm{x}^{\mathrm{2}} +\mathrm{x}+\mathrm{1}\right) \\ $$