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

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?

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

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

• Sorry i forgot to mention i dont know modular arithmetic.. – user220382 Dec 20 '15 at 0:36
• You just have to know what the notation means. You don't have to use any deep theorem. – Bernard Dec 20 '15 at 0:38
• How deep a theorem do you consider Little Fermat? – fleablood Dec 20 '15 at 0:53
• 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$. – Lubin Dec 20 '15 at 1:46

$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 = 05|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 05|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] • Wonderful proof!!+1)) – Satish Ramanathan Dec 20 '15 at 1:45 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$.” 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.