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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|improve this answer
How does 9 = 1 mod 4? – Doug Smith Nov 28 '12 at 3:56
How many times can you divide 9 by 4 and what is the remainder after doing that? – Amzoti Nov 28 '12 at 3:59
@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

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;
gap> last mod 4;

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|cite|improve this answer
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

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

share|cite|improve this answer

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|cite|improve this answer

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|cite|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) – apnorton 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$. – cderwin Nov 28 '12 at 8:20

Your Answer


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.