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 :)
$\endgroup$ 54 Answers
$\begingroup$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}$
$\endgroup$ $\begingroup$Fermat's Little Theorem gives you the answer at once: since $\;47\; $ is prime, we get
$$2^{47}=2\pmod {47}$$
which means that the wanted residue is $\;2\;$ .
$\endgroup$ 8 $\begingroup$I don't know if this constitutes a full answer, but I cannot leave comments yet.
Notice that $2^5 = 32 < 47$, and $2^6 = 64 > 47$. That is, we are starting with the first power of $2$ that is greater than the number we're dividing by. If the number were less, the remainder would simply be the number we started with.
As for a term, try looking at Modular Arithmetic.
$\endgroup$ 5 $\begingroup$The following method is called the Right-to-Left Binary Method on Wikipedia. Generally, it reduces the number of operations needed for modular exponentiation. The method works by considering the exponent in binary, where multiplying the exponent by two (shifting left in binary) corresponds to squaring, and adding one to the exponent corresponds to multiplying by the base.
$47=101111_\text{two}$ so we get $$ \begin{align} 2^{0_\text{two}}&\equiv1\pmod{47}\\ 2^{1_\text{two}}&\equiv2\pmod{47}\tag{square and multiply by 2}\\ 2^{10_\text{two}}&\equiv4\pmod{47}\tag{square}\\ 2^{101_\text{two}}&\equiv32\pmod{47}\tag{square and multiply by 2}\\ 2^{1011_\text{two}}&\equiv27\pmod{47}\tag{square and multiply by 2}\\ 2^{10111_\text{two}}&\equiv1\pmod{47}\tag{square and multiply by 2}\\ 2^{101111_\text{two}}&\equiv2\pmod{47}\tag{square and multiply by 2}\\ \end{align} $$ $32=100000_\text{two}$ so we get $$ \begin{align} 2^{0_\text{two}}&\equiv1\pmod{47}\\ 2^{1_\text{two}}&\equiv2\pmod{47}\tag{square and multiply by 2}\\ 2^{10_\text{two}}&\equiv4\pmod{47}\tag{square}\\ 2^{100_\text{two}}&\equiv16\pmod{47}\tag{square}\\ 2^{1000_\text{two}}&\equiv21\pmod{47}\tag{square}\\ 2^{10000_\text{two}}&\equiv18\pmod{47}\tag{square}\\ 2^{100000_\text{two}}&\equiv42\pmod{47}\tag{square}\\ \end{align} $$
$\endgroup$ 2
