4
$\begingroup$

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}$$

$\endgroup$
  • 1
    $\begingroup$ For $N=1$ the probability is clearly $1$ $\endgroup$ – Hagen von Eitzen Nov 25 '14 at 20:20
  • $\begingroup$ @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$. $\endgroup$ – wf34 Nov 25 '14 at 20:26
  • $\begingroup$ 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$. $\endgroup$ – Shash Dec 2 '14 at 11:08
  • $\begingroup$ @Shash Yes, you was right and I made an edit. Thanks. $\endgroup$ – wf34 Dec 7 '14 at 19:31
  • $\begingroup$ 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. $\endgroup$ – Shash Dec 8 '14 at 9:15
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Looks like I cracked it. Would you take a look on my new edit? $\endgroup$ – wf34 Nov 25 '14 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.