15
$\begingroup$

How would one calculate $6000006000600000600006006000000003 \times 3 \pmod{18}$?

The number is too big to use a calculator to manipulate the number into something I can work with, and Fermat's theorem doesn't apply since $18$ isn't prime, so I'm stumped as to what to do.

$\endgroup$
5
  • 3
    $\begingroup$ The other answers explain strategies for doing that calculation. If you just wanted the solution, you could use WolframAlpha. $\endgroup$
    – fintelia
    Dec 13, 2016 at 23:50
  • 1
    $\begingroup$ …or any other calculator that supports larger numbers. Linux/Unix examples: echo '6000006000600000600006006000000003 * 3 % 18' | bc or python -c 'print 6000006000600000600006006000000003 * 3 % 18' $\endgroup$
    – rob mayoff
    Dec 14, 2016 at 15:22
  • 3
    $\begingroup$ It would take less than a minute to do the multiplication and division by hand on paper; why do you need to use a calculator? $\endgroup$
    – Eric Lippert
    Dec 14, 2016 at 19:12
  • $\begingroup$ Cause mathematicians and students are bad with numbers, afterall 52 is a prime number, isn't it ? (To quote a mathematician once holding a talk about primes). There is a reason that the advent of automatic calculators brough civilization ahead so far. And if you need to repeat it for another number, then maybe an automatic calculator isn't so bad afterall :P? $\endgroup$
    – HopefullyHelpful
    Dec 15, 2016 at 14:07
  • $\begingroup$ Answer is obviously to get a bigger calculator ;) $\endgroup$
    – Bradley Thomas
    Dec 15, 2016 at 15:01

9 Answers 9

Reset to default
57
$\begingroup$

The digit sum of $600\ldots 03$ is a multiple of $3$, so that monster is a multiple of $3$. When multiplying by $3$, the result is a multiple of $9$. However, the result is odd, so modulo $18$, the result is $9$ (not $0$).

$\endgroup$
7
  • 3
    $\begingroup$ The trick with the sum of digits works for $9$ as well; a number is divisible by $9 \iff$ the sum of the digits is a multiple of $9$. $\endgroup$
    – Ovi
    Dec 13, 2016 at 6:07
  • 6
    $\begingroup$ @Ovi: vadim's method means that you don't have to count all those 6's. $\endgroup$
    – TonyK
    Dec 13, 2016 at 12:48
  • 3
    $\begingroup$ Why is it that my ten-second off-the-cuff answers get a bunch of upvotes, but not my detailed thoughtful solutions? $\endgroup$
    – vadim123
    Dec 14, 2016 at 0:13
  • 4
    $\begingroup$ @vadim123 Because most people prefer tricks and shortcuts for solving school problems over learning the base, understanding and doing methodical work...? (slipping off-topic) $\endgroup$
    – CiaPan
    Dec 14, 2016 at 11:51
  • $\begingroup$ @vadim123, I know; it's just unfair. :) Really, though, this is a good answer. For detailed thoughtful solutions, I think it helps to include a very short summary at the top (the size of this entire answer) which is worth upvoting by itself. (Yes, off-topic....) $\endgroup$
    – Wildcard
    Dec 14, 2016 at 17:52
51
$\begingroup$

Too long for the calculator, so use pencil and paper?

$$\quad\quad\quad6000006000600000600006006000000003$$ $$=3\times2000002000200000200002002000000001$$ $$=3\times(2\times1000001000100000100001001000000000+1)$$ $$\quad\quad=6\times1000001000100000100001001000000000+3,$$ so $$6000006000600000600006006000000003\times3$$ $$=(6\times1000001000100000100001001000000000+3)\times3$$ $$=18\times1000001000100000100001001000000000+9$$ $$\equiv9\pmod{18}.$$

$\endgroup$
17
$\begingroup$

For the specific case, all the $6$s multiplied by $3$ give $18$ because there are enough zeros to make sure the carry isn't a problem. Since $18 \equiv 0 \pmod {18}$ we can ignore those, so all we care about the the $3 \times 3 =9$ Because the big number is so special, I believe this is the expected solution. If the big number weren't so special, doing the calculation on paper with long division is not so hard.

$\endgroup$
3
  • $\begingroup$ Yes! It's always best to stand back and look at the whole problem as presented before diving in to calculations. $\endgroup$
    – Spencer
    Dec 13, 2016 at 11:49
  • 1
    $\begingroup$ Even if the number was 6666663 you could ignore the 6's in the way you describe. The presence of X000 and X0 does not mean that 600 does not divide 6. $\endgroup$
    – Taemyr
    Dec 14, 2016 at 10:42
  • $\begingroup$ @Taemyr: that is true, but the zeros make it easier to see. $\endgroup$
    – Ross Millikan
    Dec 14, 2016 at 14:49
12
$\begingroup$

Let $B = 600000600060000060000600600000000$ (your big number minus $3$). Now the original problem is $3(B+3) \pmod {18}$, or $3B+9 \pmod {18}$

$B$ is divisible by $2$ (last digit is zero) and by $9$ (the sum of the digits is divisible by $9$). Therefore $B$ is divisible by $18$, so your original problem reduces to $3 \cdot 0 + 9 \pmod {18}$, or $ 9 \pmod {18}.$

$\endgroup$
10
$\begingroup$

$$6000006000600000600006006000000003\times3=18000018001800001800018018000000009$$ so why worry ?

$\endgroup$
6
  • $\begingroup$ @ANYBODY Can anybody explain or at least suggest why this answer got a downvote???! $\endgroup$
    – CiaPan
    Dec 13, 2016 at 18:54
  • $\begingroup$ @CiaPan: probably someone thought it was a fake... Thanks for the solidarity :) $\endgroup$
    – user65203
    Dec 13, 2016 at 19:33
  • 6
    $\begingroup$ Well, it doesn't explain how we can figure what $18000018001800001800018018000000009 \mod 18$ is, I suppose. Although it's not hard. But the then the original question wasn't hard... So even though it's obvious to us it might not be to the op? I dunno. Lot's of people downvote for lots of stupid reasons. $\endgroup$
    – fleablood
    Dec 13, 2016 at 20:37
  • $\begingroup$ @fleablood IMVHO it pretty clearly shows that everything above the second order of magnitude (that is above 10) is divisible by $18$ hence the remainder is $9$. One must not understand completely the notion of a remainder and the $\mathrm{mod}$ operator to think the way you reconstructed; so I stick rather to thinking it was someone of those 'downvoting for lots of stupid reasons'... $\endgroup$
    – CiaPan
    Dec 14, 2016 at 8:53
  • 1
    $\begingroup$ Well, what's intuitively ovbvious to some (180000180001800000018000000x has remainder x because 1800001800018000000180000000 is obviously divisible by 18) isn't obvious to others. And if wasn't obvious in the op i'm not sure its really any more in this answer. Although, maybe if it isn't obvious we shouldn't be spelling it out either. Doesn't deserve a downvote but then it no longer has so many. $\endgroup$
    – fleablood
    Dec 14, 2016 at 18:59
10
$\begingroup$

Hint $\bmod \color{#c00}{18}\!:\,\ \color{#c00}3(3\!+\!\color{#c00}6n)\equiv 9$

Or $\ \color{#c00}3(k\!+\!6n)\bmod 18 = \color{#c00}3(k\! +\! 6n\bmod 6) = 3(k\bmod 6)$

employing $\ \color{#c00}ab\bmod \color{#c00}ac = \color{#c00}a(b\bmod c) = $ $\!\bmod\!$ Distributive Law to factor $\,\color{#c00}{a=3}\,$ out of the mod.

$\endgroup$
8
$\begingroup$

We can use the Chinese remainder theorem. Let $(\text{Big Number}) = x$. Notice that $x \equiv 0 \pmod{9}$ since each factor is divisible by $3$, and further $x \equiv 1 \pmod{2}$ since it is a product of two odd numbers. We have $\gcd(2, 9) = 1$ and $18 = 2 \times 9$, so the theorem guarantees a solution $\pmod{18}$. There even exists a method of constructing it explicitly.

Edit: Vadim's answer is pretty good in this case. The above method will give you a way of attacking similar problems if it isn't as obvious.

$\endgroup$
5
$\begingroup$

You imply calculators would be an acceptable means, were it not for the limit on number of digits. How about:enter image description here

$\endgroup$
0
$\begingroup$

I looked at it. On the left side we have six times stuff plus six times stuff plus six times stuff plus three more sixes times stuff plus 3, multiplied by 3.

The result of the multiplication is lots of 18's times stuff, plus 9.

Modulo 18 is 9.

Why would you need a calculator, or computer software, or any big theorems?

$\endgroup$

You must log in to answer this question.

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