3
$\begingroup$

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$
  • $\begingroup$ No!! it is 1!! sorry :) $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:18
  • $\begingroup$ The line "$12^{12}\equiv17^2=289\equiv7$" has a typo; that $12^{12}$ should read $2^{12}$; this line is obtained by squaring both sides of $2^6\equiv17$. Another typo one line below that, "$7^2=499$", that should be $49$. $\endgroup$ – bof Oct 25 '13 at 5:32
  • $\begingroup$ $\large 2\ ?$. Two ?. $\endgroup$ – Felix Marin Oct 25 '13 at 5:32
  • $\begingroup$ I have the sol as $2^{24} \equiv 7^2 = 499 \equiv 2$ and yes the 12 should be a 2! $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:40
  • $\begingroup$ is this meant to be 49? I was thinking that seems odd... $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:42
1
$\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}$

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this, i thought that may be the case but wasnt 100% sure. so for the line $$12^{12} \equiv 17^2 = 289 \equiv 7$$, how did they know that $12^{12} \equiv 17^2$? is there a way of working this out $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:24
  • $\begingroup$ On the previous step we showed that $12^6 \equiv 17$, and $12^{12} = (12^6)^2 \equiv 17^2 = 289$. The last part is the remainder of $289/47$, which is $7$. $\endgroup$ – Steve Oct 25 '13 at 5:41
  • $\begingroup$ okay great thanks! And is the 499 meant to be 49? Im confused as i have found this solution so is it an error? $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:48
  • $\begingroup$ Actually there are a few typos, some of which I've just propagated! Let me try to clear up what I previously wrote. We showed that $2^6 \equiv 17$ and $2^{12} = (2^6)^2 \equiv 17^2$. That $12$ should be a $2$, and the $499$ should be a $49$. I think one of the comments further up notes this as well. $\endgroup$ – Steve Oct 25 '13 at 5:52
  • $\begingroup$ I did edit this did it not change it? It is changed on my screen... Thanks though!! I was confused about the 49... $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:54
0
$\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\;$ .

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I just made the same mistake. Read the last line :-) $\endgroup$ – robjohn Oct 25 '13 at 5:20
  • 2
    $\begingroup$ (He asked specifically for "not Fermat's Little Theorem") $\endgroup$ – Dennis Meng Oct 25 '13 at 5:20
  • $\begingroup$ Thank you! I know about fermats little theorem but i wanted to use an alternative method as my exam may ask m to solve it without fermats.. Thank you though :) $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:20
  • $\begingroup$ Ha sorry guys my bad should have put it at the top. Many thanks though :) $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:21
  • $\begingroup$ No @DennisMeng, he wrote that in problem number two, not number one. $\endgroup$ – DonAntonio Oct 25 '13 at 5:21
0
$\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} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! I have not used this notation before does it mean the same thing as in my question sol? $\endgroup$ – Bernard.Mathews Oct 25 '13 at 5:46
  • $\begingroup$ @Bernard.Mathews: you mean base-two numerals? It is easier to see what is going on when doing modular exponentiation when the exponent is written in binary. $\endgroup$ – robjohn Oct 25 '13 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.