/sci/ - Science & Math

its on of the unsolved mysteries of math. its the kind of thing math theorists spend their whole lives trying to solve

Yes, if a number is divisible by 9, then the sum of it's digits is divisible by 9 (easily proven). The sum of the digits is less than the number. So eventually you'll end up with 9.

>>4715520
Well, if it's easily proven for 9 in base 10, I'd assume it's also easily proven for B-1 in base B. Care to give a proof?

Also, what about the 3 thing? If the square root of B-1 is a whole number, does that mean that you'll always end up with a multiple of that square root, like you do with 3 in base 10? What about 3rd roots, etc.?

Yes, it's true for all bases. A consequence of Fermat's Little Theorem plus a bit of induction.

>>4715598
Huh? Work with me here.

>>4715598
> Fermat's little theorem.

No. You don't need that for this. It's almost immediately apparent once you learn basic modular arithmetic.

>>4715700
bump, I don't know what anyone's talking about

I was under the impression that is was true for any factor of (b-1).

>>4715700
Yes, that IS Fermat's Little Theorem...

>>4717989
You may be right but I don't understand. Doesn't that theorem only deal with primes? I don't see the connection anyway.

How does this work?

>>4718265
It doesn't. 39 x 39 is not 1521, not 1114.

>>4718265
It doesn't. 39 x 39 is 1521, not 1114.

>>4718265
It doesn't. 39 x 39 is 1521, not 1411.

holy shit
let's take a number
45
4 + 5 = 9
45 * 2 = 90
9 + 0 = 9
90 * 2 = 180
1 + 8 + 0 = 9
180 * 2 = 360
3 + 6 + 0 = 9
etc
let's try another number
111111111
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9
111111111 * 2 = 222222222
2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 = 18
1 + 8 = 2
222222222 * 2 = 444444444
4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 36
3 + 6 = 9
what the fuck
fucking nines and shit

>>4718313
New multi-million dollar blockbuster:
>The number 9

>>4717989
no, retard
10 prime? I don't think so.
It's MUCH simpler.

>>4715491
The sum of the digits of a number n written in base b is a multiple of a divisor k of b-1 if and only if n is also a multiple of k. A digit is dividable by a divisor of b^k if and only if the number formed by its last k digits is a multiple of b.

It's quite easy to prove, work it out.

It's elementary: in tradition base b notation, the digits form coefficient in a polynomial evaluated at b
ie<div class="math">a_n \dots a_1 a_0 = a_n b^n + \cdots + a_1 b^1 + a_0 b^0</div>where each <span class="math">a_i[/spoiler] is a digit less than b
figure out what this is mod <span class="math">b - 1[/spoiler]
spoiler <span class="math">b^i[/spoiler] mod <span class="math">b - 1[/spoiler] is 1

It's elementary: in traditional base b notation, the digits form coefficients in a polynomial evaluated at b
ie<div class="math">a_n \dots a_1 a_0=a_n b^n + \cdots + a_1 b^1 + a_0 b^0 \equiv a_n 1^n + \cdots + a_1 1^1 + a_0 1^0 \pmod{b - 1}</div>

>>4718388
Huh?

>>4715444

DEAR RETARDS:

All numbers in base 10 can be expressed be a + 10b + 100c + 1000d + ...

This is the same as 9b + 99c + 999d + ... a + b + c + d + ...

Obviously the first part of that is divisible by 9, so we just check the sum of the digits. If those are divisible by 9, then so is the whole number. Will this work for B-1 in base B? Let's see.

In any arbitrary base, a number is a + Bb + (B^2)c + (B^3)d + ... = (B-1)b + (B^2 - 1)c + ... + a + b + c + d + ...

If the sum of the digits is divisible by B -1, then so is the whole number. So yes OP, it works in any base.

As for 3 in base 10, we apply the same technique as for 9, but check if the sum of the digits is divisible by 3.
In any base, it will work for numbers which are a factor of B-1. In base 10, only 3 is a factor of 9 so that's why the trick works.

>>4718567
I'm sorry, but I don't follow.

Yes. It will always work. To understand why, consider modular arithmetic. An integers "modulus" or remainder is what's left over after you've divided out a base. For example, 70 = 7 * 9 + 7, so you could say that <div class="math"> 70 \equiv 7 \pmod{9} </div> (In modular arithmetic, the equal sign has three lines instead of two, don't ask me why).
So (mod 9) -14, -5, 4, 13, 22, so on are all considered equivalent because they all differ by multiples of 9. Addition and subtraction works the same, you just add the remainders. Since multiplication is just repeated addition, it also works modulo. For example, <div class="math"> 525 * 727 \equiv 3 * 7 \equiv 21 \equiv 3 (mod 9) </div>
Now when you write a k-digit number in base b, you can write it as.
<div class="math"> \sum_{i = 0}^{k-1} d_i b^i </div> When you take it (mod b-1) you can subtract b-1 from the b underneath the exponent and everything will still be equivalent.

<div class="math"> \sum_{i = 0}^{k-1} d_i (1)^i </div> So it's equivalent to the sum of its digits.

>>4718877
A similar trick is that if you add every other number then, subtract the rest of the numbers, you get the remainder when divided by 11.
I.e.
987654321
9-8+7-6+5-4+3-2+1=5
987654321 has a remainder of 5, when divided by 11.

fuck this is entry level comp sci shit
fuck off

OMFG!
>MFW OP's pic is Julian Assange.

division algorithm retard

>>4718823
>>4718535
>>4718237
>>4715773
>>4715604

he's trolling, abandon topic asap

>>4718923
You're right. I never bothered to read the comments, I just kind of got tunnel vision. I really enjoy this because I proved it myself after learning modular arithmetic :) OP's just a fag who can't be bothered to read a wikipedia article. /sci/bros are surprisingly willing to explain concepts to the most ignorant and lazy people.

>>4718556

I lol'd

bump

this issue is thoroughly unresolved