So I am trying to work out how to find remainders in several different way.
I have a few very similar question,
1.) Find the remainder when $2^{47}$ is divided by 47
So i have a solution that says
$$2^{24} \equiv 2$$
$$2^{48} \equiv 4$$
$$2^{47} \equiv 2$$ Since $(2,47)=1$
and
2.)Find the remainder when $2^{32}$ is divided by $47$:
We have $$2^6 = 64 \equiv 17$$
$$2^{12} \equiv 17^2 = 289 \equiv 7$$
$$2^{24} \equiv 7^2=49 \equiv 2$$
$$2^8 \equiv 4*17=68 \equiv 21$$
$$2^{32}=2^{8}*2^{24} \equiv21*2 \equiv42$$
Okay so although i have some solutions here, Im not 100 percent sure how they derived this. For example on the second question, why have they started with $2^{6}$ before finding the remainder? Is there some steps missing or am I just missing the point?
Is this called something in particular? There are not many problems similar to and i do not know if it has a special name to search for.
P.S Please do not use fermat's little theorem, i want to understand this method, thanks 🙂
Best Answer
1) Find the remainder when $2^{47}$ is divided by $47$.
$2^1\equiv2\pmod{47}$
$2^2\equiv4\pmod{47}$
$2^4\equiv16\pmod{47}$
$2^8=(2^4)^2\equiv(16)^2=256\equiv21\pmod{47}$
$2^{16}=(2^8)^2\equiv(21)^2=441\equiv18\pmod{47}$
$2^{24}=2^8\cdot2^{16}\equiv21\cdot18=378\equiv2\pmod{47}$
$2^{48}\equiv2^2=4\pmod{47}$
$2*2^{47}\equiv2*2\pmod{47}$
Since $ca\equiv cb\pmod m$ and $(c,m)=1$ implies $a\equiv b\pmod m$, and since $(2,47)=1$, we can cancel the $2$:
$2^{47}\equiv2\pmod{47}$
2) Find the remainder when $2^{32}$ is divided by $47$.
From the previous solution:
$2^{24}\equiv2\pmod{47}$
$2^8\equiv21\pmod{47}$
$2^{32}=2^{24+8}=2^{24}\cdot2^8\equiv2\cdot21=42\pmod{47}$