# Modular Arithmetic (Basic)

• December 31st 2009, 01:45 AM
usagi_killer
Modular Arithmetic (Basic)
prove that a( a + 1 )(2a + 1) is divisible by 6 for every integer a.

Now my book says

"By taking least absolute residues mod (6), we see that a = 0, -1,1 -2,2 or 3"

What the hell does "least absolute residue" mean? Can someone explain this very carefully? (Yes I'm self learning so please don't leave out any important details)

And how do they get a = 0,-1,1,-2,2 or 3???????

Thanks very much!!!
• December 31st 2009, 02:13 AM
Bacterius
If this is divisible by $6$, then we have :

$a(a + 1)(2a + 1) \equiv 0 \pmod{6}$

Note that from the definition of the modulus operation, $a \in [0..5]$ (try with $a = 6$, you will get the same result than with $a = 0$). That comes from the fact that $ab \equiv (a \pmod{m})(b \pmod{m}) \pmod{m}$. Thus you can check all values of $a \in [0..5]$ :

$a = 0$, $0(0 + 1)(2 \times 0 + 1) \equiv 0 \pmod{6}$

$a = 1$, $1(1 + 1)(2 \times 1 + 1) \equiv 1 \times 2 \times 3 \equiv 6 \equiv 0 \pmod{6}$

Etc ... and you will find out that for $a \in [0..5]$, it works. Thus it works for $a + 6k$, with $k \in \mathbb{Z}$, which matches the set of all integer $a$.

Is it clear enough, or didn't you understand anything ?
• December 31st 2009, 03:26 AM
usagi_killer
Quote:

Originally Posted by Bacterius
If this is divisible by $6$, then we have :

$a(a + 1)(2a + 1) \equiv 0 \pmod{6}$

Note that from the definition of the modulus operation, $a \in [0..5]$ (try with $a = 6$, you will get the same result than with $a = 0$). That comes from the fact that $ab \equiv (a \pmod{m})(b \pmod{m}) \pmod{m}$. Thus you can check all values of $a \in [0..5]$ :

$a = 0$, $0(0 + 1)(2 \times 0 + 1) \equiv 0 \pmod{6}$

$a = 1$, $1(1 + 1)(2 \times 1 + 1) \equiv 1 \times 2 \times 3 \equiv 6 \equiv 0 \pmod{6}$

Etc ... and you will find out that for $a \in [0..5]$, it works. Thus it works for $a + 6k$, with $k \in \mathbb{Z}$, which matches the set of all integer $a$.

Is it clear enough, or didn't you understand anything ?

Thank you, that was so helpful!!
• January 1st 2010, 07:45 AM
SimonM
Alternatively:

$1^2+2^2+\ldots + a^2 = \frac{a(a+1)(2a+1)}{6}$
• January 1st 2010, 08:45 AM
Drexel28
Alternatively (alternatively):

Let $f(n)=n(n+1)\left(2n+1\right)$

Then $f(n+1)-f(n)=6\left(n+1\right)^2$ and the it follows by induction.