Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Have you tried looking at the number mod 4? –  ՃՃՃ Nov 28 '12 at 3:43
    
It’s a good idea to make your question self-contained, rather than having essential parts only in the title. –  Brian M. Scott Nov 28 '12 at 3:49
add comment

5 Answers 5

up vote 7 down vote accepted

$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$.

share|improve this answer
    
How does 9 = 1 mod 4? –  Doug Smith Nov 28 '12 at 3:56
3  
How many times can you divide 9 by 4 and what is the remainder after doing that? –  Amzoti Nov 28 '12 at 3:59
2  
@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$. –  Brian M. Scott Nov 28 '12 at 4:22
    
@DougSmith $9 \neq 1 ~ \mathrm{mod} ~ 4$, however $9 \equiv 1 ~ \mathrm{mod} ~ 4$ (congruence) - it's important to distinguish them. –  Thomas Nov 28 '12 at 5:16
add comment

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.)

share|improve this answer
2  
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. –  Thomas Nov 28 '12 at 5:18
    
@Thomas: thanks for pointing this out. Just in case, GAP could do it with PowerModInt, e.g. PowerModInt(19,433,4); –  Alexander Konovalov Sep 3 '13 at 23:29
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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!

share|improve this answer
    
Do you mean $\mod 20$ or $\mod 4$? Also (FYI), you need to fix the math formatting in the second paragraph... (the powers) –  anorton Nov 28 '12 at 3:54
    
How did you get the 19 = -1? –  Doug Smith Nov 28 '12 at 4:00
    
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$. –  dirty derwin Nov 28 '12 at 8:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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