Modular Arithmetic (Basic)

**usagi_killer** · December 31st 2009, 01:45 AM

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!!!

**Bacterius** · December 31st 2009, 02:13 AM

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 ?

**usagi_killer** · December 31st 2009, 03:26 AM

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!!

**SimonM** · January 1st 2010, 07:45 AM

Alternatively:

$1^2+2^2+\ldots + a^2 = \frac{a(a+1)(2a+1)}{6}$

**Drexel28** · January 1st 2010, 08:45 AM

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.

Thread: Modular Arithmetic (Basic)

LinkBack

Thread Tools

Display

Modular Arithmetic (Basic)

Similar Math Help Forum Discussions

Modular arithmetic

Modular Arithmetic

Modular Arithmetic

Modular Arithmetic

Modular Arithmetic

Search Tags