Probability that $5 \mid x^4 - y^4$ for random $x, y$

Two numbers $x$ and $y$ are chosen at random without replacement from the set $\{1,2,3,\cdots,100\}$. Find the probability that $x^4 - y^4$ is divisible by $5$.

I don't know how to proceed with this problem. So any help would be appreciated.

• Hint: for $x = 1,2,3,4$, $x^4 \equiv1 \mod 5$. So you want to find the probability that both $x$ and $y$ are divisible by $5$ or that neither is. May 22, 2014 at 15:47
• As commented above, this should help. Now make cases and calculate the probability May 22, 2014 at 16:04

Here are the fourth powers modulo $5$: $$0^4 \equiv 0, 1^4 \equiv 1, 2^4 \equiv 1, 3^4 \equiv 1, 4^4 \equiv 1$$ (You can calculate these by hand, or conclude using Fermat's little theorem.) Anyway, $x^4 - y^4$ is a multiple of $5$ if and only if $x^4 \equiv y^4 \pmod 5$. There are $20$ multiples of $5$ and $80$ non-multiples, so the number of unordered pairs of numbers where $x^4 \equiv y^4 \pmod 5$ is $${20 \choose 2} + {80 \choose 2}$$ You should then divide this by the total number of ways of choosing $2$ numbers out of $100$.

• But answer is not coming 67/69 May 22, 2014 at 16:11
• Is there some error in the book's answer? May 22, 2014 at 16:12
• @user34304 I get the answer as $67 / 99$. What is the book's answer? May 22, 2014 at 16:16
• 67/69 is the answer May 22, 2014 at 16:19
• Maybe it's a printing error May 22, 2014 at 16:21

HINT:

If $\displaystyle 5|(x^4-y^4)$

Case $1:$

$\displaystyle 5|x^4$

as $5$ is prime, it must divide $x$ and subsequently $5|y^4\iff 5|y$

Case $2:$

As $5$ is prime, if $5\nmid x,(5,x)=1$

Now, $\displaystyle x^4-1=(x^2-1)(x^2+1)=(x-1)(x+1)(x^2-4+5)=(x-1)(x+1)(x-2)(x+2)+5(x^2-1)$

If $5\nmid x,5$ must divide exactly one of $(x-1),(x+1),(x-2),(x+2)$

$\displaystyle\implies 5\mid(x^4-1)$

Similarly, $5\nmid y,(5,y)=1$

Now there are $\displaystyle\frac{100}5=20$ multiples of $5$ in the given set

We need $$P\{xy, (xy,5)=1 \text{ or } (5|x\text{ and } 5|y)\}$$

Can you take it from here?

• Sir, I am not familiar with fermats little theorem. Btw, it's an iit problem, so is there an answer at that level? May 22, 2014 at 15:42
• @user34304, Let me edit May 22, 2014 at 15:45
• @user34304 : If you are familiar with congruences but not Fermat's Little Theorem, in this case you can just check it by hand, there are only $4$ cases to check and they are not long to compute. May 22, 2014 at 15:48
• @user34304, Please find the edited version May 22, 2014 at 15:53