Problem: What is the remainder when$$3^{57}+27$$ is divided by $28$ ?
Source: I'm pretty much interested in calculus (you can refer to my previous posts) but I have to prepare for a test where they even put up problems on elementary number theory. I got this problem from a practice set and it stumped me. I looked up for similar questions on the website and most of them include the use of $\mathrm{mod}$. I don't know what it is, and I haven't got time to understand it as I also have to deal with physics and chemistry at the same time. I have solved a very few problems of this kind (mainly divisibility) using mathematical induction and binomial theorem last year.
My try: When you got integral calculus embedded into your mind, how do you approach without using it? I have tried to develop a function: $$f(x) = \int(a^x+b)\mathrm{d}x$$ $$= \int{a^x}\mathrm{d}x + b\int \mathrm{d}x$$ $$= \frac{ a^{x+1}}{x+1} + bx + C$$ put limits $l_l = 0$ and $l_u = 57$ where $l_l$ and $l_u$ are lower and upper limits respectively.
But I have tried to solve it for no good. I can't think of a possible way, and my professor is unwilling to help me with it (duh!). I'm stuck. I have to perform better. So can you please give me an approach without using the $\mathrm{mod}$ function? All help appreciated!
$\endgroup$ 94 Answers
$\begingroup$You want remainder when $3^{57}+27 $ is divided by $28$. Note that $3^{57}=(3^3)^{19}$.
$$3^{57}+27=(3^3)^{19}+27=(28-1)^{19}+27={19\choose0}28^{19}-{19\choose 1}28^{18}\cdot\cdot\cdot\cdot\cdot+{19\choose18}28-{19\choose19}+27=28k-1+27=28k+26$$
When divided by $28$, $28k+26$ gives $26$ as remainder.
$\endgroup$ 2 $\begingroup$If you really want to avoid modular arithmetic, you can use binomial theorem:
Note that $3^{57} = 3^{3 \cdot 19} = 27 ^ {19} = (28-1)^{19}$. Now use the binomial theorem.
$$3^{57 } + 27 = (28-1)^{19} + 28-1 = 28k-2$$
So the remainder is $26$.
$\endgroup$ 0 $\begingroup$Here's a way to solve it without the "mod" function.
Note that any polynomial of the form $P(x)=x^{2n+1}+1$ has $x+1$ as a factor, since $P(-1)=(-1)^{2n+1}+1=0$. In particular,
$$x^{19}+1=(x+1)(x^{18}-x^{17}+x^{16}-\cdots-x+1)$$
Now let $x=3^3=27$. Then
$$3^{57}+27=(x^{19}+1)+26=(x+1)(x^{18}-x^{17}+\cdots+x^2-x+1)+26\\ =28(3^{18}-3^{17}+\cdots+3^2-3+1)+26$$
so the remainder is $26$.
Remark: What makes this work is that we have $28=3^k+1$ for a power $k$ (namely $k=3$) that divides $57$.
$\endgroup$ $\begingroup$Look.
When you divide $n$ by $d$ you have a remainder of $r$ if $n=q*d + r$.
That would also mean $n = (q+1)*d - (d-r)$. For all practical purposes, we can talk about a remainder being negative if it makes the math easy. What difference in the math can it make if we say $n=q*d + r; 0 \le r < d$ or $n = s*d - v; 0 \ge v > -d$?
So the remainder of $27$ divided by $28$ is $-1$. Let's assume we can say that.
Then $3^3 = 27$ and the remainder of $3^3$ is $-1$.
Now if the remainder of $n$ is $r$ then $n = q*d + r$ for some $q$. And $a*n = (aq)*d + a*r$. So if $n$ has $r$ as a remainder, then $a*n$ will have the same remainder as $a*r$.
By induction, $n^m$ will have the same remainder as $r^m$.
So the remainder of $3^{57} + 27= (3^3)^{19} + 27$ will have the same remainder as $(-1)^{19} - 1= -2$.
But we can't actually get away with telling a professor that a remainder is negative. That was just a secret between you and me. We need a positive remainder.
$-2$ will have the same remainder as $-2 + 28 = 26$. So the positive remainder is $26$.
$\endgroup$ 1
