Modular arithmetic

Consider the following theorem from secondary two.

A number is divisible by 3 if and only if the sum of its digits are also divisible by 3.

for eg, 1001020344 is divisible by 3,
because the sum of its digits, 1+0+0+1+0+2+0+3+4+4=15
and 15 is certainly divisible by 3.

To prove this theorem, know first that any number can be written as (a+10b+100c+...), where a,b and c are positive integers (I've notice that a surprising number of people do not know what integers are.. integers are also known as whole numbers. The set of integers is {....-3,-2,-1,0,1,2,3...})

For example, the number 345678 can be represented as;
8+10(7)+100(6)+1000(5)+10'000(4)+100'000(3)

Now that this is clarified, lets continue

suppose we have a number that is in the above form (a+10b+100c+1000d+...) where a,b,c are positive integers. and suppose that the number is divisible by 3.

Since it is divisible by 3, its remainder,when divided by 3 must be zero. In modular arithmetic this is written as;

a+10b+100c+1000d+... = 0 (mod3)

but from the previous post we also have 10^k=1 (mod 3)
which means that any power of ten equals to 1 under mod3.

Thus, we can replace the 10,100,1000.... in our equation above

We will get a+b+c+d+.... = 0 (mod3)

And hey the proof is complete! This shows that if any number is divisible by 3, the sum of its digits must also be divisible by 3. And all the action happens so fast!XD


Now for a deeper use of modular arithmetic.

we will show that if
7a²+7b²+6 = d²

then a,b and d can never be integers.
Under mod7, 7=0

thus the left side of the equation can be rewritten as
0a²+0b²+6=6

and the right hand side stays unchanged. Thus we have
6 = d²(mod 7)

now we just have to test for the possible values of d and show that d² cannot be 6 under mod 7.
since we restrict d to be an integer, d can only be 0,1,2,3,4....

0²=0=0(mod7)

1²=1=1 (mod7)

2²=4=4 (mod7)

3²=9=2 (mod7)

4²=16=2 (mod7)

5²=25=4 (mod7)

6²=36=1 (mod7)

haha and you actually thought i was going all the way to infinity didn't you! In fact we can stop here because 7 which is the next number, is equal to 0 under mod7 which means the the list of numbers repeat themselves.

to show you what i mean, see that
7²=0²=0(mod7)

8²=1²=1 (mod7)

9²=2²=4 (mod7)

notice that the second number in the equality is the same as the first list. Thus we only need to test for d=0 to d=6. Since in all these 7 cases, the numbers are not congruent to 6 (mod7), thus there is no positive integer that satisfies the congruence d²=6 (mod)7

And thus, there is no positive integer that will satisfy the equation 7a²+7b²+6 = d²

Haha.. damn chio man..Imagine know, out of the whole infinity of positive integers(1,2,3,4,5,6,7,8,9....) there is no combination that will solve the equality 7a²+7b²+6 = d²

Proving such a thing can be of no pratical use, but it is certainly an elegant display of the power of mathematics.

Kay off to continue killing poeple in GtaIV!!!