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.
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ 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. $\endgroup$– user3294068May 22, 2014 at 15:47
-
$\begingroup$ As commented above, this should help. Now make cases and calculate the probability $\endgroup$– MathManMay 22, 2014 at 16:04
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
9
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$.
answered May 22, 2014 at 16:07
-
-
$\begingroup$ Is there some error in the book's answer? $\endgroup$ May 22, 2014 at 16:12
-
$\begingroup$ @user34304 I get the answer as $67 / 99$. What is the book's answer? $\endgroup$ May 22, 2014 at 16:16
-
-
$\begingroup$
$\endgroup$
4
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?
-
$\begingroup$ Sir, I am not familiar with fermats little theorem. Btw, it's an iit problem, so is there an answer at that level? $\endgroup$ May 22, 2014 at 15:42
-
-
$\begingroup$ @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. $\endgroup$ May 22, 2014 at 15:48
-
$\begingroup$ @user34304, Please find the edited version $\endgroup$ May 22, 2014 at 15:53