2
$\begingroup$

Two numbers $x$ and $y$ are chosen at random without replacement from the set $\{1,2,3...,5n\}$.

What is the probability that $x^4-y^4$ is divisible by $5$?

I divided the numbers into groups of 5 $(1,2,3,4,5),(6,7,8,9,10),...$.The probability in the first group would itself be the answer.But how to find that?

$\endgroup$
1
  • 1
    $\begingroup$ Without replacement. That's not quite as tidy, alas. $\endgroup$ – Brian Tung Dec 20 '15 at 1:05
7
$\begingroup$

Hint: If $x \equiv 0\pmod{5}$, then $x^4 \equiv 0\pmod{5}$. If $x \not\equiv 0\pmod{5}$, then $x^4 \equiv 1\pmod{5}$ by Fermat's Little Theorem.

Alternatively, if you don't know modular arithmetic, you can do the following to get the same result.

If $x = 5q+r$ for some integers $q$ and $r$ with $0 \le r \le 4$, then we have $x^4 = (5q+r)^4$ $= 625q^4+500q^3r+150q^2r^2+20qr^3+r^4$ $= 5(125q^4+100q^3r+30q^2r^2+4qr^3)+r^4$ where $r^4$ is one of $\{0, 1, 16, 81, 256\}$. Thus, if $x$ is divisible by $5$, then so is $x^4$, and if $x$ is not divisible by $5$, then $x^4$ is one more than a multiple of $5$.

Hence, $x^4-y^4$ is divisible by $5$ iff $x$ and $y$ are both divisible by $5$ or both not divisible by $5$.

Here is how to finish the problem in case you are still stuck:

There are $5n(5n-1)$ total ways to choose $x$ and $y$ without replacement. There are $n(n-1)$ ways to choose $x$ and $y$ without replacement such that both are divisible by $5$, and there are $4n(4n-1)$ ways to choose $x$ and $y$ without replacement such that both are not divisible by $5$. Hence, the probability that $x^4-y^4$ is divisible by $5$ is $\dfrac{n(n-1)+4n(4n-1)}{5n(5n-1)} = \dfrac{17n-5}{25n-5}$.

$\endgroup$
4
  • $\begingroup$ Sorry i forgot to mention i dont know modular arithmetic.. $\endgroup$ – user220382 Dec 20 '15 at 0:36
  • $\begingroup$ You just have to know what the notation means. You don't have to use any deep theorem. $\endgroup$ – Bernard Dec 20 '15 at 0:38
  • 1
    $\begingroup$ How deep a theorem do you consider Little Fermat? $\endgroup$ – fleablood Dec 20 '15 at 0:53
  • 1
    $\begingroup$ In the case $p=5$, it’s not deep at all, ’cause you can try it out for the four cases: $(\pm1)^4=1$, $(\pm2)^4=16\equiv1\pmod5$. $\endgroup$ – Lubin Dec 20 '15 at 1:46
4
$\begingroup$

$x^4 - y^4 = (x^2 + y^2)(x^2 - y^2) = (x^2 + y^2)(x + y)(x - y)$.

If $x = 5k + j; 0 \le j < 5$ then $5|x^4 - y^4$ if $y = 5l + m; 0 \le m < 5$ where $m = j$; $m = 5 - j$; $m^2 + $j^2 = 5V$.

If $j = 0$ $5|x^4 - y^4 \iff m = 0$.

As $1 = 1 = 5 -4; 1^2 + 2^2 = 5; 1^2 + 3^2 = 10; 2 = 2 = 5 -3; 2^2 + 4^2 = 20; 3^2 + 4^2 = 25$. If $j \ne 0$ $5|x^2 - x^4 \iff m \ne 0$.

So... the ways it can be divisible by 5:

The first element is of form $a = 5k$ and the second is of form $b = 5m$. The probability of this is: 1/5*(n-1)/(5n - 1).

The first element is not of the form $a = 5k$ and the second is not of the form $b = 5m$. The probability of this is: 4/5*(4n -1)/(5n - 1).

These two possibilities are mutually exclusive so Probability is: [(n-1) + 4(4n - 1)]/5(5n - 1) = [17n -5]/[25n - 5]

$\endgroup$
1
  • $\begingroup$ Wonderful proof!!+1)) $\endgroup$ – Satish Ramanathan Dec 20 '15 at 1:45
0
$\begingroup$

It’s not hard to compute the probabilities (blue fractions below) for small values of $n$ by recording and counting (summing) $0$s and $1$s in a matrix of the pairs, where $1$ means “is divisible by $5$.”

enter image description here

The pattern is then not too hard to see, especially if you think to look at the column sums (row 19 in the picture):

For $n=1$, $p=\frac{1+2+3+0}{1+2+3+4}$, and for larger $n$, the probability seems to be $\frac{\left(1+2+\cdots(4n-1)\right)+(0+\cdots+(n-1))}{1+2+\cdots+(n-1)}$.

Once you see the pattern, you can then figure out what you need to show and get a simpler formula:

The difference is divisible by $5$ except when exactly one of the integers is a multiple of $5$ (I won’t prove this, since other people have). This happens for some multiple of $4$ pairs (see the vertical and horizontal groups of red zeroes?) — specifically, for $4$ times the $n$th number in the sequence $1, 1+3, 1+3+5+\dots$, or $4n^2$, of all the $5n\choose2$ pairs. Therefore the probability is $$\frac{{5n\choose2}-4n^2}{5n\choose2},$$ which can be simplified to $\frac{17n-5}{25n-5}$, the answer others have found.

$\endgroup$

Your Answer

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