0
$\begingroup$

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$
  • 2
    $\begingroup$ $$3^3\equiv27\equiv-1 (mod28)$$ so $$\quad{3^{57}+27\equiv(3^3)^{19}+27\\\equiv(-1)^{19}+27\\\equiv(-1)+27\\\equiv26 (mod28) \to \\3^{57}+27=28Q+26}$$ $\endgroup$ – Khosrotash Oct 1 '17 at 17:59
  • $\begingroup$ So $3^{57}=(3^3)^{19}\equiv -1 \mod 28$ and $3^{57}+27\equiv 26\mod 28$ $\endgroup$ – Raffaele Oct 1 '17 at 17:59
  • $\begingroup$ Sirs/madams sir/madam, can you please read the description of the question? $\endgroup$ – YourAverageEuler Oct 1 '17 at 18:00
  • 2
    $\begingroup$ Your question is analogous to asking for a way to find antiderivatives without integration. Moreover, a vast chunk of elementary number theory revolves around the modulus function. $\endgroup$ – wjm Oct 1 '17 at 18:05
  • 2
    $\begingroup$ "So can you please give me an approach without using the mod function?" No. I can not and will not. Why should I. mod function is the way to do this and you are being tested on knowing the mod function. And, jeebus, integration of the continuum of real numbers to find a discreet remainder via divisibility of integers. You must realize that is fruitless. $\endgroup$ – fleablood Oct 1 '17 at 18:37
2
$\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$
  • $\begingroup$ Thank you, I'm such a noob at number theory that I couldn't even figure this out! $\endgroup$ – YourAverageEuler Oct 1 '17 at 18:12
  • 1
    $\begingroup$ @YourAverageEuler, my pleasure. $\endgroup$ – Vidyanshu Mishra Oct 1 '17 at 18:14
1
$\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$
1
$\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$
1
$\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$
  • $\begingroup$ Ha, Thanks @fleablood this approach is the most suitable to me as its an objective test and I won't have to show my work! $\endgroup$ – YourAverageEuler Oct 2 '17 at 3:46

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.