How to find the remainder of $\frac{2^{99}}{9}$?

Question

The question is solved in the book I read in a very odd way as,

$$\frac{2^{99}}{9} = \dfrac{{(2^{3})}^{33}}{2^3-(-1)}$$ Hence by remainder theorem the remainder is $-1$. In questions when remainder is negative than the number is subtracted from numbers like $2^3$ to get a positive number so the answer is $8-{-1}=9$.

I don't know which remainder theorem the book is talking of. I converted the question in mod notation as,

$$2^{99} \bmod 9 = (2^3)^{33} \bmod (2^3 - (-1))$$

But I don't think there is some formula for $a \bmod (c-d)$. Please tell me how to solve these type of questions.

Yes. I don't have the book now just remember a little bit from that. — user103816, Oct 09 '15 at 11:33
I guess the book is using some theorem in which the denominator is of type $N^x \bmod (N-a) = N-a$ IS there any such formula? — user103816, Oct 09 '15 at 11:37
@OriaGruber I didn't get your hint. I know that $33 \times 3 = 99$. — user103816, Oct 09 '15 at 11:43

score 6 · Answer 1 · answered Oct 09 '15 at 11:33

6

$$2^{99} \equiv (2^3)^{33} \equiv 8^{33} \equiv (-1)^{33} \equiv -1 \equiv 8 \pmod 9$$

answered Oct 09 '15 at 11:33

gammatester

18,827

Are you using binomial theorem in $8^{33}=(9-(-1))^{33})$? – user103816 Oct 09 '15 at 11:34
No, just $8\equiv -1 \pmod 9$ just the same as in the last step. – gammatester Oct 09 '15 at 11:35
But in the last power we don't have the exponent. – user103816 Oct 09 '15 at 11:38
In which last power? – gammatester Oct 09 '15 at 11:38
Ok, perhaps you are using the fact $8^{33}-(-1)^{33}=[8-(-1)](other terms)=9(other terms)$ so $8$ and $-1$ are congruent with respect to $9$. – user103816 Oct 09 '15 at 11:46
I guess you are thinking to complicated: $8=9-1$ and therefore $8 \equiv 9-1 \equiv 0 -1 \equiv -1 \pmod 9$ – gammatester Oct 09 '15 at 11:52
I just did not get how is $8^{33}≡(−1)^{33}$? I understand $8≡-1$ because $8-(-1)$ is divisible by $9$. – user103816 Oct 09 '15 at 11:58
For natural $n$ you have: If $a\equiv b\pmod c$ then $a^n\equiv b^n \pmod c$ – gammatester Oct 09 '15 at 12:01
And this would be true only when $a^n-b^n$ is divisible by $c$ or $a-b$ is divisible by $c$, i.e. $(a-b) \bmod c = 0$. – user103816 Oct 09 '15 at 12:03
(+1) I was about to add $$ \begin{align} 2^{99} &\equiv8^{33}\ &\equiv(-1)^{33}\ &\equiv-1\ &\equiv8\pmod{9} \end{align} $$ when I noticed it was just a vertical version of yours. – robjohn Oct 09 '15 at 12:06
@user103816: Yes of couse, if $a\equiv b \pmod c$ then $(a-b) \equiv 0 \pmod c$ – gammatester Oct 09 '15 at 12:06

skyking · Accepted Answer · 2015-10-09T12:20:20.710

3

The theorem referred to is probably the polynomial remainder theorem. That is that the remainder of $p(x)/(x-a)$ is $p(a)$. So with $p(x) = x^{33}$ and $a=-1$ we have that the remainder of the division will be $p(-1) = (-1)^{33}$. That is: $$p(x) = x^{33} = (x-(-1))q(x) + (-1)^{33} = (x-(-1))q(x) - 1$$

Inserting $x = 2^3$ into this results in

$$p(2^3) = (2^3-(-1))q(2^3) - 1 = 9q(2^3)-1$$

From this we can see that $2^{99} = 9q(2^3) - 1 = 9q(2^3)-9+8 = 9(q(2^3)-1) + 8$ and since $q$ is a polynomial with integer terms we have that $Q = q(2^3)-1$ is an integer so $2^{99} = 9Q + 8$

For proof of the polynomial remainder theorem let $p(x)$ be a polynomial and use euclid division with $x-a$ then we will get a result $q(x)$ and a remainder $r(x)$ of degree one less than $x-a$, that is r(x) is a constant expression $C$. Now the result of the division will be $$p(x) = q(x)(x-a) + r(x) = q(x)(x-a) + C$$.

Now substitute $x$ with $a$ and we get

$$p(a) = q(a)(a-a) + C = 0q(a) + C = C$$

edited Oct 09 '15 at 12:20

answered Oct 09 '15 at 11:48

skyking

16,654

Only answer so far to actually explain the quote the OP found in his book. – hmakholm left over Monica Oct 09 '15 at 11:50
Aren't Polynomial remainder theorem and Euclid division algorithm different? In polynomial division we subtract powers of $x$ and if the divisor's degree is higher than $2$, say divisor is $x^2+1$ then the remainder will be of type $ax+b$ which exclusively depends upon $x$. – user103816 Oct 09 '15 at 11:56
I also don't get how can the remainder be negative in numerical division, e.g. 33/5 gives remainder 3(i.e. 33-56) but if we do 33-(75) then we get (-2) as the remainder. But then why does it make sense? Why do 3 and -2 become congurent and help in simplifying calculations? – user103816 Oct 09 '15 at 12:09
but if $q(c)=0$ then $r(c)$ is actually the remainder but still the remainder of polynomial division. How can we show that if q(x) has a degree 1 in x then r(c)[which will obviously be a numeric constant] is same as would be the remainder of Euclid division? – user103816 Oct 09 '15 at 12:12
I know that. In our case the remainder of polynomial division a numeric constant. But why is this constant same as would be the remainder of actual Euclid division performed on actual numbers. BTW I could not understand which degree of denominator are you saying in Euclid division. – user103816 Oct 09 '15 at 12:19

score 2 · Answer 3 · answered Oct 09 '15 at 11:31

To solve questions like this, the usual approach is using $$\def\mod{\mathbin{\rm mod}} ab \mod n = (a \mod n)(b\mod n) \mod n $$ iteratively. Let's start. We have that $$ 2^{99} = 2^{4\cdot 24 + 3} = 8 \cdot 16^{24} $$ reducing modulo $9$, we have $$ 2^{99}\mod 9 = 8 \cdot 7^{24} \mod 9 $$ But $7^{24} = 49^{12}$, reducing again and continue in that way \begin{align*} 2^{99} \mod 9 &= 49^{12}\cdot 8 \mod 9\\ &= 4^{12} \cdot 8 \mod 9\\ &= 16^6 \cdot 8 \mod 9\\ &= 7^6 \cdot 8 \mod 9\\ &= 49^3 \cdot 8 \mod 9\\ &= 4^3 \cdot 8 \mod 9\\ &= 16^2 \cdot 2 \mod 9\\ &= 49 \cdot 2 \mod 9\\ &= 8. \end{align*}

score 0 · Answer 4 · answered Oct 09 '15 at 11:48

It could be that the book was using the geometric sum formula instead $$ \frac{1-x^{n+1}}{1-x}=1+x+x^2+\ldots+x^n. $$ In this way we get $$ A=\frac{1-(-2^3)^{33}}{1-(-2^3)}=1-2^3+2^6-\ldots+2^{32}\in\mathbb{N} $$ and $$ \frac{2^{99}}{9}=\frac{1-(-2^3)^{33}-1}{1-(-2^3)}=A-\frac{1}{9}. $$

How to find the remainder of $\frac{2^{99}}{9}$?

4 Answers4