# Find the chance that $a^3 + b^3 \equiv 0 (\mod 3)$

We are given set of integer numbers $\{1,2, \dots N\}$. $N \ge 3$
Then perform a drawing with replacement of two elements $a$ and $b$.
Problem is to find the probability of following statement holding true:
$a^3 + b^3 \equiv 0\space (\mod 3)$

Solution draft
I believe Little Fermat theorem will be of help here, $a^3 \equiv a \space(\mod 3)$.
From there we conclude that either $a$ and $b$ both must be divisible by 3, or one must have residue 1 and other must have 2.
Total amount of possible $a$ and $b$ pairs is $n^2$.
Case when $3|a$ and $3|b$ is achievable for ${\lfloor \frac n 3 \rfloor}^2$ pairs.
Last case holds for the same amount of pairs.

Hence, answer would be $\frac {2{\lfloor \frac n 3 \rfloor}^2} {n^2} = \frac 2 9$
Is that a correct answer and is that legal to drop lowerbound around $\frac n 3$ here? Thanks!

Edit
Solution above is wrong.
Suppose, $N=4$
than (3,3) (2,1) (2,4) (1,2) (4,2) fits, hence $P= \frac 5 {16}$.
I would appreciate some suggestions.
Edit 2
$$P = \begin{cases} \frac 1 3 & if N \equiv 0 (\mod 3 )\\ \frac {{\lfloor \frac n 3 \rfloor}^2 + 2 \cdot \lfloor \frac n 3 \rfloor \lceil \frac n 3 \rceil}{n^2} & N \equiv 1 (\mod 3 )\\ \frac {{\lfloor \frac n 3 \rfloor}^2 + 2 \cdot \lceil \frac n 3 \rceil \lceil \frac n 3 \rceil}{n^2} & N \equiv 2 (\mod 3 ) \end{cases}$$

• For $N=1$ the probability is clearly $1$ – Hagen von Eitzen Nov 25 '14 at 20:20
• @HagenvonEitzen I see you point. Thanks. My solution must be for all possible N. But when I give it some thought... I believe the way the question is asked: $\{1,2, \dots N\}$ - allows us to assume that $N \ge 3$. – wf34 Nov 25 '14 at 20:26
• You don't need to give two expressions depending on the value of $N$. When $N=3$, the second expression becomes $1/3$. Now consider $N=5$. The valid pairs are $(1,2), (1,5), (2,1), (2,4), (3,3), (4,2), (4,5), (5,1)$ and $(5,4)$. So, the answer is $9/25$. Your answer says $\frac{1+2\times2}{25} = 1/5$. – Shash Dec 2 '14 at 11:08
• @Shash Yes, you was right and I made an edit. Thanks. – wf34 Dec 7 '14 at 19:31
• Yes, now it appears correct. You can simplify it as $$P(n) = \frac{\lfloor n/3\rfloor^2 + 2 \lfloor n/3 \rceil \lceil n/3 \rceil}{n^2}$$ for all $n$, where $\lfloor x\rceil$ denotes the round operation. – Shash Dec 8 '14 at 9:15

you can write all possible remainders by divisibility of $3$ these are $0,1,2$ and you will get $$a^3+b^3 \equiv \mod 0+0;1+0;0+1;1+1;2+0;0+2;2+1;1+2;2+2, 3$$ now we will find $$0+0;2+1;1+2\equiv 0 \mod 3$$