3
$\begingroup$

We went over this in class awhile ago, but I can't seem to figure out how to solve it. Obviously you can do it exhaustively with a supercomputer, but that doesn't seem practical when I know there's a simplistic way to solve it.

$\endgroup$
2
  • 2
    $\begingroup$ Have you tried looking at the number mod 4? $\endgroup$
    – ՃՃՃ
    Nov 28, 2012 at 3:43
  • $\begingroup$ It’s a good idea to make your question self-contained, rather than having essential parts only in the title. $\endgroup$ Nov 28, 2012 at 3:49

5 Answers 5

7
$\begingroup$

$9\equiv 1\pmod4$, so every power of $9$ is also congruent to $1\bmod 4$; in particular, $9^{32}\equiv 1\pmod 4$. $19\equiv -1\pmod 4$, so $19^{433}\equiv(-1)^{433}\equiv -1\pmod 4$, since $(-1)^{433}=-1$. Thus, $$9^{32}+19^{433}\equiv 1+(-1)\equiv 0\pmod 4\;,$$ meaning that $9^{32}+19^{433}$ is divisible by $4$. The smallest non-negative $m$ such that $9^{32}+19^{433}+m$ is divisible by $4$ is therefore $0$, and the smallest positive $m$ is $4$.

$\endgroup$
4
  • $\begingroup$ How does 9 = 1 mod 4? $\endgroup$
    – Doug Smith
    Nov 28, 2012 at 3:56
  • 3
    $\begingroup$ How many times can you divide 9 by 4 and what is the remainder after doing that? $\endgroup$
    – Amzoti
    Nov 28, 2012 at 3:59
  • 2
    $\begingroup$ @Doug: To verify that $9\equiv 1\pmod 4$, recall that by definition $a\equiv b\pmod m$ if and only if $m\mid a-b$. Certainly $4\mid 8=9-1$, so $9\equiv 1\pmod 4$. To calculate it from scratch, just divide $9$ by $4$: you get a quotient of $2$ and a remainder of $1$, meaning that $9=2\cdot 4+1$. Thus, $9$ and $1$ differ by a multiple of $4$, so they must be congruent mod $4$. More generally, if $a$ and $b$ have the same remainder when divided by $m$, they must be congruent mod $m$. $\endgroup$ Nov 28, 2012 at 4:22
  • $\begingroup$ @DougSmith $9 \neq 1 ~ \mathrm{mod} ~ 4$, however $9 \equiv 1 ~ \mathrm{mod} ~ 4$ (congruence) - it's important to distinguish them. $\endgroup$
    – Thomas
    Nov 28, 2012 at 5:16
4
$\begingroup$

Since you've gotten the mathematical answer already, I'd like to point out that it's not a particularly hard problem computationally (and certainly doesn't require a supercomputer). It can be computed in GAP as follows:

gap> 9^32+19^433;
501544200119392562625247277746089908092336003464306403005859888420683628454522\
294504197711028243108230887275382154581016491417414644491962851915431414455652\
288045095893781599660030753306640524923972275437754069448537906581323068453513\
432352483965776742110824103821944465300751947471969610305958014477196847328310\
211743932024655151477385264075258820700008154477693517186089623494722993687602\
585620203537058139081722096639662034404319726334084194425480243598759870559077\
000920199390664370931533991434513332012987998517097840035144875728681773054413\
22534740
gap> last mod 4;
0

Since every 4-th integer is divisible by 4, and $9^{32}+19^{433}$ is divisible by 4, we can deduce that $9^{32}+19^{433}+m$ is divisible by $4$ if and only if $m$ is divisible by $4$.

This was computed on my home computer, and took less than a microsecond to compute (it took me significantly longer to type 9^32+19^433;). You could similarly compute it using a zillion other computer algebra systems, or even Wolfram|Alpha.

(Note: while I'm not advocating solely relying on computers to solve mathematical problems, I think it's useful to know what the computer will be able to do.)

$\endgroup$
2
  • 2
    $\begingroup$ You could've also performed modular exponentiation (taking the result modulo $4$ at each iteration) which is more efficient in the general case, though for such a small case it's not important. Computational results can sometimes give insight into a problem. $\endgroup$
    – Thomas
    Nov 28, 2012 at 5:18
  • $\begingroup$ @Thomas: thanks for pointing this out. Just in case, GAP could do it with PowerModInt, e.g. PowerModInt(19,433,4); $\endgroup$ Sep 3, 2013 at 23:29
2
$\begingroup$

Hint $\rm\,\ mod\ n\!:\ (an\!+\!1)^j + (bn\!-\!1)^{2k+1}\equiv 1^j + (-1)^{2k+1}\equiv 1-1\equiv 0$

$\endgroup$
1
$\begingroup$

I presume “the smallest number m” here is intended in the sense of “the smallest non-negative integer m”. Assuming this, I’d suggest:

  • first, show that for any number n, “what’s the smallest number m such that n + m is divisible by 4” is equivalent to a slightly different question about n, in a more standard form.

  • secondly, use techniques about powers (which you’ve hopefully seen) to answer that question.

$\endgroup$
1
$\begingroup$

It seems you can do this simply by modding out: $$ 9^{32}\equiv 81^{16}\equiv 1^{16}\equiv 1 \mod 4 $$ $$ 19^{433}\equiv (-1)^{433}\equiv -1 \mod 4 $$

Adding these, we see $9^{32}+19^{433}$ is divisible by four, so $m=0$ is valid. I assume you mean the smallest absolute value, as you can just make negative multiples of four. Hope that's what you were looking for!

$\endgroup$
3
  • $\begingroup$ Do you mean $\mod 20$ or $\mod 4$? Also (FYI), you need to fix the math formatting in the second paragraph... (the powers) $\endgroup$
    – apnorton
    Nov 28, 2012 at 3:54
  • $\begingroup$ How did you get the 19 = -1? $\endgroup$
    – Doug Smith
    Nov 28, 2012 at 4:00
  • $\begingroup$ Oops. I have no clue how how a got 20. Luckily, it works, and I'll fix that now. @ Doug, $19\equiv 3\equiv -1$ since modular arithmetic can easily be applied in negative numbers, and it is clear $19-5\cdot 4=-1$. $\endgroup$
    – cderwin
    Nov 28, 2012 at 8:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .