Two natural numbers $x$ and $y$ are chosen at random with a uniform distribution.Then the question is to find out the probability that $x^2+y^2$ is divisible by $5$ and $7$.
I understand that divisible by $5$ and $7$ is the same thing as divisible by $35$.But I am a bit confused on how to calculate probability on an infinite set.Any help shall be highly appreciated.Thanks.
Best Answer
First thing to note: you can not just take a "random number with a uniform distribution". My intuition "why not". Imagine you selected a random number. How big would it be? No way it will be less than a million: million is too small compared to infinity. And whatever upper bound you imagine the randomly selected number must be bigger than that. So there is some problem with "uniformly distributed integers". It's just an intuition, but hope it helps.
To fix the text of your problem it's necessary to set up an upper bound for selected numbers. Something like "Two natural numbers x and y are chosen at random with a uniform distribution in a range (0, N). Find the probability that $x^2+y^2$ is divisible by 35 for large N".
Probability that $x≡n \mod 35$ is 1/35. Probability that remainders of $x$ and $y$ when divided by 35 are $n$ and $m$ is $1/35^2$.
I had to write a short program that calculates $(x^2 + y^2) \mod 35$ (which is equal to $(n^2+m^2)\mod 35$) for all 35^2 possible pairs of $(n, m)$. It turned out that there are exactly 5 pairs such that $(n^2 + m^2)$ is divided by 35. So, the answer is $5/35^2$.
Takahiro's approach must be smarter, but I am too slow to follow it :)